Stacks, Queues and Linked Lists

Stack: last in, first out

class Stack:
    """A list is already a stack; wrapping it gives the right interface."""

    def __init__(self, items=None):
        self._items = list(items or [])

    def push(self, item):
        self._items.append(item)          # O(1)
        return self

    def pop(self):
        if not self._items:
            raise IndexError("pop from an empty stack")
        return self._items.pop()          # O(1)

    def peek(self):
        if not self._items:
            raise IndexError("peek at an empty stack")
        return self._items[-1]

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

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

    def __repr__(self):
        return f"Stack({self._items!r})"


stack = Stack()
for value in [1, 2, 3]:
    stack.push(value)

print(stack)
print(stack.pop(), stack.peek(), len(stack))     # 3 2 2

Where stacks appear

def is_balanced(text):
    """Check that brackets are matched and correctly nested."""
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []

    for character in text:
        if character in "([{":
            stack.append(character)
        elif character in pairs:
            if not stack or stack.pop() != pairs[character]:
                return False

    return not stack


for text in ["(a[b]{c})", "(a[b)c]", "((", "", "a(b)c"]:
    print(f"{text!r:<14}{is_balanced(text)}")

def evaluate_postfix(tokens):
    """Evaluate reverse Polish notation: 3 4 + 2 * -> 14."""
    import operator

    operations = {
        "+": operator.add, "-": operator.sub,
        "*": operator.mul, "/": operator.truediv,
    }
    stack = []

    for token in tokens.split():
        if token in operations:
            if len(stack) < 2:
                raise ValueError("not enough operands")
            right, left = stack.pop(), stack.pop()
            stack.append(operations[token](left, right))
        else:
            stack.append(float(token))

    if len(stack) != 1:
        raise ValueError("malformed expression")
    return stack[0]


print(evaluate_postfix("3 4 + 2 *"))       # 14.0
print(evaluate_postfix("5 1 2 + 4 * + 3 -"))   # 14.0

class UndoHistory:
    """Undo and redo with two stacks."""

    def __init__(self):
        self._done = []
        self._undone = []

    def do(self, action):
        self._done.append(action)
        self._undone.clear()          # a new action invalidates the redo stack
        return action

    def undo(self):
        if not self._done:
            return None
        action = self._done.pop()
        self._undone.append(action)
        return action

    def redo(self):
        if not self._undone:
            return None
        action = self._undone.pop()
        self._done.append(action)
        return action


history = UndoHistory()
for action in ["type a", "type b", "delete"]:
    history.do(action)

print(history.undo())      # delete
print(history.undo())      # type b
print(history.redo())      # type b

Queue: first in, first out

from collections import deque


class Queue:
    """A deque, because list.pop(0) is O(n)."""

    def __init__(self, items=None):
        self._items = deque(items or [])

    def enqueue(self, item):
        self._items.append(item)          # O(1)
        return self

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

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

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

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


queue = Queue()
for value in ["a", "b", "c"]:
    queue.enqueue(value)

print(queue.dequeue(), queue.peek(), len(queue))     # a b 2

Never build a queue on a list. list.pop(0) shifts every remaining element, making the queue O(n) per operation and O(n²) overall. collections.deque is O(1) at both ends.

import time
from collections import deque

n = 100_000

start = time.perf_counter()
values = list(range(n))
while values:
    values.pop(0)
print(f"list:  {time.perf_counter() - start:.3f}s")

start = time.perf_counter()
values = deque(range(n))
while values:
    values.popleft()
print(f"deque: {time.perf_counter() - start:.3f}s")

Priority queue

import heapq
import itertools


class PriorityQueue:
    """Lowest priority number comes out first; ties keep insertion order."""

    def __init__(self):
        self._heap = []
        self._counter = itertools.count()

    def push(self, item, priority):
        heapq.heappush(self._heap, (priority, next(self._counter), item))
        return self

    def pop(self):
        if not self._heap:
            raise IndexError("pop from an empty queue")
        priority, _, item = heapq.heappop(self._heap)
        return item, priority

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


queue = PriorityQueue()
queue.push("write report", 2)
queue.push("fix outage", 1)
queue.push("reply to email", 3)
queue.push("review PR", 1)

while queue:
    print(queue.pop())

The counter breaks ties without ever comparing the items themselves, which matters because heaps compare tuples element by element and your items may not be comparable at all.

Circular buffer

from collections import deque

recent = deque(maxlen=5)                  # keeps only the last five

for i in range(10):
    recent.append(i)

print(list(recent))                        # [5, 6, 7, 8, 9]

Linked list

class Node:
    __slots__ = ("value", "next")

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

    def __repr__(self):
        return f"Node({self.value!r})"


class LinkedList:
    def __init__(self, items=None):
        self.head = None
        self._size = 0
        for item in reversed(list(items or [])):
            self.prepend(item)

    def prepend(self, value):
        """Add at the front. O(1)."""
        self.head = Node(value, self.head)
        self._size += 1
        return self

    def append(self, value):
        """Add at the end. O(n) without a tail pointer."""
        node = Node(value)
        self._size += 1
        if self.head is None:
            self.head = node
            return self
        current = self.head
        while current.next:
            current = current.next
        current.next = node
        return self

    def find(self, value):
        """O(n) - there is no indexing."""
        current, index = self.head, 0
        while current:
            if current.value == value:
                return index
            current, index = current.next, index + 1
        return -1

    def remove(self, value):
        """Remove the first match. O(n)."""
        previous, current = None, self.head
        while current:
            if current.value == value:
                if previous is None:
                    self.head = current.next
                else:
                    previous.next = current.next
                self._size -= 1
                return True
            previous, current = current, current.next
        return False

    def reverse(self):
        """Reverse in place. O(n), O(1) extra space."""
        previous, current = None, self.head
        while current:
            following = current.next
            current.next = previous
            previous, current = current, following
        self.head = previous
        return self

    def __len__(self):
        return self._size

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

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


chain = LinkedList([1, 2, 3])
chain.append(4).prepend(0)
print(chain)                     # 0 -> 1 -> 2 -> 3 -> 4
print(chain.find(3), len(chain))
chain.remove(2)
print(chain)
print(chain.reverse())

reversing, one pointer at a time:

  previous   current
     None  ->  [1] -> [2] -> [3] -> None
               ^
  after one step:
     None <- [1]     [2] -> [3] -> None
              ^       ^
           previous current

Classic linked list problems

def middle_node(head):
    """Find the middle in one pass, using two pointers."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


def has_cycle(head):
    """Detect a loop. Floyd's algorithm: O(n) time, O(1) space."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


a, b, c = Node(1), Node(2), Node(3)
a.next, b.next = b, c
print(middle_node(a).value)          # 2
print(has_cycle(a))                  # False

c.next = a                            # create a loop
print(has_cycle(a))                  # True

Linked list or list?

In Python you will almost never need a linked list. list covers indexed access and deque covers both ends, both implemented in C. Linked lists are worth building once because interviews ask about them and because the pointer manipulation teaches something real - not because you will deploy one.

Common mistakes

• Using list.pop(0) for a queue.
• Popping from an empty stack or queue without checking.
• Losing the rest of a linked list by reassigning next before saving it.
• Forgetting the head case when removing the first node.
• Pushing non-comparable items into a heap without a tie breaker.
• Building a linked list where a list or deque would be faster and shorter.

Best practices

• Use a list for a stack and a deque for a queue.
• Use heapq for priorities, with a counter to break ties.
• Use deque(maxlen=n) for a sliding window or recent history.
• Wrap the structure in a class so only the intended operations are exposed.
• Raise a clear error on empty rather than returning None.

Practice

1. Implement a stack that also reports the minimum value in O(1).
2. Build a queue using two stacks and explain the amortised cost.
3. Reverse a linked list iteratively and recursively.
4. Detect and locate the start of a cycle in a linked list.
5. Implement a task scheduler with a priority queue and stable ordering.

Conclusion

A stack adds and removes at one end, a queue at opposite ends, and a linked list gives O(1) insertion anywhere you already hold a node. In Python, use list and deque for the first two and build the third only to understand it.