Stacks & queues

Stacks

A stack hands back the last thing you put on it

A stack is a list you only touch at one end, the top. You push an item onto the top and pop the top item off. Whatever went on last comes off first: last in, first out, or LIFO.

That rule matches a lot of real work:

an editor's undo history pops the most recent change first;
a browser's back button returns to the page you came from most recently;
a running program keeps its function calls on a stack, so a function returns to whichever call started it.

A dynamic array is all a stack needs. Push is an append at the end, O(1) amortized; pop removes the last item, O(1). Nothing ever shifts, because nothing happens at the front. In the pseudocode, append x to stack pushes and pop(stack) pops.

Using a stack

A stack matches whatever opened last with whatever closes next

Are the brackets in {[]()} balanced? Each closing bracket has to match the most recent opening bracket that hasn't been closed yet. "Most recent, not yet closed" is exactly what the top of a stack holds.

So: push every opening bracket. At a closing bracket, pop the top and check that the two match. If the stack is empty when a closer arrives, or the pair doesn't match, or openers are left over at the end, the string isn't balanced.

Each character is pushed or popped at most once, so the check is O(n) time, with up to n items on the stack.

Queues

A queue serves items in the order they arrived

A queue adds at one end, the back, and removes from the other, the front: first in, first out, or FIFO. Adding is called enqueue, removing dequeue. Print jobs, customer-support tickets and tasks waiting for a worker all work this way.

A plain dynamic array is a bad queue. Dequeuing removes the front item, and an array's front can only be removed by shifting every other item left: O(n) per dequeue. Python's documentation warns about exactly this for its list.

Two structures make both ends O(1):

a linked list with a head and a tail: enqueue links a node after the tail, dequeue moves the head one node on;
a ring buffer, below, which keeps the array's compact memory.

The ring buffer

A ring buffer lets a fixed array act as a queue

Instead of shifting items toward the front, let the front move. Keep the index of the front item and the number of items. Dequeuing reads the front cell and moves the front index one cell on; enqueuing writes at front + size.

Both indexes run off the end of the array eventually. The trick is to wrap them around to the start with mod: in a 4-cell array, the cell after 3 is (3 + 1) mod 4 = 0. The cells freed at the start by earlier dequeues get used again, as if the array were a ring.

The rule

Choose the structure by which end you take from. Take the newest item: a stack. Take the oldest: a queue. Both do every operation in O(1).

When a ring buffer is full, there are three choices: refuse the new item, overwrite the oldest (a log that keeps only recent lines), or copy everything into a bigger ring the way a dynamic array grows.

Hard

A second stack remembers the minimum

A stack can report its smallest item in O(1) if a second stack moves with it. Each time an item is pushed, push the smaller of it and the current minimum onto mins. Each pop removes the top of both. The top of mins is always the smallest item still on the stack, because it was computed from exactly those items.

One number for the minimum wouldn't work: when the smallest item is popped, the next smallest is unknown without a search. Keeping the minimum for every height means the answer for the stack below is already waiting.

A queue can be built from two stacks: push arrivals onto an inbox, serve from an outbox, and when the outbox is empty pour the whole inbox across, which reverses its order so the oldest item ends up on top. One pour is O(n), but each item is poured exactly once in its life, so the cost per operation is O(1) amortized, the idea from Space & amortized analysis.

Deques

A deque works at both ends

A deque (a double-ended queue, pronounced "deck") allows adding and removing at both ends in O(1). A ring buffer gives you one almost for free: move the front index back one cell to add at the front.

Because a deque does everything a stack and a queue do, it is what most standard libraries offer for both:

Language	As a stack	As a queue
Python	`list` (append, pop)	`collections.deque`
Java	`ArrayDeque`	`ArrayDeque`
C++	`std::stack` (over `std::deque`)	`std::queue` (over `std::deque`)
JavaScript	an array (push, pop)	no built-in; a ring buffer or two stacks

Java's documentation notes that ArrayDeque, a ring buffer that grows as needed, is likely to be faster than its older Stack class as a stack and faster than LinkedList as a queue. In JavaScript, shift() removes the front of an array, but like any front removal it may cost O(n).

Check yourself

4 questions

1. You push 1, 2 and 3 onto a stack, pop once, then push 4. What do the next two pops return?

2. Why is a plain dynamic array a poor queue?

3. A ring buffer has 8 cells. The front item is in cell 6 and the queue holds 3 items. Which cell does the next enqueue write to?

4. Which problem fits a stack rather than a queue?

Takeaways

Remember this

A stack is last in, first out: push and pop at one end, both O(1) on a dynamic array.
A queue is first in, first out: enqueue at the back, dequeue at the front.
A dynamic array makes a poor queue, because removing the front shifts everything; use a ring buffer or a linked list with a tail.
A ring buffer moves the front index instead of the items and wraps around with mod.
A deque does both ends in O(1), which is why libraries offer it for stacks and queues alike.

Practice

Now solve some yourself

Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.