Go数据结构:队列

Go中Queue数据结构的分析与实现

队列是遵循先进先出(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”


更多教程: