A queue is a collection data type in which elements are removed in the order that they were inserted (with the first being inserted being removed first). Queues define two main operations:

• Enqueue: which adds an element to the end of the collection.
• Dequeue: which removes the first added element.

Additionally, a peek operation can be implemented which returns the first value added without removing it.

Abstract Data Type

template <class T>
class Queue {
	public:
		Queue();
	
		// Insert into the back of the queue
		void enqueue(const T& element);
		
		// Remove and return from the front of the queue
		T dequeue();
}

Implementation

Singly Linked List

Using a singly linked list with head and tail pointer the front of the queue. New elements are inserted at the tail of the linked list and elements are removed from the head to ensure insertions and deletions.

Circular Array

A circular array can be used to create a queue by maintaining an integer that stores the index of the front and the back of the queue.

When elements of the queue are removed instead of having to move all the elements in the array backwards one index (an operation) we can instead just increment the index to the front of the queue a operation. Additionally the addition operation can also be implemented in by inserting into the end of the array and incrementing the counter for the back of the queue

If the queue's max size is unknown the circular array can be combined with a resizable array to ensure the queue can grow as necessary, otherwise a fixed size can be decided with older elements being overwritten as required.