A queue is a an ordered collection of items following the First-In-First-Out (FIFO) principle. We add items from one end of the queue, and we retrieve items from the other end.
Queue applications have all sorts of uses, which can be easily inferred from real-world queues. It’s not hard to imagine a queue representation of a supermarket line or the queue to get into a concert hall.
Implementation
Internally the queue will be represented with a slice
type, and I’ll expose the
New()
Enqueue()
Dequeue()
Front()
IsEmpty()
Size()
methods.
New()
serves as the constructor, which initializes the internal slice when we start using it.
I’ll create an ItemQueue
generic type, concurrency safe, that can generate queues containing any type by using genny
, to create a type-specific queue implementation, encapsulating the actual value-specific data structure containing the data.
// Package queue creates a ItemQueue data structure for the Item type
package queue
import (
"sync"
"github.com/cheekybits/genny/generic"
)
// 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)
}
Tests
The 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)
if size := s.Size(); size != 3 {
t.Errorf("wrong count, expected 3 and got %d", size)
}
}
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)
}
s.Dequeue()
s.Dequeue()
if size := len(s.items); size != 0 {
t.Errorf("wrong count, expected 0 and got %d", size)
}
if !s.IsEmpty() {
t.Errorf("IsEmpty should return true")
}
}
Creating a concrete queue data structure
You can use this generic implemenation to generate type-specific queues, using
//generate a `IntQueue` queue of `int` values
genny -in queue.go -out queue-int.go gen "Item=int"
//generate a `StringQueue` queue of `string` values
genny -in queue.go -out queue-string.go gen "Item=string"
More go tutorials:
- Using NGINX Reverse Proxy to serve Go services
- Making a copy of a struct in Go
- The basics of a Go Web Server
- Sorting a map type in Go
- Go pointers in a nutshell
- Go Tags explained
- Go Date and Time Formatting
- JSON processing with Go
- Go Variadic Functions
- Go Strings Cheat Sheet
- The Go Empty Interface Explained
- Debugging Go with VS Code and Delve
- Named Go returns parameters
- Generating random numbers and strings in Go
- Filesystem Structure of a Go project
- Binary Search Algorithm Implemented in Go
- Using Command Line Flags in Go
- GOPATH Explained
- Build a Command Line app with Go: lolcat
- Building a CLI command with Go: cowsay
- Using Shell Pipes with Go
- Go CLI tutorial: fortune clone
- List the files in a folder with Go
- Use Go to get a list of repositories from GitHub
- Go, append a slice of strings to a file
- Go, convert a string to a bytes slice
- Visualize your local Git contributions with Go
- Getting started with Go CPU and memory profiling
- Solving the "does not support indexing" error in a Go program
- Measuring execution time in a Go program
- Building a Web Crawler with Go to detect duplicate titles
- Go Best Practices: Pointer or value receivers?
- Go Best Practices: Should you use a method or a function?
- Go Data Structures: Set
- Go Maps Cheat Sheet
- Generate implementations for generic types in Go
- Go Data Structures: Dictionary
- Go Data Structures: Hash Table
- Implement Events Listeners in Go through Channels
- Go Data Structures: Stack
- Go Data Structures: Queue
- Go Data Structures: Binary Search Tree
- Go Data Structures: Graph
- Go Data Structures: Linked List
- The complete guide to Go Data Structures
- Comparing Go Values
- Is Go object oriented?
- Working with a SQL Database in Go
- Using environment variables in Go
- Go tutorial: REST API backed by PostgreSQL
- Enabling CORS on a Go Web Server
- Deploying a Go Application in a Docker Container
- Why Go is a powerful language to learn as a PHP developer
- Go, remove the io.Reader.ReadString newline char
- Go, how to watch changes and rebuild your program
- Go, count the months since a date
- Accessing HTTP POST parameters in Go