Implementing Queue In Go

This article discusses the queue data structure in computer science: what the queue data structure is, the queue fundamental operations, an example of a slice-based queue implementation.

Defining Queue as Abstract Data Type

In computer science, a queue is an abstract data type which serves a linear collection of items. An item can only be inserted at the end, rear, and removed from the other end front according to the FIFO (first-in, first-out) principle.

Pic. 1. An illustration of the Queue model

An analogy to help you understand the queue principle is to think of a queue as a line of people who are waiting for service. The newcomer goes at the end of the queue while the person who at the beginning gets service.

An underlying data type for a queue could be an array or a linked list.

Declaring Queue Type

The same as the stack, we declare the queue as the struct with the items and mutex fields.

Operations

There are two fundamental operations for the queue: Enqueue() and Dequeue().

queue.Enqueue(item Item)

Inserts the item at the end (rear) of the queue.

Pic. 2. An illustration of the Enqueue() method

For inserting the new item into the queue we use the append() built-in function, which inserts a new item at the end of the slice.

queue.Dequeue() Item

Removes the last item from the beginning (front) of the queue and returns the removed item.

Pic. 3. An illustration of the Dequeue() method

Since the function Dequeue() returns the removed item, before re-slicing we initialize the variable lastItem and store the removed item inside the variable:

lastItem := queue.items[0]

And then, we re-slice the queue with the following statement:

queue.items = queue.items[1:]

As a result, we get all the items from the second (first index) to the last from the queue. The first item in the queue has a zero index.

Also, applying this method to an empty queue must return nil. Thus, before removing an item we need to check the length of the queue. In the following example, the method returns nil if the length of the queue is equal to zero:

main()

Create a new instance of the queue in the main.go file. Add new items with the Enqueue() method. In the example below we created the queue that consists of several items:

5←4←3←2←1

To see the full queue use Dump().

The last item (front) in this queue is 5, and the first (rear) is 1.

To empty the queue use Reset().

To know whether the queue is empty or not use IsEmpty(). True if the queue is empty, and false if the queue is non-empty.

The methods Dump(), Reset(), Peek(), and IsEmpty() are omitted in this article as they have already been discussed here.

Jane is a Go programmer and technical writer in software engineering. She has been writing technical material for 5 years in both English and Russian. She completed her specialist degree in Information Security from Novosibirsk State Technical University, and specializes in the information security of automated systems. You can follow her on Twitter and see her other written work at publications.enthusiastic.io.