データ構造の移動:キュー

Goでのキューデータ構造の分析と実装

キューは、先入れ先出し(FIFO)の原則に従って順序付けられたアイテムのコレクションです。キューの一方の端からアイテムを追加し、もう一方の端からアイテムを取得します。

キューアプリケーションにはさまざまな用途があり、実際のキューから簡単に推測できます。スーパーマーケットの列の列の表現やコンサートホールに入るための列を想像するのは難しいことではありません。

実装

内部的には、キューはで表されますsliceタイプ、そして私は公開します

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

メソッド。

New()コンストラクターとして機能し、使用を開始すると内部スライスを初期化します。

作成しますItemQueueジェネリック型、並行性セーフ、を使用して任意の型を含むキューを生成できますgenny、タイプ固有のキュー実装を作成し、データを含む実際の値固有のデータ構造をカプセル化します。

// 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) }

テスト

テストでは、上記の実装の使用法について説明します。

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>)
}

}

具体的なキューデータ構造の作成

この一般的な実装を使用して、を使用してタイプ固有のキューを生成できます。

//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”


その他のチュートリアル: