programmingconcepts

§ 2.2 · Data structures

Stacks and queues

Two ways to hold items in order: a stack gives back the newest item first, a queue the oldest.

A stack and a queue both hold items in the order they arrive; they differ in which end you take from. A stack is last in, first out: push and pop at the top, like plates. A queue is first in, first out: join at the back, leave from the front, like a line. All four operations take O(1).

Push and pop
O(1)
Enqueue and dequeue
O(1) with a deque
Stack order
Last in, first out
Queue order
First in, first out
Requires
Arrays
from collections import deque

stack = []
queue = deque()


def add(x):
    stack.append(x)
    queue.append(x)


def remove():
    from_stack = stack.pop()
    from_queue = queue.popleft()
    return from_stack, from_queue

Add the same values to a stack and a queue, then take some out. Watch which value each one gives back.

step 0 / 0just addednext to leave

Fig. 2.2. The same values go into both. Orange is the item just added; the outlined item is the one that will leave next. Compare the "gave" counters at the end.

Intuition

A stack is a pile of plates: you put clean plates on top and take from the top, so the last plate added is the first used. A queue is a line at a shop: people join at the back and are served from the front, so the first to arrive is the first to leave.

Both hold items in the order they arrived. The only difference is which end you take from.

How it works

Operation Stack Queue
Add push: put on top enqueue: join at the back
Remove pop: take from the top dequeue: leave from the front
Look without removing peek the top peek the front
Order out Last in, first out (LIFO) First in, first out (FIFO)

A stack fits neatly on a dynamic array: push and pop both work at the end, which costs O(1). A queue needs both ends. Removing from the front of an array shifts everything, O(n), so real queues use a deque (a ring buffer or linked blocks) where both ends are O(1).

Common mistakes

  1. Using an array’s front as a queue. list.pop(0) in Python and shift() in JavaScript are O(n). On large queues, use collections.deque or a ring buffer.
  2. Popping an empty stack. Check the size first; the error (or undefined, or a panic) depends on the language.
  3. Picking the wrong one. If the newest work matters most (undo, nested calls, depth-first search), you want a stack. If fairness or arrival order matters (tasks, breadth-first search), you want a queue.

In other languages

Language Stack Queue
Python list (append, pop) collections.deque (append, popleft)
JavaScript Array (push, pop) None built in; Array works for small queues
Java ArrayDeque (push, pop) ArrayDeque (offer, poll)
C Write your own Write your own
Go Slice (append, reslice) Slice, or container/list
Rust Vec (push, pop) VecDeque (push_back, pop_front)

Try it yourself

Push and pop your own values:

step 1 / 1changingtop

Now the same with a queue. Notice which value each one gives back:

step 1 / 1changingfront

Check yourself

Check yourself

Push 1, 2 and 3 onto a stack, then pop twice. What is left?

Check yourself

Enqueue 1, 2 and 3, then dequeue once. What is now at the front?

Sources

  • Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 10.1, “Stacks and queues” (3rd edition).

Newsletter

One new concept each week, by email.

Signup opens soon.