Card 01/ 09
Stacks and Queues: Last In First Out, First In First Out
A stack hands back the newest item first, and a queue hands back the oldest.
A stack and a queue both hold items waiting to be dealt with, and they differ only in which item leaves first: a stack hands back the newest, and a queue the oldest. This card covers the two orders, the operations each structure offers, and what those operations cost.
A pile of clean plates works like a stack. Plates go on the top and come off the top, so the plate washed last is the first one used. A queue at a ticket office works the other way: people join at the back and are served from the front, so whoever arrived first leaves first. The likeness breaks in the middle: a person can leave a real queue from anywhere, but only the front item can leave a queue structure.
A stack is last in, first out, often shortened to LIFO. Push adds an item on top, pop removes the top item and returns it, and peek returns the top item without removing it. A queue is first in, first out, or FIFO. Enqueue adds an item at the back, dequeue removes the item at the front and returns it, and peek returns the front item. Neither lets a program reach an item in the middle, and that restriction is what keeps every operation cheap.
A run added A, B and C to an empty stack and to an empty queue, then removed one item from each. It printed the stack from its top and the queue from its front, so the first item on each line is the one that would leave next.
The same three items through a stack and a queue
Add A
With one item, the top of the stack and the front of the queue are the same item.
stack, top first: A
queue, front first: AAdd B
B goes on top of the stack, and joins the queue at the back.
stack, top first: B A
queue, front first: A BAdd C
Both structures now hold the same three items, in opposite orders of leaving.
stack, top first: C B A
queue, front first: A B CRemove one item from each
Pop returns C, the newest item, and dequeue returns A, the oldest.
stack, top first: B A
queue, front first: B CIn general, a stack serves the most recent item still waiting, and a queue serves the item that has waited longest. Each is defined by that order alone, not by how it stores its items, so either can sit on an array or on a linked list. With the storage chosen well, every operation is O(1), though a push onto an array that has to grow is O(1) only amortised, meaning averaged over many pushes.
| Operation | Stack | Queue | Cost |
|---|---|---|---|
| Add an item | Push, onto the top | Enqueue, at the back | O(1) |
| Remove an item | Pop, from the top | Dequeue, from the front | O(1) |
| Look at the next item to leave | Peek at the top | Peek at the front | O(1) |
| Check whether it is empty | Compare the size with zero | Compare the size with zero | O(1) |
An emergency department is neither: patients are seen by urgency, not by arrival, so a heart attack goes ahead of a sprained wrist that has waited an hour. That order needs a priority queue, a structure that hands back the most urgent item whatever its age. The question that chooses between a stack and a queue is which item a problem needs next: the newest unfinished one calls for a stack, and the one that has waited longest calls for a queue.
← → move through sections and cards