Stacks and queues explained
The difference between a stack and a queue, what push, pop, enqueue and dequeue do, and what each structure is for. A robot runs the same five commands off each one, and the same map search runs off each one, in your browser: press Run and watch the order change.
A stack and a queue are the two simplest ways to hold things that are waiting. They hold the same items, they are built from the same array or list, and they differ in one rule only: which item you are allowed to take out next.
A stack gives you the item that went in last. A queue gives you the item that went in first. That one choice changes what a program does with them, and on this page you can watch it change what a robot does. Each demo below is a real program you can change and run.
The idea in one line
stack: last in, first out (LIFO)
queue: first in, first out (FIFO)
A stack has one end, called the top. You push an item on to the top, and you pop the top item off. A queue has two ends: items join the back and leave from the front. Putting one in is enqueue, taking one out is dequeue.
| Stack | Queue | |
|---|---|---|
| Add an item | push | enqueue |
| Take an item | pop, from the top | dequeue, from the front |
| Look without taking | peek | peek |
| The item you get | the newest | the oldest |
| Adding when there is no room | stack overflow | queue full |
| Taking from an empty one | stack underflow | queue empty |
Both are abstract data types: a list of operations and the rules they follow, with nothing said about how they are built. A Python list, an array with a pointer, and a chain of linked nodes can all be a stack, and the code that uses it cannot tell the difference.
The same five commands, off a queue
Here are five commands for the robot. They go into a queue in the order they are written, and come out of the front one at a time, in the order they went in. This is how a robot handles jobs that arrive while it is busy: a message from another robot, a button press, a line of a route.
The program
from bugbot import *
connect()
# change the commands and press Run
COMMANDS = [("forward", 25), ("turn right", 90), ("forward", 25),
("turn right", 90), ("forward", 15)]
START = (50, 20) # where the robot begins, in cm on the mat
def here():
# position() counts from the start, so add the start on
x, y = position()
return (START[0] + x, START[1] + y)
def do(name, amount):
if name == "forward":
forward(60, distance=amount)
elif name == "backward":
backward(60, distance=amount)
elif name == "turn right":
turn_right(40, angle=amount)
elif name == "turn left":
turn_left(40, angle=amount)
queue = []
for command in COMMANDS:
queue.append(command) # enqueue: join the back
print("joined the back:", command[0], command[1])
path = [here()]
while len(queue) > 0:
plot("commands waiting", len(queue))
name, amount = queue.pop(0) # dequeue: take from the front
print("off the front:", name, amount)
do(name, amount)
path.append(here())
draw("path", path, "blue", "line", 3)
plot("commands waiting", len(queue))
x, y = here()
print("finished at", round(x), round(y))
The blue line is where the robot went. pop(0) takes the item at the front of the list and shuffles everything else along one place, which is fine for five commands. A real program uses collections.deque instead, whose popleft() takes from the front without moving anything.
The same five commands, off a stack
Now change one character. pop() with no number takes from the end of the list, which is the top of a stack, so the last command pushed is the first one run.
The program
from bugbot import *
connect()
# change the commands and press Run
COMMANDS = [("forward", 25), ("turn right", 90), ("forward", 25),
("turn right", 90), ("forward", 15)]
START = (50, 20) # where the robot begins, in cm on the mat
def here():
# position() counts from the start, so add the start on
x, y = position()
return (START[0] + x, START[1] + y)
def do(name, amount):
if name == "forward":
forward(60, distance=amount)
elif name == "backward":
backward(60, distance=amount)
elif name == "turn right":
turn_right(40, angle=amount)
elif name == "turn left":
turn_left(40, angle=amount)
stack = []
for command in COMMANDS:
stack.append(command) # push: on to the top
print("pushed:", command[0], command[1])
path = [here()]
while len(stack) > 0:
plot("commands waiting", len(stack))
name, amount = stack.pop() # pop: take the top
print("popped:", name, amount)
do(name, amount)
path.append(here())
draw("path", path, "blue", "line", 3)
plot("commands waiting", len(stack))
x, y = here()
print("finished at", round(x), round(y))
Same five commands, same robot, same starting place. The queue finished at 75, 30 and the stack at 75, 10: both 25 cm to the right of the start, one 10 cm above it and one 10 cm below. The chart looks identical, because a chart of how many items are waiting cannot tell you which item comes next. Only the order out is different.
Reversing is what a stack is for. Push the moves a robot makes, pop them, and you get the way back. Push each open bracket in an expression and pop one at each closing bracket, and you find out whether the brackets match. Push a subroutine's return address before you call it, and pop it when the subroutine ends: that is the call stack, and it is why an error message prints the calls with the most recent one first.
Keeping things in order is what a queue is for. Jobs sent to a printer, keys typed before the program was ready for them, sensor readings waiting to be dealt with, and messages arriving over the radio all go into queues, so that nothing overtakes anything else and nothing waits for ever.
The same search, off a stack and off a queue
Here is the difference doing something bigger. The mat is a 5 by 5 grid of 20 cm cells with a ring of blocks in the middle. The robot is in the corner, the goal is the middle cell, and the only way in is a gap in the top of the ring.
The program searches for the goal. It keeps a list of cells it has found but not yet been to, and each time round the loop it takes one cell out of that list, looks at it, and adds any new neighbours. The list is the only thing that changes between the two demos. waiting.pop() makes it a stack, waiting.pop(0) makes it a queue, and everything else is the same.
On the mat, the blue squares are cells the search has reached, the small yellow squares are cells waiting in the list, and the red line joins the cells in the order they were reached.
The program
from bugbot import *
connect()
# change MODE and press Run
MODE = "stack" # "stack": take the newest "queue": take the oldest
BLOCKED = [(1, 1), (2, 1), (3, 1),
(1, 2), (3, 2),
(1, 3), (3, 3)]
START = (0, 0) # the robot's corner
GOAL = (2, 2) # the middle of the ring
STEPS = [(0, 1), (1, 0), (0, -1), (-1, 0)] # up, right, down, left
def cm(cell):
# the centre of a cell, in cm on the mat
return (10 + 20 * cell[0], 10 + 20 * cell[1])
def is_open(cell):
col, row = cell
if not (0 <= col <= 4 and 0 <= row <= 4):
return False
return cell not in BLOCKED
waiting = [START] # the cells found but not yet reached
reached = [] # the cells taken out, in order
came = {START: None} # each cell, and the cell it was found from
while len(waiting) > 0:
if MODE == "stack":
cell = waiting.pop() # the top: last in, first out
else:
cell = waiting.pop(0) # the front: first in, first out
reached.append(cell)
draw("reached", [cm(c) for c in reached], "blue", "squares", 16)
draw("order", [cm(c) for c in reached], "red", "line", 2)
draw("waiting", [cm(c) for c in waiting], "yellow", "squares", 8)
plot("cells waiting", len(waiting))
plot("cells reached", len(reached))
wait(0.4)
if cell == GOAL:
break
for dcol, drow in STEPS:
neighbour = (cell[0] + dcol, cell[1] + drow)
if is_open(neighbour) and neighbour not in came:
came[neighbour] = cell # found it: it joins the list
waiting.append(neighbour)
route = []
cell = GOAL
while cell is not None:
route.append(cm(cell))
cell = came[cell]
draw("route", route, "green", "line", 3)
print("cells reached:", len(reached))
print("route:", len(route) - 1, "steps")
Watch the yellow squares. The stack hands back the cell the search found most recently, which is nearly always the one next door, so the red line runs round the ring as one long snake: along the bottom, up the right side, back along the top and down the left. It jumps once, at the sixteenth cell, when the left side runs out and the newest cell left in the list is the gap into the middle, found back at the eleventh. The cell directly above the robot, the very first one found, is still waiting when the goal comes out, which is why the search reached 17 of the 18 open cells and not all 18.
Now the same program with MODE = "queue".
The program
from bugbot import *
connect()
# change MODE and press Run
MODE = "queue" # "stack": take the newest "queue": take the oldest
BLOCKED = [(1, 1), (2, 1), (3, 1),
(1, 2), (3, 2),
(1, 3), (3, 3)]
START = (0, 0) # the robot's corner
GOAL = (2, 2) # the middle of the ring
STEPS = [(0, 1), (1, 0), (0, -1), (-1, 0)] # up, right, down, left
def cm(cell):
# the centre of a cell, in cm on the mat
return (10 + 20 * cell[0], 10 + 20 * cell[1])
def is_open(cell):
col, row = cell
if not (0 <= col <= 4 and 0 <= row <= 4):
return False
return cell not in BLOCKED
waiting = [START] # the cells found but not yet reached
reached = [] # the cells taken out, in order
came = {START: None} # each cell, and the cell it was found from
while len(waiting) > 0:
if MODE == "stack":
cell = waiting.pop() # the top: last in, first out
else:
cell = waiting.pop(0) # the front: first in, first out
reached.append(cell)
draw("reached", [cm(c) for c in reached], "blue", "squares", 16)
draw("order", [cm(c) for c in reached], "red", "line", 2)
draw("waiting", [cm(c) for c in waiting], "yellow", "squares", 8)
plot("cells waiting", len(waiting))
plot("cells reached", len(reached))
wait(0.4)
if cell == GOAL:
break
for dcol, drow in STEPS:
neighbour = (cell[0] + dcol, cell[1] + drow)
if is_open(neighbour) and neighbour not in came:
came[neighbour] = cell # found it: it joins the list
waiting.append(neighbour)
route = []
cell = GOAL
while cell is not None:
route.append(cm(cell))
cell = came[cell]
draw("route", route, "green", "line", 3)
print("cells reached:", len(reached))
print("route:", len(route) - 1, "steps")
The queue hands out the cell that has been waiting longest, which is always the cell nearest the start, so the search works outwards in rings and goes both ways round at once. The red line jumps from one side of the mat to the other.
Look at the green route each one found. The queue's route is 8 steps, the shortest there is. The stack's is 12, the long way round, and it is 12 because that is simply the way the search happened to be facing when it arrived. Take the oldest cell first and every cell is first reached by the fewest steps; take the newest and no such promise holds.
That is the whole reason a search that needs the shortest route uses a queue. The search built on a stack is depth-first search and the one built on a queue is breadth-first search, and the BFS and DFS guide follows them out on to open ground, where the difference in how much each has to remember shows up as well. On this map, penned into a corridor, neither list ever holds more than 3 cells.
Building them without a list
Python's list does both jobs, but an exam wants the array version, with the ends tracked by hand.
A static stack is an array of a fixed size plus one integer, the top pointer, holding the index of the top item. An empty stack has top = -1.
push(item): if top = MAX - 1 then OUTPUT "stack overflow"
else top = top + 1
stack[top] = item
pop(): if top = -1 then OUTPUT "stack underflow"
else item = stack[top]
top = top - 1
RETURN item
Pop does not wipe anything. The old value stays in the array above the pointer, where it is no longer part of the stack and the next push will write over it.
A linear queue is an array with front and rear. It has a flaw: every dequeue moves front up, so the space at the start of the array is lost, and the queue can report itself full with most of the array empty. A circular queue fixes it by wrapping both pointers round with MOD:
enqueue(item): if count = MAX then OUTPUT "queue full"
else rear = (rear + 1) MOD MAX
queue[rear] = item
count = count + 1
dequeue(): if count = 0 then OUTPUT "queue empty"
else item = queue[front]
front = (front + 1) MOD MAX
count = count - 1
RETURN item
A third kind is the priority queue, where each item carries a priority and the one with the highest priority leaves first, however long the others have waited. It is what a robot uses when a "stop, something is in the way" message must overtake a queue of driving commands, and what turns breadth-first search into Dijkstra's algorithm.
In Python
stack = []
stack.append("a") # push
stack.append("b")
print(stack.pop()) # b: the newest
print(stack[-1]) # a: peek, without taking
from collections import deque
queue = deque()
queue.append("a") # enqueue, at the back
queue.append("b")
print(queue.popleft()) # a: the oldest
print(queue[0]) # a is gone, so this peeks at b
A Python list makes a good stack, because append and pop both work at the end and both are O(1). It makes a poor queue: pop(0) has to move every other item along one place, which is O(n). deque is a double-ended queue, and append, pop, appendleft and popleft are all O(1) on it. Both demos above use a plain list, because five commands and eighteen cells are too few for it to matter.
Where this is taught
- Abstract data types and stacks builds a static stack with a top pointer, and uses it to drive the robot home.
- Queues: linear, circular and priority builds all three kinds, and shows what the wrap in a circular queue is for.
- Stack frames and the call stack and Recursion are the stack the language keeps for you.
- Depth-first traversal and Breadth-first traversal are the two searches on this page, on graphs.
- Arrays, records and tuples and Linked lists are the structures a stack or a queue is built out of.
Questions
What is the difference between a stack and a queue?
The order in which items come out. A stack is last in, first out: the newest item is the one you get. A queue is first in, first out: the oldest item is the one you get. Everything else about them can be identical.
What does LIFO and FIFO mean?
LIFO is last in, first out, which is the stack rule: think of a pile of plates, where the plate you take is the one just put on. FIFO is first in, first out, which is the queue rule: think of a queue at a shop, where the person served is the one who has waited longest.
What are push, pop, enqueue and dequeue?
Push adds an item to the top of a stack, and pop takes the top item off and returns it. Enqueue adds an item to the back of a queue, and dequeue takes the item at the front off and returns it. Both structures usually also have peek, which returns the next item without removing it.
When should you use a stack instead of a queue?
Use a stack when the most recent thing matters most, or when you need to undo or reverse something: an undo list, a browser's back button, the return addresses of subroutine calls, matching brackets, backtracking out of a dead end. Use a queue when things must be dealt with fairly, in the order they arrived: printer jobs, keyboard presses, messages arriving over a radio link, and searches that must find the shortest route.
What is stack overflow and stack underflow?
Overflow is pushing on to a stack that has no room left, which can only happen to a stack of a fixed size. Underflow is popping from an empty stack. Both are errors the code has to check for, by comparing the top pointer with the size and with -1.
Why does a queue need a circular buffer?
A plain array queue moves its front pointer up on every dequeue, so the slots before the front are used up and never given back. Once the rear pointer reaches the end of the array, the queue calls itself full even though most of it is empty. Wrapping both pointers round with MOD lets the rear pointer carry on at slot 0 and reuse that space.
Is a stack or a queue faster?
Neither. Push, pop, enqueue and dequeue are all O(1): the time does not depend on how many items are in there. The one trap is using a Python list as a queue, because pop(0) moves every remaining item along one place, making it O(n). Use collections.deque for a queue.
Why does depth-first search use a stack and breadth-first search a queue?
A stack hands back the cell the search found most recently, which is a neighbour of the cell it has just looked at, so the search keeps going deeper along one path. A queue hands back the cell found longest ago, which is the nearest one to the start, so the search finishes everything one step away before anything two steps away. On this page the same program does both, and the only difference is pop() against pop(0).
Can a stack be made from a queue, or a queue from a stack?
Yes, and it is a classic exercise. Two queues can behave as a stack, and two stacks can behave as a queue, by moving the items across from one to the other so that the ends swap over. It is slower than using the right structure in the first place, which is the point of the exercise.
Are stacks and queues on the A level Computer Science specification?
Yes, on all the main boards, and they are not on GCSE. AQA's A level (7517) covers stacks and queues, linear, circular and priority queues, and their operations (4.2.1.4, 4.2.2.1, 4.2.3.1). OCR's H446 asks you to create, traverse, add to and remove from stacks and queues (1.4.2). Eduqas covers both in its data structures section (1.1).
Learn it step by step
These lessons build the same ideas one at a time, each with tasks the simulator marks.
- A3.2 Abstract data types and stacks Data structures, A level
- A3.3 Queues: linear, circular and priority Data structures, A level
- A3.1 Arrays, records and tuples Data structures, A level
- A3.4 Linked lists Data structures, A level
- A2.1 Stack frames and the call stack Recursion and computational thinking, A level
- A2.2 Recursion Recursion and computational thinking, A level
- A4.3 Depth-first traversal Trees and graphs, A level
- A4.4 Breadth-first traversal Trees and graphs, A level