Programming Concepts

Foundational Data Structures~20 min

Stacks and Queues

A stack always serves the most recent item first; a queue always serves the oldest — the same list, used two opposite ways.

By the end of this lesson, you can

  • Explain what makes a stack last-in-first-out and a queue first-in-first-out
  • Implement a stack and a queue using a Python list, and trace how items enter and leave each
  • Choose between a stack and a queue based on which processing order a problem needs

Why it matters

An “undo” button and a customer service line both process a sequence of items one at a time — but in opposite orders. Undo reverses the most recent action; the line serves whoever has been waiting longest. Both can be built from the same Python list — the only difference is which end you remove from.

Mental model

  • A stack is last-in, first-out (LIFO): whatever was added most recently comes off first. Think of a stack of plates — you take from the top, the same place you added to.
  • A queue is first-in, first-out (FIFO): whatever was added earliest comes off first. Think of a line of people — the front of the line leaves first, regardless of how recently anyone joined the back.

A Python list can act as either, depending only on which end pop() removes from.

PythonA stack: undo history
history = []
history.append("open file")
history.append("edit line 3")
history.append("save file")

print(history.pop())
print(history.pop())
Output
save file
edit line 3

pop() with no argument removes from the end of the list — the most recently added item — undoing the most recent action first, then the one before it.

PythonA queue: a customer service line
line = []
line.append("Ada")
line.append("Grace")
line.append("Linus")

print(line.pop(0))
print(line.pop(0))
Output
Ada
Grace

pop(0) removes from the front of the list — whoever has been waiting longest — regardless of who joined most recently.

Trace it

The same three names, served in opposite orders
Structure1st removed2nd removed3rd removed
Stack (pop())Linus (most recent)GraceAda (oldest)
Queue (pop(0))Ada (oldest)GraceLinus (most recent)

Same three names, added in the same order — completely reversed removal order, depending entirely on which end is used.

Check your understanding

What does this print? plates = [] plates.append("blue") plates.append("red") plates.append("green") print(plates.pop())
Or reveal the answer without checking

Answer:"green"
plates.pop() with no argument removes from the end — "green" was the most recently added, so it comes off first, matching LIFO order.

A print job scheduler needs to print documents in the order they were submitted. Which structure fits?
Or reveal the answer without checking

Answer:A queue, using pop(0)
Printing documents in submission order means the earliest-submitted document goes first — first in, first out, which is exactly what a queue models.

Practice: warm-up

Trace this program — write down what each pop() call removes and returns, in order.

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop())
print(stack.pop())
print(stack.pop())

Stuck? Reveal one hint at a time.

  1. Hint 1

    Each pop() with no argument removes from the end of the list — the most recently added remaining item.

  2. Hint 2

    After the first pop() removes 3, what's now at the end of the list for the second pop() to remove?

Reveal the trace

Try the problem yourself before reading this. There is often more than one reasonable approach — treat this as one worked example, not the only correct answer.

stack after appends: [1, 2, 3]
pop() #1 -> removes and returns 3   (stack now [1, 2])
pop() #2 -> removes and returns 2   (stack now [1])
pop() #3 -> removes and returns 1   (stack now [])

Practice: apply it

This code is meant to serve support tickets in the order they were submitted, oldest first:

tickets = []
tickets.append("ticket A")
tickets.append("ticket B")
tickets.append("ticket C")

next_ticket = tickets.pop()
print(next_ticket)
What does this actually print, and is that correct for 'oldest first'?
Or reveal the answer without checking

Answer:"ticket C" — incorrect, since ticket A was submitted first and should be served first
tickets.pop() removes from the end (LIFO), returning the most recently added ticket, C — the opposite of 'oldest first,' which needs a queue's pop(0) instead.

Modification challenge: fix this by changing tickets.pop() to tickets.pop(0), so tickets are served in the order they were submitted.

Summary

  • A stack is last-in-first-out: the most recently added item is removed first. A Python list acts as one using append() and pop().
  • A queue is first-in-first-out: the earliest added item is removed first. A Python list acts as one using append() and pop(0).
  • Mixing up pop() and pop(0) doesn’t raise an error — it silently serves items in the wrong order, a logic error rather than a crash.
  • Choose based on the order the problem needs: “most recent first” is a stack; “oldest first” is a queue.

Key terms