Implementing a Queue Using a Linked List in C++

In the last post, we implemented a stack, a container that operates on a last-in, first-out policy. This time, we take a look at the queue, which is instantly and practically recognizable. Orders that come into a restaurant may be processed based on when a customer sits down. The lines for rides at a theme park operate on a first-in, first-out policy (unless you have a fast pass). You may even be in a queue (as "lines" are referred to outside of the US) at this very moment.

In this post, we will implement a queue using C++.

Defining the API

The interface of a queue is similar to that of a stack, with different names for some operations. The defining feature of a queue is that it operates on a first-in, first-out (LIFO) policy. This means that elements are removed from the front of the queue and added to the back. It also means that iteration should proceed from the front of the queue to the back.

With that in mind, our API should have the following minimal features:

• is_empty - Returns true if the queue is empty.
• size - Returns the number of elements in the queue.
• enqueue - Add an element to the back of the queue.
• dequeue - Remove an element from the front of the queue.
• begin and end - For iteration.

Storage Using Linked List

We implemented the stack using a dynamically sized array. An array worked well in that context because pushes and pops only affected the top of the stack. If we wanted to remove an item from the bottom of the stack, it would be much more costly, as all higher items would need to be adjusted down.

Thus, for a queue, we will prefer to store data in a linked list. A linked list consists of a series of nodes. Each node contains an item of the desired type and a pointer to the next node in the list. A node pointed to by no other is considered the head of the list and a node that points to no other is considered the tail of the list.

To implement this list, we define a structure called Node within our Queue class.

struct Node
{
  T item_;
  Node* next_;

  Node(T item)
	  : item_(item)
    , next_(nullptr)
	{

	}
}

The constructor stores the provided item and sets the next_ to nullptr. Like Stack, Queue is a template type, and the type T of item_ comes from the containing Queue class.

Our Queue class contains just three members: a head_ and tail_ to track the first and last nodes in the list and n_ to track the size of the list.

Node* head_;
Node* tail_;
int n_;

Queueing and Dequeueing

To add an item to the back of the queue, we start by caching the old tail and pointing tail to a new Node that contains the desired item. If the old tail is valid, point it to the new tail to complete the chain. If the old tail is null, it means the list was empty. We can infer that the head is also null, and we fix that up by pointing it to the new tail.

void enqueue(T item)
{
	Node* old_tail = tail_;
	tail_ = new Node(item);

	if (old_tail)
	{
		old_tail->next_ = tail_;
	}

	else
	{
		head_ = tail_;
	}

	++n_;
}

To remove an item from the front of the queue, we follow a similar process. Grab the item stored in the head, and move the head pointer up, cleaning up the old head in the process and updating the count.

If head is now null, it means the list is empty. We can infer that the list previously had one item in it and that tail was pointing to that item. Accordingly, we null out tail as well.

T dequeue()
{
	T item = head_->item_;
	Node* old_head = head_;
	head_ = head_->next_;
	delete old_head;

	if (head_ == nullptr)
	{
		tail_ = head_;
	}

	--n_;
	return item;
}

Query Size Information

As with stack, size information is easy to gather using the members we have declared. The size method simply returns the item count stored in n_. The is_empty method returns true if head_ is null.

int size() { return n_; }
bool is_empty() { return head_ == nullptr; }

Iterating Over the List

As before, iteration is a bit beyond the scope of this post. Suffice to say, the following Iterator class is implemented within Queue.

class Iterator
{
	Node* current_;

public:

	Iterator()
		: current_(nullptr)
	{

	}

	Iterator(Node* first)
		: current_(first)
	{

	}

	void operator++()
	{
		current_ = current_->next_;
	}

	bool operator!=(const Iterator& Other)
	{
		return current_ != Other.current_;
	}

	T& operator*()
	{
		return current_->item_;
	}
};

In turn, Queue implements the following start and end functions to iterate from start to finish.

Iterator begin()
{
	return Iterator(head_);
}

Iterator end()
{
	return Iterator();
}

Cleaning Up Memory

Because every entry in the queue is dynamically allocated, we need to make sure to clean up after ourselves once the queue is destroyed. In the destructor, we iterate over the list, deleting nodes as we go.

~Queue()
{
	for (Node* current = head_; current != nullptr;)
	{
		Node* temp = current;
		current = current->next_;
		delete temp;
	}
}

Testing the Implementation

To test this implementation of the queue, try running the following client code.

#include <iostream>
#include <string>

#include "queue.h"

int main()
{
	Queue<std::string> orders;
	orders.enqueue("burger");
	orders.enqueue("fries");
	orders.enqueue("shake");

	while (!orders.is_empty())
	{
		std::cout << "Order up: " << orders.dequeue() << std::endl;
	}
}

The program should print the items in the queue from oldest to newest.

Order up: burger
Order up: fries
Order up: shake

Closing Thoughts

Both enqueue and dequeue are quick operations that take constant time regardless of the length of the list. However, adding items to the middle of the list may be expensive, potentially taking up to n - 1 reads.

This implementation also provides no way to iterate backwards over the queue. That concern, and others, might be addressed by replacing the storage with a doubly linked list. But that is an issue for another day.