Stacks and Queues — LIFO, FIFO, and Why They Matter
stacksqueuesdata-structuresbeginnerfree
The two simplest abstract data structures — stacks (last in, first out) and queues (first in, first out) — and the algorithms they power.
Stacks and Queues
Stacks and queues are abstract data types — they define what operations are allowed, not how the data is stored. Both restrict access to elements in a specific way, and that restriction is what makes them powerful.
A stack is last-in, first-out (LIFO). Think of a pile of plates — you add to the top and take from the top.
A queue is first-in, first-out (FIFO). Think of a line at a shop — the first person in line is served first.
Stacks (LIFO)
Operations: push (add to top), pop (remove from top), peek (look at top without removing).
All three are O(1). That’s it — stacks are beautifully simple.
Where Stacks Appear
- Function call stack — every recursive call pushes a frame, every return pops one
- Undo/redo — each action is pushed onto a stack; undo pops the last action
- Browser back button — each page visit is pushed; back pops the last page
- DFS — depth-first search uses a stack (explicitly or via recursion)
- Expression parsing — balanced parentheses, postfix evaluation
python
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if self.is_empty():
return None
return self.items.pop()
def peek(self):
if self.is_empty():
return None
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
s = Stack()
for x in [10, 20, 30]:
s.push(x)
print(f"Push {x} -> top is {s.peek()}")
while not s.is_empty():
print(f"Pop -> {s.pop()}")Queues (FIFO)
Operations: enqueue (add to back), dequeue (remove from front), peek (look at front).
Where Queues Appear
- BFS — breadth-first search uses a queue
- Task scheduling — OS process queues, print queues, message queues
- Rate limiting — sliding window of request timestamps
python
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if self.is_empty():
return None
return self.items.popleft()
def peek(self):
if self.is_empty():
return None
return self.items[0]
def is_empty(self):
return len(self.items) == 0
q = Queue()
for x in ["A", "B", "C"]:
q.enqueue(x)
print(f"Enqueue {x} -> front is {q.peek()}")
while not q.is_empty():
print(f"Dequeue -> {q.dequeue()}")Stack vs Queue operations
| Operation | Stack | Queue |
|---|---|---|
| Add | push() - O(1) | enqueue() - O(1) |
| Remove | pop() - O(1) | dequeue() - O(1) |
| Peek | O(1) - top | O(1) - front |
| Order | LIFO | FIFO |
| Key use | DFS, undo, parsing | BFS, scheduling, buffering |
Key Takeaways
- Stacks are LIFO. Push and pop from the same end. Powers DFS, undo, and recursion.
- Queues are FIFO. Enqueue at back, dequeue from front. Powers BFS and scheduling.
- All core operations are O(1) with the right backing structure.
- Use Python’s
listfor stacks,collections.dequefor queues. - These two structures are the foundation for BFS and DFS — the graph algorithms lesson builds directly on this.