📚 Stacks & Queues

Two ways to organize what comes next

← Back to Algorithms

🥞 A Stack — Last In, First Out (LIFO)

A stack is like a pile of pancakes 🥞 or plates: you add to the top and remove from the top. The last item you put in is the first one to come out — LIFO.

You use stacks every day:

  • Undo (Ctrl+Z) — the most recent action is undone first.
  • The browser Back button.
  • The function call stack in recursion!
stack = [] stack.append("a") # push stack.append("b") stack.append("c") print(stack.pop()) # c (last in, first out) print(stack.pop()) # b

📌 In Python

A plain list is a stack: .append() to push, .pop() to remove the top.

🚶‍♂️🚶‍♀️ A Queue — First In, First Out (FIFO)

A queue is like a line at a store: the first person to arrive is the first served — FIFO. You add at the back and remove from the front.

Queues power printers (first document prints first), task schedulers, and breadth-first search (next lesson territory!).

from collections import deque queue = deque() queue.append("a") # enqueue (add at back) queue.append("b") queue.append("c") print(queue.popleft()) # a (first in, first out) print(queue.popleft()) # b

Why not just use list.pop(0)?

Removing from the front of a list is O(n) — Python has to shift every item. A deque (double-ended queue) does it in O(1). Use deque for queues!

📏 Quick comparison

Stack (LIFO)Queue (FIFO)
Addappend()append()
Removepop() (end)popleft() (front)
Real-worldUndo, Back buttonPrint line, ticket queue

✅ What you learned

  • Stack = LIFO. Push/pop from the same end. Use a list.
  • Queue = FIFO. Add at back, remove from front. Use deque.
  • Both add and remove in O(1) when used correctly.