Stacks, Queues & Linked Lists

This lab shows two ways to get a stack: the quick way (a plain Python list already behaves like a stack) and the honest way (a small class that spells out every operation so the rules are obvious).

1. stack.append("a") is a push — it adds to the end of the list, which we treat as the top. stack[-1] is a peek: -1 means "last item", and it looks without removing. stack.pop() is a pop: it removes and returns the last item ('b' here).
2. The Stack class stores its data in a private list self._items. The leading underscore is a convention meaning "don't poke at this from outside — use my methods".
3. push appends, pop first calls is_empty() and raises an error on an empty stack instead of returning garbage, and peek returns the top without removing it — exactly the contract the diagram drew.
4. __len__ lets you write len(my_stack), and is_empty returns not self._items — an empty list is "falsy", so not [] is True.

What the output means: Nothing prints here (it's building blocks). After the top lines, top holds 'b' (peeked, still on the stack) and x holds 'b' (popped, now removed).

Try this: Call pop() on an empty Stack() and read the IndexError — that deliberate error is the class keeping its promise instead of failing silently.

A real, famous use of a stack: checking that brackets in a string are balanced — every (, [ and { is closed by the right partner in the right order. The stack remembers the openers you still owe a closer for.

1. pairs is a lookup table from each closer to the opener it must match (")" needs "(", and so on).
2. Walking through the string one character at a time: if ch is an opener (in "([{"), we push it onto the stack — "remember this is open".
3. If ch is a closer, the top of the stack must be its matching opener. not stack (nothing to match) or stack.pop() != pairs[ch] (wrong partner) means it's unbalanced, so we return False immediately.
4. At the end, return not stack means "balanced only if the stack is empty" — anything left over is an opener that never got closed.

What the output means: is_balanced("{[()]}") prints True (perfectly nested); is_balanced("{[(])}") prints False — the ] arrives while ( is still on top, so the partners cross.

Try this: Trace "([)]" by hand, pushing and popping as you go. You will hit a mismatch — which is exactly why editors use a stack to highlight your unbalanced brackets.

Two queues in one lab: first the easy, correct tool (collections.deque), then a clever from-scratch queue built out of two stacks — a classic interview puzzle.

1. deque() is a double-ended queue. q.append("task1") adds at the back and q.popleft() removes from the front — both fast (O(1)). This is the queue you should actually use.
2. The Queue class keeps two lists: _in (where new items land) and _out (where items leave). enqueue just appends to _in.
3. dequeue is the trick: if _out is empty, it pours everything from _in into _out by popping (self._in.pop()) and appending. Popping off one stack and pushing onto another reverses the order — which flips last-in-first-out back into first-in-first-out.
4. After the refill it pops from _out, so the oldest item comes out first. It still raises an IndexError if there is genuinely nothing to dequeue.

What the output means: first ends up as 'task1' — the first thing enqueued is the first thing dequeued, proving FIFO order from two LIFO stacks.

Try this: The note below explains why this averages O(1): each item is moved from _in to _out exactly once. Enqueue three items, dequeue one, enqueue two more, and trace when the refill fires.

This lab shows the single most useful deque trick: give it a maxlen and it becomes a bounded history that automatically forgets the oldest item once it's full.

1. deque(maxlen=3) can hold at most 3 items. Once it's full, every new append silently drops one from the far end to make room.
2. The loop appends "m1", "m2", "m3", then "m4". When "m4" is added the deque is already full, so "m1" (the oldest) falls off the front.
3. list(recent) just converts the deque to a normal list so we can print it.
4. appendleft("m0") adds at the front instead; since the deque is full, that pushes off the far end ("m4").

What the output means: print(list(recent)) shows ['m2', 'm3', 'm4'] — 'm1' was evicted the moment a 4th item arrived, with no bookkeeping from you.

Try this: This is exactly how you keep "the last N chat messages" in an agent. Change maxlen to 2 and predict the printout before running it.

The heapq module turns any plain list into a min-heap — a structure whose smallest item is always instantly available. This lab uses it two ways: as a priority queue, and to grab the top-k biggest scores without sorting everything.

1. pq = [] starts as an ordinary empty list; heapq functions maintain the heap order for you. heappush(pq, (2, "reindex")) adds a (priority, item) pair.
2. Because tuples compare by their first element, the priority number decides ordering. heappop(pq) removes and returns the smallest — here (1, 'page oncall') — no matter what order things were pushed.
3. scores is a list of (score, doc) pairs. heapq.nlargest(2, scores) returns the two largest pairs directly, again comparing by the first element.
4. This is the retrieval trick: to get the k best matches out of millions you never sort the whole list — a size-k heap does it in O(n log k).

What the output means: heappop prints (1, 'page oncall') (lowest number = highest priority), and top2 becomes [(0.91,'docA'), (0.88,'docD')] — the two highest scores.

Try this: Add (0, "outage") to pq and pop again — it jumps the line. That is how a scheduler makes urgent work run first.

Here we build a singly linked list from nothing, then solve its most famous puzzle: reversing it in place. Everything is just re-pointing the .next arrows the diagram drew.

1. Node holds a value and next (the arrow to the following node, or None at the end). That's the whole box-with-a-pointer idea in code.
2. LinkedList keeps only self.head. push_front makes a new node whose next is the old head, then makes it the new head — an O(1) insert at the start.
3. __iter__ walks the chain: start at head, yield each value, then hop to cur.next until cur is None. This lets you write for v in my_list. find reuses it — it must scan (O(n)) because there's no random access.
4. reverse is the classic: keep three markers. nxt remembers the rest before you break the link, cur.next = prev flips this node's arrow backwards, then prev and cur both step forward. When cur runs off the end, prev is the new head.

What the output means: reverse returns the new head of a list running in the opposite direction — done in one pass (O(n) time) using only three variables (O(1) extra space).

Try this: Draw three nodes A→B→C and move prev/cur/nxt along on paper. Watch each arrow flip; this pointer-juggling is asked in interviews constantly.

This builds the doubly linked list, using a neat trick — two sentinel nodes — to make the code short and bug-free. Sentinels are permanent dummy nodes at the ends that hold no real data.

1. DNode stores a key, a value, and two pointers prev and next (both start as None).
2. The constructor creates a head and tail sentinel, then links them to each other. Real items always live between these two, so the list is never truly empty and you never have to special-case "first item" or "last item".
3. add_back inserts a node just before tail: grab the current last real node (self.tail.prev), then rewire four pointers so the new node sits between it and tail.
4. remove is the diagram's blue arc in code: node.prev.next = node.next and node.next.prev = node.prev — the two neighbours now point at each other, skipping the node. No scanning, so O(1).

What the output means: Nothing prints — this is a reusable building block. Both add_back and remove touch a fixed handful of pointers, so both are O(1) regardless of list size.

Try this: Notice there are no if node is None checks. That simplicity is because of the sentinels — the ends always exist, so the neighbour pointers are never missing.

The whole tortoise-and-hare idea in six lines: walk two pointers at different speeds and watch for them to collide.

1. slow = fast = head starts both pointers at the front of the list.
2. The loop condition while fast and fast.next stops safely: if fast or the node after it is None, we've hit the end and can call fast.next.next without crashing.
3. Each pass, slow advances one node and fast advances two. If there's a loop, fast keeps circling and gains on slow.
4. if slow is fast checks whether they're now the same node (is compares identity, not value). If so, they met inside a loop → return True. If the loop instead runs off the end, we return False.

What the output means: True when the list loops back on itself, False when it terminates normally — using just two pointers, no set of visited nodes.

Try this: Build 1→2→3→1 (a loop) versus 1→2→3→None and run both. The first returns True, the second False.

Here the two structures from the diagram become one working cache with O(1) get and put — then the punchline: Python's standard library already gives you this for free.

1. In __init__, self.map is the dict (key → node) for instant lookup and self.dll is the doubly linked list holding recency order (front = old, back = new).
2. get: if the key is missing, return None. Otherwise find the node via the map, then remove it and add_back it — pulling it out and re-attaching at the back marks it most-recently-used, all in O(1).
3. put: if the key already exists, unlink the old node first. Make a new node, record it in the map, and add_back (most-recent). If we're now over self.cap, evict: self.dll.head.next is the front node (least recently used), remove it and delete its key from the map.
4. The final block shows the shortcut: @lru_cache(maxsize=256) above a function makes Python cache its results automatically — the same dict-plus-recency machinery, hidden behind a decorator.

What the output means: Not runnable as-is (it uses the DoublyLinkedList from §7 — see the collapsed setup block). Conceptually: repeated get/put stay fast forever, and old entries silently disappear once you pass capacity.

Try this: Now you know what @lru_cache does under the hood. Trace a capacity-2 cache: put a, put b, get a, put c — which key gets evicted, and why is it b?

The interview version of the balanced-brackets checker from §2 — classic problem. Same stack idea, written as tightly as possible.

1. pairs maps each closer to its opener. stack holds openers we haven't matched yet.
2. For each character: if it's an opener (c in "([{"), push it. Otherwise it's a closer, so the top must be its partner.
3. not stack or stack.pop() != pairs[c] catches both failures at once — an empty stack (a closer with nothing open) or a mismatched partner — and returns False.
4. return not stack at the end means "valid only if nothing is left open".

What the output means: True for correctly nested brackets, False otherwise — the canonical one-stack answer interviewers expect.

Try this: This is the §2 checker minus comments. Say out loud why the stack is the right structure here: the most recent opener must be the first one closed — that's LIFO.

classic problem: a stack that can also report its current minimum in O(1) — no scanning. The trick is a second stack that tracks the running minimum alongside the values.

1. self.st is the normal value stack; self.mins is a parallel stack whose top is always the smallest value currently in st.
2. On push(x), we push x to st, and push to mins either x (if it's the first) or min(x, self.mins[-1]) — the smaller of the new value and the previous minimum.
3. pop pops both stacks together, so the two stay in lock-step and the minimum for the remaining values is still correct.
4. get_min just returns self.mins[-1] — the top of the mins stack — instantly.

What the output means: get_min() always returns the smallest value still on the stack in O(1), because that answer was pre-computed on every push.

Try this: Push 5, 3, 7, 2, then pop twice, calling get_min after each step. Watch the mins stack shadow the values and always keep the current minimum on top.