Truy cập cấu trúc dữ liệu: Hàng đợi

Phân tích và triển khai cấu trúc dữ liệu Hàng đợi trong Go

Hàng đợi là một tập hợp các mục có thứ tự theo nguyên tắc Nhập trước Xuất trước (FIFO). Chúng tôi thêm các mục từ một đầu của hàng đợi và chúng tôi lấy các mục từ đầu kia.

Các ứng dụng hàng đợi có tất cả các loại sử dụng, có thể dễ dàng suy ra từ các hàng đợi trong thế giới thực. Không khó để tưởng tượng cảnh xếp hàng đại diện cho hàng siêu thị hoặc hàng đợi để vào phòng hòa nhạc.

Thực hiện

Bên trong hàng đợi sẽ được biểu thị bằngslicegõ, và tôi sẽ hiển thị

  • New()
  • Enqueue()
  • Dequeue()
  • Front()
  • IsEmpty()
  • Size()

các phương pháp.

New()đóng vai trò là phương thức khởi tạo, khởi tạo lát bên trong khi chúng ta bắt đầu sử dụng nó.

Tôi sẽ tạo mộtItemQueueloại chung, an toàn đồng thời, có thể tạo hàng đợi chứa bất kỳ loại nào bằng cách sử dụnggenny, để tạo triển khai hàng đợi kiểu cụ thể, đóng gói cấu trúc dữ liệu giá trị cụ thể thực tế có chứa dữ liệu.

// Package queue creates a ItemQueue data structure for the Item type
package queue

import ( “sync”

<span style="color:#e6db74">"github.com/cheekybits/genny/generic"</span>

)

// Item the type of the queue type Item generic.Type

// ItemQueue the queue of Items type ItemQueue struct { items []Item lock sync.RWMutex }

// New creates a new ItemQueue func (s ItemQueue) New() ItemQueue { s.items = []Item{} return s }

// Enqueue adds an Item to the end of the queue func (s *ItemQueue) Enqueue(t Item) { s.lock.Lock() s.items = append(s.items, t) s.lock.Unlock() }

// Dequeue removes an Item from the start of the queue func (s ItemQueue) Dequeue() Item { s.lock.Lock() item := s.items[0] s.items = s.items[1:len(s.items)] s.lock.Unlock() return &item }

// Front returns the item next in the queue, without removing it func (s ItemQueue) Front() Item { s.lock.RLock() item := s.items[0] s.lock.RUnlock() return &item }

// IsEmpty returns true if the queue is empty func (s *ItemQueue) IsEmpty() bool { return len(s.items) == 0 }

// Size returns the number of Items in the queue func (s *ItemQueue) Size() int { return len(s.items) }

Kiểm tra

Các bài kiểm tra mô tả việc sử dụng triển khai trên.

package queue

import ( “testing” )

var s ItemQueue

func initQueue() *ItemQueue { if s.items == nil { s = ItemQueue{} s.New() } return &s }

func TestEnqueue(t *testing.T) { s := initQueue() s.Enqueue(1) s.Enqueue(2) s.Enqueue(3)

<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">s</span>.<span style="color:#a6e22e">Size</span>(); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">3</span> {
    <span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 3 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}

}

func TestDequeue(t *testing.T) { s.Enqueue(1) s.Enqueue(1) s.Enqueue(1) s.Dequeue() if size := len(s.items); size != 2 { t.Errorf(“wrong count, expected 2 and got %d”, size) }

<span style="color:#a6e22e">s</span>.<span style="color:#a6e22e">Dequeue</span>()
<span style="color:#a6e22e">s</span>.<span style="color:#a6e22e">Dequeue</span>()
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">size</span> <span style="color:#f92672">:=</span> len(<span style="color:#a6e22e">s</span>.<span style="color:#a6e22e">items</span>); <span style="color:#a6e22e">size</span> <span style="color:#f92672">!=</span> <span style="color:#ae81ff">0</span> {
    <span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"wrong count, expected 0 and got %d"</span>, <span style="color:#a6e22e">size</span>)
}

<span style="color:#66d9ef">if</span> !<span style="color:#a6e22e">s</span>.<span style="color:#a6e22e">IsEmpty</span>() {
    <span style="color:#a6e22e">t</span>.<span style="color:#a6e22e">Errorf</span>(<span style="color:#e6db74">"IsEmpty should return true"</span>)
}

}

Tạo cấu trúc dữ liệu hàng đợi cụ thể

Bạn có thể sử dụng cách áp dụng chung này để tạo hàng đợi loại cụ thể, bằng cách sử dụng

//generate a `IntQueue` queue of `int` values
genny -in queue.go -out queue-int.go gen "Item=int"

//generate a </span>StringQueue<span style="color:#e6db74"> queue of </span>string<span style="color:#e6db74"> values genny -in queue.go -out queue-string.go gen “Item=string”


Các hướng dẫn về go khác: