Premium

Queue

Basic Algorithms
≈ 2 min read

First in, first out

A queue follows the FIFO (First In, First Out) principle: elements are removed in the same order in which they were added. Insertion happens at the tail, while reading and removal happen at the head. 

Deque<String> queue = new ArrayDeque<>();

queue.addLast("A");
queue.addLast("B");
queue.addLast("C");

String first = queue.peekFirst(); // A
String removed = queue.removeFirst(); // A

After removing A, B becomes the first element. For ArrayDeque, adding at the tail and removing from the head are amortized O(1) operations.

When a queue fits the problem

A queue is useful when an earlier element must be processed before a later one. For example, if an algorithm gradually discovers new states and must process them in discovery order, a queue preserves that order naturally without manually shifting array elements.

The main difference from a stack is not the stored data but the removal rule. The same set of values will be processed in a different order if FIFO is replaced with LIFO, and that can completely change an algorithm's behavior.

Do not implement a queue by repeatedly removing the first element of a plain array. Shifting the remaining elements every time makes removal O(n). A Deque maintains structure boundaries without those shifts.
Back Next