Stacks and queues are the two simplest ways to line up data, and once you can see them you start noticing them everywhere: the browser back button, the undo key, the print jobs waiting on a shared printer. This post builds both from Python’s standard library, wires up a linked list by hand so you understand what a “pointer” really is, and then puts them to work on the exact problems interviewers love to ask.

“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.”

Linus Torvalds, on the Git mailing list

Last Updated: July 2026 | Tested on: Python 3.14.6 | Difficulty: Intermediate | Reading Time: 20 minutes

Here is the everyday version. A stack is a pile of plates: you add to the top and you take from the top, so the last plate on is the first one off. That is called LIFO, last in first out. A queue is the line at a canteen counter: the first person to arrive is the first one served, which is FIFO, first in first out. That single difference in which end you touch is the whole personality of each structure, and choosing the right one (and the right Python type to back it) is the difference between code that stays fast and code that quietly crawls as your data grows.

A linked list is the third character in this story. Instead of storing items in one solid block like a Python list, it strings together little boxes where each box holds a value and a pointer to the next box. It is the structure that makes insertions and deletions cheap in the middle, and understanding it is what finally makes “pointers” click for people coming from higher-level languages.

Tip: click the diagram to open it full screen, then use the zoom and pan controls for a closer look.

The diagram above is the mental model for the whole post: a stack works entirely at the top, a queue adds at one end and serves at the other, and a linked list insertion is a small piece of pointer surgery where you rewire two links to splice a node into place. Keep it nearby as we build each one in code.

Two Ways to Line Up Data: Stacks and Queues

A plain Python list is already a perfect stack. You append() to push onto the top and pop() to take from the top, and both operations are O(1) because they touch the end of the list where there is always room. A queue looks almost the same, but there is a trap: if you use a list and call pop(0) to serve from the front, Python has to shift every remaining element one slot to the left, which is O(n). The fix is collections.deque, a double-ended queue built exactly for cheap adds and removes at both ends. Let’s see all three in action and then measure the trap.

📄 queues.py: a list as a stack, a deque as a queue, and why list-as-queue is slow

from collections import deque
import timeit

# --- Stack: a list is already a perfect stack ---
stack = []
stack.append("draft")     # push
stack.append("review")
stack.append("publish")
print("stack after pushes:", stack)
print("pop:", stack.pop())   # last in, first out
print("stack now:", stack)

# --- Queue: use deque, not a list ---
queue = deque()
queue.append("Anvi")      # enqueue at the back
queue.append("Aditi")
queue.append("Aviraj")
print("queue:", list(queue))
print("serve:", queue.popleft())   # first in, first out
print("queue now:", list(queue))

# --- Why a list is a bad queue: pop(0) is O(n) ---
print()
print(f"{'n':>9} | {'list.pop(0)':>14} | {'deque.popleft':>15}")
print("-" * 44)
for n in [10_000, 20_000, 40_000, 80_000]:
    list_setup = f"data=list(range({n}))"
    t_list = timeit.timeit("data.pop(0)", setup=list_setup, number=n) / n
    dq_setup = f"from collections import deque; data=deque(range({n}))"
    t_dq = timeit.timeit("data.popleft()", setup=dq_setup, number=n) / n
    print(f"{n:>9,} | {t_list*1e9:>12.1f}ns | {t_dq*1e9:>13.1f}ns")

▶ Output

stack after pushes: ['draft', 'review', 'publish']
pop: publish
stack now: ['draft', 'review']
queue: ['Anvi', 'Aditi', 'Aviraj']
serve: Anvi
queue now: ['Aditi', 'Aviraj']

        n |    list.pop(0) |   deque.popleft
--------------------------------------------
   10,000 |        627.0ns |          33.4ns
   20,000 |       1237.7ns |          33.3ns
   40,000 |       3228.8ns |          33.5ns
   80,000 |       7667.4ns |          35.4ns

What happened here: The stack behaves exactly like a pile of plates: publish went on last and came off first. The deque queue behaves like the canteen line: Anvi arrived first and was served first. The measurement is the part worth staring at. When the list has 10,000 items, serving from the front with pop(0) costs about 627 nanoseconds; double the list and it roughly doubles, then doubles again, climbing to 7,667 nanoseconds at 80,000 items. That steady doubling is the fingerprint of O(n).

The deque.popleft() column, meanwhile, sits flat at around 33 nanoseconds no matter how big the queue gets. That flat line is why the rule is simple: if you need a queue, reach for deque, never a list.

Building a Linked List From Scratch

You will almost never build a linked list for real work in Python, because the built-in list and deque already cover the ground. But building one by hand is the clearest way to understand pointers, and it ties directly back to the classes and objects you learned earlier in this series. Think of a treasure hunt where each clue tells you where the next clue is hidden. The clue is a Node: it holds a value and a reference to the next node. Follow the references from the first clue (the head) and you visit every value in order. Here is the whole thing, with the three operations that matter: insert, delete, and traverse.

📄 linked_list.py: a Node class plus insert, delete, and traverse

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt          # a pointer to the next node, or None at the end

class LinkedList:
    def __init__(self):
        self.head = None

    def push_front(self, value):
        # New node points at the old head, then becomes the head. O(1).
        self.head = Node(value, self.head)

    def insert_after(self, target, value):
        node = self.head
        while node and node.value != target:
            node = node.next
        if node is None:
            raise ValueError(f"{target!r} not found")
        # Splice the new node between node and node.next
        node.next = Node(value, node.next)

    def delete(self, target):
        prev, node = None, self.head
        while node and node.value != target:
            prev, node = node, node.next
        if node is None:
            return False
        if prev is None:            # deleting the head
            self.head = node.next
        else:                       # skip over the deleted node
            prev.next = node.next
        return True

    def __iter__(self):
        node = self.head
        while node:
            yield node.value
            node = node.next

    def __repr__(self):
        return " -> ".join(str(v) for v in self) or "(empty)"

menu = LinkedList()
menu.push_front("paneer")
menu.push_front("dal")
menu.push_front("rice")          # rice is now the head
print("after pushes: ", menu)

menu.insert_after("dal", "roti") # splice roti in the middle
print("after insert: ", menu)

menu.delete("dal")               # remove a middle node
print("after delete: ", menu)

menu.delete("rice")              # remove the head
print("after head del:", menu)

print("traverse:     ", list(menu))

▶ Output

after pushes:  rice -> dal -> paneer
after insert:  rice -> dal -> roti -> paneer
after delete:  rice -> roti -> paneer
after head del: roti -> paneer
traverse:      ['roti', 'paneer']

What happened here: Every operation is just pointer rewiring, which is the pointer surgery from the diagram. push_front makes a new node whose next is the old head, then names it the new head, so three pushes leave rice at the front. insert_after("dal", "roti") walks to the dal node and sets its next to a fresh node that points at whatever came after (paneer), splicing roti in without moving anything else.

Deleting is the mirror image: to remove dal we make its previous node point past it to roti, and to remove the head we simply move head forward one node. Nothing shifts in memory the way a Python list would; you only ever change a couple of links. That is the superpower of a linked list, and also its weakness, because to reach the middle you must walk from the head every time, which is O(n).

Classic Problems That Are Really Stacks and Queues

Once you can see stacks and queues, a whole category of problems turns easy. Three of them show up constantly: checking that brackets are balanced (a stack), building undo for an editor (a stack), and exploring a graph one level at a time with breadth-first search, or BFS (a queue). Think of the bracket checker like matching parentheses in a math worksheet: every time you open one you owe a close, and the most recent opener must be closed first, which is precisely LIFO behavior. Here are all three, short and runnable.

📄 classic.py: balanced brackets, an undo stack, and a BFS frontier

from collections import deque

# --- 1. Balanced brackets: the classic stack problem ---
def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)            # push every opener
        elif ch in ")]}":
            if not stack or stack.pop() != pairs[ch]:
                return False            # wrong or missing partner
    return not stack                    # leftover openers = unbalanced

tests = ["()[]{}", "([{}])", "(]", "((())", "a[b(c)d]e"]
for t in tests:
    print(f"{t!r:>12} -> {is_balanced(t)}")

print()

# --- 2. Undo stack: every editor is a stack under the hood ---
class Editor:
    def __init__(self):
        self.text = ""
        self.history = []               # stack of previous states

    def type(self, s):
        self.history.append(self.text)  # snapshot before changing
        self.text += s

    def undo(self):
        if self.history:
            self.text = self.history.pop()

ed = Editor()
ed.type("hello")
ed.type(" world")
print("typed:", repr(ed.text))
ed.undo()
print("undo :", repr(ed.text))
ed.undo()
print("undo :", repr(ed.text))

print()

# --- 3. BFS frontier: a queue explores a graph level by level ---
graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [], "E": ["F"], "F": [],
}

def bfs(start):
    seen = {start}
    frontier = deque([start])           # the queue of nodes to visit
    order = []
    while frontier:
        node = frontier.popleft()       # FIFO: nearest node first
        order.append(node)
        for nbr in graph[node]:
            if nbr not in seen:
                seen.add(nbr)
                frontier.append(nbr)    # explore it later
    return order

print("BFS order:", bfs("A"))

▶ Output

    '()[]{}' -> True
    '([{}])' -> True
        '(]' -> False
     '((())' -> False
 'a[b(c)d]e' -> True

typed: 'hello world'
undo : 'hello'
undo : ''

BFS order: ['A', 'B', 'C', 'D', 'E', 'F']

What happened here: The bracket checker pushes every opener and, on each closer, pops the top and checks it is the matching partner. '([{}])' passes because the closers arrive in exactly reverse order of the openers, while '(]' fails on a mismatch and '((())' fails because an opener is left on the stack at the end. The undo editor keeps a stack of past text snapshots; each keystroke pushes the old state, and each undo pops back to it, so two undos peel hello world back to hello and then to empty.

The BFS uses a deque as its frontier: it serves the nearest unvisited node first, which is why the walk comes out A, then B and C (one hop away), then D, E, and F. Swap that popleft() for a pop() and the same code becomes depth-first search. Same structure, different end.

An LRU Cache, Two Ways

An LRU (least recently used) cache is a box that holds a fixed number of items and, when it fills up, throws out whatever was touched longest ago to make room. Picture a small fridge shelf: when it is full and you buy something new, the item pushed to the back that nobody has reached for gets tossed. This is one of the most useful structures in real systems, and Python gives you two clean ways to build it. The hand-rolled version uses OrderedDict, which remembers order and lets you move a key to the “most recent” end in O(1). The zero-effort version is the functools.lru_cache decorator, which turns any pure function into a cached one.

📄 lru.py: a hand-built LRU with OrderedDict, then functools.lru_cache

from collections import OrderedDict
from functools import lru_cache

# --- Hand-built LRU cache with OrderedDict ---
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.store = OrderedDict()      # remembers insertion / use order

    def get(self, key):
        if key not in self.store:
            return None
        self.store.move_to_end(key)     # mark as most recently used
        return self.store[key]

    def put(self, key, value):
        if key in self.store:
            self.store.move_to_end(key)
        self.store[key] = value
        if len(self.store) > self.capacity:
            evicted, _ = self.store.popitem(last=False)  # drop oldest
            print(f"  evicted {evicted!r}")

cache = LRUCache(capacity=2)
cache.put("a", 1)
cache.put("b", 2)
print("get a:", cache.get("a"))     # touch 'a' so 'b' is now oldest
cache.put("c", 3)                   # over capacity -> evicts 'b'
print("get b:", cache.get("b"))     # gone
print("keys :", list(cache.store))

print()

# --- The batteries-included version: functools.lru_cache ---
@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print("fib(50):", fib(50))
print("stats  :", fib.cache_info())

▶ Output

get a: 1
  evicted 'b'
get b: None
keys : ['a', 'c']

fib(50): 12586269025
stats  : CacheInfo(hits=48, misses=51, maxsize=None, currsize=51)

What happened here: In the hand-built cache, capacity is 2. We store a and b, then read a, which calls move_to_end and marks a as freshly used, leaving b as the oldest. Adding c pushes us over capacity, so popitem(last=False) evicts the oldest key, b, exactly as the printout shows. Asking for b afterward returns None. The second half is the shortcut you will actually use day to day: decorating fib with @lru_cache stores each result the first time it is computed, so the famously slow recursive Fibonacci finishes instantly.

The cache_info() line proves it, 48 hits against 51 misses, meaning almost half the calls were served straight from the cache instead of recomputed. When you need real caching, prefer the built-in decorator; build the OrderedDict version only when you need custom eviction rules.

Interview Drills: Reverse, Detect a Cycle, Queue From Stacks

These three problems come up in coding interviews so often they are almost a rite of passage. Reversing a linked list tests whether you can juggle pointers without losing the rest of the chain. Detecting a cycle uses Floyd’s tortoise-and-hare trick, where a slow pointer and a fast pointer will meet if and only if there is a loop, like two runners on a circular track where the faster one eventually laps the slower. Building a queue from two stacks tests whether you truly understand that reversing a stack twice gives you FIFO order. All three run below.

📄 drills.py: reverse a list, detect a cycle, and build a queue from two stacks

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

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def show(head):
    out = []
    while head:
        out.append(str(head.value))
        head = head.next
    return " -> ".join(out) or "(empty)"

# --- 1. Reverse a linked list in place ---
def reverse(head):
    prev = None
    while head:
        nxt = head.next     # remember the rest
        head.next = prev    # flip the pointer backwards
        prev = head         # advance prev
        head = nxt          # advance head
    return prev             # new head is the old tail

lst = build([1, 2, 3, 4, 5])
print("original:", show(lst))
print("reversed:", show(reverse(lst)))

print()

# --- 2. Detect a cycle with Floyd's tortoise and hare ---
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # one step
        fast = fast.next.next       # two steps
        if slow is fast:            # they meet inside a loop
            return True
    return False

straight = build([1, 2, 3])
print("straight list has cycle:", has_cycle(straight))

looped = build([1, 2, 3, 4])
tail = looped
while tail.next:
    tail = tail.next
tail.next = looped.next             # point tail back to node 2
print("looped list has cycle:  ", has_cycle(looped))

print()

# --- 3. A queue built from two stacks ---
class QueueFromStacks:
    def __init__(self):
        self.inbox = []             # push here
        self.outbox = []            # pop here

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

    def dequeue(self):
        if not self.outbox:                 # refill only when empty
            while self.inbox:
                self.outbox.append(self.inbox.pop())  # reverse the order
        return self.outbox.pop()

q = QueueFromStacks()
for name in ["Anvi", "Anvay", "Aviraj"]:
    q.enqueue(name)
print("dequeue:", q.dequeue())
print("dequeue:", q.dequeue())
q.enqueue("Aditi")
print("dequeue:", q.dequeue())
print("dequeue:", q.dequeue())

▶ Output

original: 1 -> 2 -> 3 -> 4 -> 5
reversed: 5 -> 4 -> 3 -> 2 -> 1

straight list has cycle: False
looped list has cycle:   True

dequeue: Anvi
dequeue: Anvay
dequeue: Aviraj
dequeue: Aditi

What happened here: The reversal walks the chain once and, at each node, saves the next link before flipping the current node’s pointer to face backward. When the loop ends, prev is sitting on the old tail, which is the new head, so 1 -> 2 -> 3 -> 4 -> 5 becomes 5 -> 4 -> 3 -> 2 -> 1 in a single O(n) pass with no extra list. Floyd’s cycle detector reports False on the straight list and True on the one whose tail we wired back to node 2, because the fast pointer, moving two steps to the slow pointer’s one, is guaranteed to lap and collide with it inside any loop.

The two-stack queue is the clever one: pushing goes into the inbox, and the first dequeue pours the inbox into the outbox, reversing the order so the oldest item ends up on top. That is why Anvi, Anvay, and Aviraj come out in arrival order even though each individual stack is LIFO.

Common Mistakes

❌ Mistake: Using a list as a queue with pop(0)

# Bad: pop(0) shifts every remaining element left -> O(n) per serve
queue = []
queue.append(task)
next_task = queue.pop(0)      # slow, and it gets slower as the queue grows

# Good: deque removes from the front in O(1)
from collections import deque
queue = deque()
queue.append(task)
next_task = queue.popleft()   # constant time, always

Why: A Python list stores its items in one contiguous block, so removing the first element forces everything after it to slide down one position. On a short queue you will never notice, but as you saw in the very first benchmark, the cost grows linearly with the length. A deque is built for this and removes from either end in constant time. Whenever the words “first in, first out” describe your problem, that is the signal to import deque.

❌ Mistake: Losing the rest of the list during pointer surgery

# Bad: overwrite head.next before saving it -> the tail is lost forever
def reverse_broken(head):
    prev = None
    while head:
        head.next = prev      # we just threw away the link to the rest!
        prev = head
        head = head.next      # head.next is now prev, so this loops or stops early

# Good: stash the next node BEFORE you rewrite the pointer
def reverse_ok(head):
    prev = None
    while head:
        nxt = head.next       # save first
        head.next = prev
        prev = head
        head = nxt
    return prev

Why: A linked list only knows where the rest of the chain is through the next pointer. The moment you overwrite head.next without first saving it, the tail of the list is unreachable and gone. The fix is a one-line discipline that applies to every linked-list operation: capture the node you are about to orphan in a temporary variable before you rewire anything. Draw the boxes and arrows on paper the first few times and this becomes automatic.

Best Practices

• List for a stack, deque for a queue. A plain list is a great, fast stack. The moment you need to remove from the front, switch to collections.deque and use popleft().
• Do not hand-roll a linked list in production Python. The built-in list and deque are implemented in C and beat a Python-level linked list for almost everything. Build one to learn pointers, then reach for the standard library.
• Prefer functools.lru_cache for caching. It is one line, thread-safe, and well tested. Only build an OrderedDict cache when you need eviction logic the decorator does not offer.
• Save before you rewire. In any linked-list operation, stash the node you are about to disconnect in a temporary variable first. This one habit prevents the most common linked-list bug.
• Match the structure to the traffic pattern. LIFO problems (undo, backtracking, bracket matching) want a stack; FIFO problems (scheduling, BFS, task pipelines) want a queue. Naming the pattern usually names the tool.

Wrapping Up

Stacks and queues are small ideas with enormous reach. A stack is a list you only touch at the top, a queue is a deque you add to at one end and serve from the other, and a linked list is a chain of nodes you rewire by moving pointers instead of shifting memory. You saw why a list makes a bad queue (the O(n) pop(0) that got steadily slower on the clock), you built each structure by hand, and you put them to work on the balanced-brackets, undo, BFS, LRU, and pointer-juggling problems that fill interview rounds and real codebases alike.

None of this depends on a framework or a library that will go out of fashion; it is standard-library Python that works the same in 3.14 as it did years ago and will keep working years from now.

Next in this chapter we build on these foundations with the tree and graph structures that power everything from file systems to recommendation engines. or step back and see the whole path on the Python + AI/ML tutorial series home.

Frequently Asked Questions

Interview Questions on Stacks and Queues

Interviewers rarely ask for definitions. They ask what happens in situations like these.

Q: Why is removing from the front of a Python list O(n), and how does a deque avoid it?

A list keeps its elements in one contiguous block indexed by position, so removing the first element leaves a hole at index 0 that Python fills by shifting every other element down one slot, which is O(n). A deque is implemented as a doubly linked structure of blocks, so it can detach the front element in constant time without moving the rest. That is why deque is the correct choice for a FIFO queue.

Q: How do you reverse a singly linked list in place, and what is its complexity?

You walk the list once with three references: previous, current, and a saved next. At each node you stash the next node, point the current node’s link back at previous, then advance previous and current forward. When current falls off the end, previous is the new head. It is O(n) time because you visit each node once, and O(1) space because you only keep a few pointers, no second list.

Q: How would you implement a queue using two stacks?

Keep an inbox stack for pushes and an outbox stack for pops. Enqueue always pushes onto the inbox. Dequeue pops from the outbox, but if the outbox is empty first, pour the entire inbox into it, which reverses the order so the oldest item ends up on top. Each element moves between stacks at most once, so the operations are amortized O(1) even though a single refill is O(n).

Q: Why does Floyd’s tortoise-and-hare detect a cycle, and what does it need?

If the list has a loop, the fast pointer gains one node on the slow pointer every step, so the gap between them shrinks by one each iteration until it hits zero and they land on the same node. If there is no loop, the fast pointer simply runs off the end. It needs only two pointers, giving O(1) extra space, and it finishes in O(n) time.

Q: A candidate uses a plain dict for an LRU cache and is surprised eviction is wrong. What is missing?

A plain dict does preserve insertion order, but an LRU cache also needs to move an item to the most-recent position every time it is read, not just when written. Without that, a frequently read old item still looks “old” and gets evicted incorrectly. An OrderedDict solves it with move_to_end on every access, and popitem(last=False) then reliably removes the genuinely least recently used entry.

Q: When is a stack the natural data structure to reach for?

Whenever the problem has a “most recent first” or “undo the last thing” shape. Matching brackets, evaluating expressions, backtracking through choices, walking a call stack, and depth-first search all fit, because each wants to finish the most recently opened piece of work before older ones. The moment you hear “last opened, first closed,” that is a stack.

Further reading: for the full reference, see the official Python documentation.

Related Posts

Previous: Sorting and Searching Algorithms in Python (From Scratch)

Next: Trees and Graphs in Python: BFS and DFS From Scratch

Series Home: Python + AI/ML Tutorial Series