A Queue is a linear data structure (i.e. its elements form a sequence) and can be modified by the addition of elements at one end of the sequence and removal from the other end. A queue is a FIFO (First In, First Out) data structure.

The queue data structure works in exactly the same way as its real life analogue — the first element in the queue is automatically at the front, with subsequent elements forming in line behind their precedent.

Queues can be used to control access to shared system resources e.g. a printer queue managing access to a printer on a first come, first served basis. Queues can also feature in any architecture involving asynchronicity e.g. purchasing event tickets online.

Typically, a queue implementation will provide at least three operations — enqueue, dequeue, and peek.

Enqueuing and dequeuing can be visualised at follows:

Complexity

🔔 Complexity is considered in terms of worst case.

Time

Space

An implementation

Here we’re using an array as a backing store for simplicity (although you can of course use a different approach such as a doubly linked list which can provide enqueing and dequeing in Θ(1) time).

Define a Queue<T> class with the following methods:

• dequeue - dequeues an element, removing it from the queue
• enqueue - enqueues an element, adding it to the queue
• isEmpty - determines whether the queue is empty
• length - returns the number of elements in the queue
• peek - returns the front element in the queue without dequeuing it

// TypeScript
export class Queue<T> {
	private elements: T[];

	public constructor() {
		this.elements = new Array<T>();
	}

	public dequeue(): T | undefined {
		if (this.elements.length > 0) {
			return this.elements.pop();
		}
		return undefined;
	}

	public enqueue(element: T): void {
		this.elements.unshift(element);
	}

	public isEmpty(): boolean {
		return this.elements.length < 1;
	}

	public length(): number {
		return this.elements.length;
	}

	public peek(): T | undefined {
		return !this.isEmpty() ?
			this.elements[this.elements.length - 1] :
			undefined;
	}
}

Code on Github