Stacks and Queues

Stacks and queues are abstract data types that restrict how you access elements. A stack is LIFO (Last In, First Out). A queue is FIFO (First In, First Out).

Why It Matters

Stacks power function calls, undo systems, expression parsing, and DFS. Queues power BFS, task scheduling, and message queues. They appear everywhere.

Stack (LIFO)

Think of a stack of plates — you add and remove from the top only.

Operation	Time
push(item)	O(1)
pop()	O(1)
peek()	O(1)
is_empty()	O(1)

class Stack:
    def __init__(self):
        self._items = []
 
    def push(self, val):
        self._items.append(val)
 
    def pop(self):
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()
 
    def peek(self):
        if not self._items:
            raise IndexError("peek at empty stack")
        return self._items[-1]
 
    def is_empty(self):
        return len(self._items) == 0
 
# Classic problem: balanced parentheses
def is_valid_parens(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return len(stack) == 0
 
assert is_valid_parens("({[]})") == True
assert is_valid_parens("([)]") == False

Queue (FIFO)

Think of a line at a store — first person in line is first served.

Operation	Time
enqueue(item)	O(1)
dequeue()	O(1)
peek()	O(1)

from collections import deque
 
class Queue:
    def __init__(self):
        self._items = deque()
 
    def enqueue(self, val):
        self._items.append(val)
 
    def dequeue(self):
        if not self._items:
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()  # O(1) with deque
 
    def peek(self):
        if not self._items:
            raise IndexError("peek at empty queue")
        return self._items[0]
 
    def is_empty(self):
        return len(self._items) == 0

Variants

Variant	Description
Deque (double-ended queue)	O(1) push/pop from both ends
Priority Queue	Dequeue by priority, not order. See Heaps
Circular Buffer	Fixed-size queue that wraps around

Where They’re Used

• Stack: function call stack, undo/redo, browser back button, parsing expressions
• Queue: BFS traversal, print spooling, task scheduling, rate limiting buffers
• Deque: sliding window problems, work-stealing schedulers

Related

• Arrays — underlying storage for stack
• Linked Lists — alternative underlying storage
• Heaps — priority queue implementation
• BFS and DFS — BFS uses a queue, DFS uses a stack