Pointer Walk

Stacks and Queues

Put the same three items into both. A stack gives back the last one first. A queue gives back the first one first.

Data StructuresBeginner7 min read

Two rules for taking things out

Many programs need a place to put things for later. Often it does not matter which thing comes out next, as long as there is a clear rule. Two rules cover most cases, and each has its own data structure.

  • A stack hands back the item added most recently.
  • A queue hands back the item that has been waiting longest.

That is the whole difference. Give both the same items and watch what comes out.

A stack and a queue, same instructionsInteractive

Stack

Add and remove at the same end. Last in, first out.

Came out

Queue

Add at one end, remove from the other. First in, first out.

Came out

Start. Two empty containers. Both will be given the same items in the same order, and asked to hand one back at the same moments.

Stack: last in, first out

Think of a stack of plates. You put a plate on top and you take a plate from the top. The plate at the bottom was the first one there and will be the last to leave.

A stack has two operations.

  • Push: put an item on top.
  • Pop: take the top item off.

Both touch only one end, so both are instant however tall the stack is.

python
stack = []
stack.append("A")     # push
stack.append("B")
stack.pop()           # "B": the most recent

A plain list or array works as a stack, as long as you add and remove at the end.

Where stacks appear

  • Undo. Each action is pushed. Undo pops the most recent one.
  • The back button. Pages you visit are pushed. Back pops.
  • Function calls. The call stack is one: the most recently called function is the first to return.
  • Matching brackets. Push each opening bracket, and pop when a closing one arrives. If they do not match, the code is wrong.
  • Depth-first search. See Graph Traversal.

Example

Checking brackets

Is ( [ ] { } ) balanced? Read left to right.

( push. [ push. ] matches the top [: pop. { push. } matches: pop. ) matches the remaining (: pop.

The stack is empty at the end, so it is balanced. In ( [ ) ], the ) arrives when the top is [. Mismatch.

Queue: first in, first out

A queue is a line at a shop. New people join at the back. The person at the front is served next. It is fair: nobody is overtaken.

  • Enqueue: add an item at the back.
  • Dequeue: take the item from the front.
python
from collections import deque

queue = deque()
queue.append("A")     # enqueue
queue.append("B")
queue.popleft()       # "A": the one that waited longest

Where queues appear

  • Work waiting to be done. Print jobs, emails to send, tasks for a thread pool.
  • Messages between systems. See Queues and Backpressure.
  • Breadth-first search, which explores nearest things first.
  • Anything where order of arrival should be respected.

Side by side

StackQueue
RuleLast in, first outFirst in, first out
AddAt the topAt the back
RemoveFrom the topFrom the front
PictureA pile of platesA line of people
Good forUndoing, backtracking, nestingFairness, processing in order

Two relatives

  • A deque (double-ended queue) allows adding and removing at both ends. It can act as either.
  • A priority queue ignores arrival order and always hands back the most important item. It is usually built with a heap.

Key takeaways

  • A stack returns the most recently added item: last in, first out.
  • A queue returns the item that has waited longest: first in, first out.
  • Both add and remove in one step, because they only ever touch the ends.
  • Stacks suit undo, nested structures and going deep. Queues suit fairness and going wide.
  • A plain array makes a good stack and a poor queue.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    6 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress