Go data structure: queue

Analysis and Implementation of Queue Data Structure in Go

A queue is an ordered collection of items following the first in first out (FIFO) principle. We add items from one end of the queue, and then retrieve items from the other end.

Queue applications have various uses, which can be easily inferred from actual queues. It is not difficult to imagine the queue in the supermarket or the queue in the concert hall.

carried out

Internally, the queue will usesliceType, I will expose

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

method.

New()Used as a constructor, it will initialize the internal slice when we start using it.

I will create aItemQueueGeneric type, concurrency safety, you can use the following command to generate a queue containing any typegennyTo create a type-specific queue implementation, encapsulating the actual value-specific data structure that contains the data.

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

test

These tests describe the usage of the above implementation.

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

}

Create a specific queue data structure

You can use the following generic implementation to generate a type-specific queue by using

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


More tutorials: