Data Structures · Data structures

Stacks & queues

Choose what leaves next: the newest item or the oldest.

Same items. Different next item.

Stacks and queues hold pending items but choose the next one differently. A stack removes the newest item first: last in, first out. A queue removes the oldest item first: first in, first out. The right choice expresses the order your program needs.

Undo and a waiting line need different orders.

Undo usually reverses the most recent action first, so a stack fits. An arrival-order waiting line serves the earliest arrival first, so a queue fits. These are container policies; a stack container is not the same thing as the program’s call stack.

Add and remove at the top.

After pushing A, B, then C, C is the top. Popping removes C and exposes B. You do not traverse to the oldest item to choose the next removal.

Stack top is C, followed by B and A. Remove C first, from the same end where it was added.

C · top: remove here
B
A · oldest

Join at the back, leave at the front.

After enqueuing A, B, then C, A is at the front. Removing A makes B next. A newly enqueued D goes behind C, so it does not jump ahead of B.

Queue front is A, then B, then C at the back. Remove at A; new items join after C.

A · front: remove here
B
C · back: append after here

A · front leads to B
B leads to C · back

Read before removing.

The stack’s top is 30, but the queue’s front is 10. In these C++ adapters pop removes an item and returns no value. Read top or front before pop, and first ensure the container is nonempty.

std::stack<int> undo;
std::queue<int> waiting;
for (int value : {10, 20, 30}) {
    undo.push(value);
    waiting.push(value);
}
std::cout << undo.top() << ' ' << waiting.front();