Stacks and Queues

When processing order matters

Arrays and hash tables help us access data quickly by index or key, but some problems are organized differently: what matters is not only what is stored, but in what order elements must be removed. A stack returns the most recently added element, a queue returns the earliest one, and a deque lets us work with both ends.

These structures are especially useful when an algorithm needs to remember unfinished actions, process events in arrival order, or maintain a small set of candidates from which elements leave according to a strict rule. They also form the basis for stronger techniques such as monotonic structures and nesting checks.

What this section covers

• Stack. We will examine the LIFO principle and the operations for adding, viewing, and removing the top element.
• Queue. We will move to the FIFO principle and process elements in the order they arrive.
• Deque. You will learn to add and remove elements at both ends of one structure.
• Monotonic Stack. We will see how to keep a stack ordered and quickly find nearby suitable elements.
• Monotonic Queue. We will apply a similar idea to a window of data and keep only useful candidates.
• Parentheses Problems. We will use a stack to check proper nesting and match opening and closing symbols.
• Queue Using Stacks. We will build one abstraction on top of another and see how moving elements changes removal order.

One interface, different rules

Deque<Integer> values = new ArrayDeque<>();
values.push(10);
values.push(20);

int last = values.pop(); // 20

In the following topics, the important part is not memorizing a set of methods, but seeing the rule by which the structure returns elements. That rule usually tells us whether a problem needs a stack, a queue, or a deque.