Stacks and Queues in DSA

A stack and a queue are the simplest data structures with names. They each give you one place to put things in and one place to take things out — but the order in which items come back is different, and that single difference is enough to power undo systems, expression parsers, breadth-first search, browser history, job runners, and a long list of other things. This post covers the discipline behind each, the Python tools that implement them, and how to roll your own when you need to.

A stack is LIFO

A stack is last-in, first-out. The most recent item pushed is the next item popped. Think of a stack of plates — you take from the top, you put on the top, and the plate at the bottom only sees the light of day after every plate above it is gone.

The two operations are push and pop. A read-only peek at the top is peek.

push(1):       push(2):       push(3):       pop() = 3:     pop() = 2:
┌───┐

│ 3 │ ◄ top

├───┤          ┌───┐

┌───┐           │ 2 │          │ 2 │ ◄ top

│ 2 │ ◄ top     ├───┤          ├───┤          ┌───┐

┌───┐         ├───┤           │ 1 │          │ 1 │          │ 1 │ ◄ top

│ 1 │ ◄ top   │ 1 │           └───┘          └───┘          └───┘

└───┘         └───┘

A queue is FIFO

A queue is first-in, first-out. The first item enqueued is the first item dequeued. Think of a line at a coffee shop — the person who has waited longest is served first.

The two operations are enqueue (add at the back) and dequeue (remove from the front).

enqueue(1):     enqueue(2):     enqueue(3):     dequeue() = 1:
front ► ┌───┐    front ► ┌───┬───┐    front ► ┌───┬───┬───┐    front ► ┌───┬───┐
│ 1 │            │ 1 │ 2 │            │ 1 │ 2 │ 3 │            │ 2 │ 3 │
└───┘            └───┴───┘            └───┴───┴───┘            └───┴───┘
◄ back              ◄ back               ◄ back                ◄ back

The discipline is what makes the structure useful. A stack guarantees that whatever you put on most recently is what comes off — so it naturally models “undo,” “function call return,” and “depth-first.” A queue guarantees fair ordering — so it naturally models “job processing,” “BFS traversal,” and “messaging.”

A Python list as a stack

The built-in list already supports stack operations efficiently:

stack = []
stack.append(1)    # push
stack.append(2)
stack.append(3)
print(stack)       # [1, 2, 3]

top = stack.pop()  # pop → 3
print(top)         # 3
print(stack)       # [1, 2]

print(stack[-1])   # peek → 2

list.append and list.pop are both O(1) amortised. The end of the list is the top of the stack. Don’t use pop(0) — that pops from the front and is O(n).

A wrapper class makes intent clear at the call site:

class Stack:
    def __init__(self):
        self._items = []

    def push(self, x):
        self._items.append(x)

    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 from empty stack")
        return self._items[-1]

    def __len__(self):
        return len(self._items)

    def __bool__(self):
        return bool(self._items)

s = Stack()
for ch in "hello":
    s.push(ch)
out = []
while s:
    out.append(s.pop())
print("".join(out))    # olleh

That’s a one-line string reverser — and a good demonstration of why stacks “naturally” undo things.

A Python list as a queue — don’t

You can enqueue with list.append and dequeue with list.pop(0). But pop(0) shifts every remaining element down by one slot, making it O(n). For a large queue this is catastrophic.

The right tool is collections.deque — a double-ended queue with O(1) operations at both ends.

from collections import deque

q = deque()
q.append(1)        # enqueue at back
q.append(2)
q.append(3)
print(q)           # deque([1, 2, 3])

front = q.popleft()  # dequeue from front → 1
print(front)         # 1
print(q)             # deque([2, 3])

A small wrapper:

from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()

    def enqueue(self, x):
        self._items.append(x)

    def dequeue(self):
        if not self._items:
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()

    def peek(self):
        if not self._items:
            raise IndexError("peek from empty queue")
        return self._items[0]

    def __len__(self):
        return len(self._items)

    def __bool__(self):
        return bool(self._items)

q = Queue()
for x in [10, 20, 30]:
    q.enqueue(x)
while q:
    print(q.dequeue(), end=" ")    # 10 20 30

Building them on a linked list

If you want to see how it works under the hood — or you’re in an interview that forbids built-ins — you can build both structures on a singly linked list. We covered the Node class in the linked lists intro.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class LinkedStack:
    def __init__(self):
        self.head = None
        self.size = 0

    def push(self, x):
        self.head = Node(x, next=self.head)
        self.size += 1

    def pop(self):
        if self.head is None:
            raise IndexError("pop from empty stack")
        x = self.head.value
        self.head = self.head.next
        self.size -= 1
        return x

    def peek(self):
        if self.head is None:
            raise IndexError("peek from empty stack")
        return self.head.value

The head of the list is the top of the stack — both operations are O(1).

For a queue, you need both a head (front) and a tail (back):

class LinkedQueue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def enqueue(self, x):
        node = Node(x)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1

    def dequeue(self):
        if self.head is None:
            raise IndexError("dequeue from empty queue")
        x = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return x

Enqueue appends at the tail; dequeue pops from the head. Both O(1).

Where stacks show up

• Function calls. The call stack we drew in the recursion post is a real stack. Each call’s frame is pushed; each return pops it.
• Undo systems. Each action is pushed; “undo” pops the most recent one.
• Expression parsing. Matching () [] {} is a classic stack problem — push openers, pop on closers, fail if there’s a mismatch.
• Depth-first search. A stack of frontier nodes implements DFS iteratively.
• Backtracking. Saving state to “rewind to” is a stack of choices.

Where queues show up

• Breadth-first search. A queue of frontier nodes guarantees we explore level by level.
• Task/job runners. Producer enqueues work; worker dequeues and processes it.
• Print spoolers, request handling, message brokers. Anything where “first come, first served” is the right policy.
• Streaming buffers. Audio/video frames flow through a queue between producer and consumer.

Bounded variants

Real systems often need a bounded queue — accept at most N items, block or drop on overflow. collections.deque supports this with maxlen:

from collections import deque

q = deque(maxlen=3)
q.append(1)
q.append(2)
q.append(3)
q.append(4)    # 1 is silently dropped from the front
print(q)       # deque([2, 3, 4], maxlen=3)

That’s not the right behaviour for every application — sometimes you want to refuse, not drop — but it’s a useful primitive.

A worked example — breadth-first traversal

A queue gives you BFS for free. Given a graph as an adjacency dictionary:

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

def bfs(start):
    visited = {start}
    q = deque([start])
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)
                q.append(nbr)
    return order

print(bfs("A"))    # ['A', 'B', 'C', 'D', 'E', 'F']

Swap the queue for a stack (q.pop() instead of q.popleft()) and you have DFS. Same skeleton, different discipline, different behaviour.

Practice problems

Solve each before reading the solution.

1. Reverse a string with a stack

def reverse(s):
    stack = list(s)
    out = []
    while stack:
        out.append(stack.pop())
    return "".join(out)

print(reverse("hello"))    # olleh

2. Check if a string of brackets is balanced

def balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in "([{":
            stack.append(c)
        elif c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
    return not stack

print(balanced("({[]})"))    # True
print(balanced("({[})"))     # False

3. First non-repeating character in a stream

A queue of characters plus a count map:

from collections import deque

def first_unique_streamer():
    q = deque()
    count = {}
    def feed(c):
        count[c] = count.get(c, 0) + 1
        q.append(c)
        while q and count[q[0]] > 1:
            q.popleft()
        return q[0] if q else None
    return feed

feed = first_unique_streamer()
for c in "aabc":
    print(feed(c), end=" ")    # a b b b

4. Implement two stacks in one list

Grow one from the left, the other from the right:

class TwoStacks:
    def __init__(self, size):
        self.arr = [None] * size
        self.left = -1
        self.right = size

    def push1(self, x):
        self.left += 1
        if self.left >= self.right:
            raise OverflowError
        self.arr[self.left] = x

    def push2(self, x):
        self.right -= 1
        if self.right <= self.left:
            raise OverflowError
        self.arr[self.right] = x

    def pop1(self):
        x = self.arr[self.left]; self.left -= 1; return x

    def pop2(self):
        x = self.arr[self.right]; self.right += 1; return x

5. Hot-potato simulation with a queue

from collections import deque

def hot_potato(names, k):
    q = deque(names)
    while len(q) > 1:
        for _ in range(k):
            q.append(q.popleft())
        q.popleft()
    return q[0]

print(hot_potato(["A", "B", "C", "D", "E"], 3))    # winner

Rotate k players to the back, eliminate the next one, repeat.

6. Max in a stack in O(1)

Track a parallel stack of “max so far”:

class MaxStack:
    def __init__(self):
        self.s = []
        self.maxes = []
    def push(self, x):
        self.s.append(x)
        if not self.maxes or x >= self.maxes[-1]:
            self.maxes.append(x)
        else:
            self.maxes.append(self.maxes[-1])
    def pop(self):
        self.maxes.pop()
        return self.s.pop()
    def max(self):
        return self.maxes[-1]

We will see this same idea in the “Min Stack” practice problem next.

Recap

You now know:

• A stack is LIFO; a queue is FIFO
• Python list is a great stack — append and pop are O(1)
• collections.deque is the right queue — append and popleft are O(1)
• Don’t use list.pop(0) for a queue — it’s O(n)
• Both structures cost the same to build on a linked list (head for stack, head+tail for queue)
• Stacks back DFS, undo, parsing; queues back BFS, job runners, fair ordering

Next steps

Time to put both to work. The next post walks through eight classic stack/queue interview problems — valid parentheses, daily temperatures, sliding window max, monotonic stack tricks, and queue/stack implementations of each other.

→ Next: Stacks & Queues: 8 Practice Problems with Solutions

Questions or feedback? Email codeloomdevv@gmail.com.