Speaker note: Today we meet the two oldest, most-used linear structures in computing. Stack = touch one end only. Queue = add at one end, remove at the other. That single rule change explains everything that follows.
Speaker note: Sixteen short animations carry the whole lecture; each appears once, exactly where its idea is introduced.
Speaker note: Every term gets a full definition the first time it appears; this table just says where to find it again.
Speaker note: Open a terminal now if you want to run these live; every snippet on today's slides compiles and runs exactly as shown.
Speaker note: Nothing new about memory is needed today — only new rules about which end of it you are allowed to touch.
Speaker note: We will do both malloc and free again today, and point out exactly where a forgotten free would bite.
Speaker note: The only new part today is restricting which end(s) of the chain you are allowed to touch.
Speaker note: Ask the class: which end of a queue do the ones who arrived first sit at? The front — and that is the whole idea.
Speaker note: Every box on this map gets its own slides below, most with a short animation and a complete C/Java program.
Speaker note: Section 1 builds the stack from scratch: an array version, then a linked version, both with the same tiny interface.
Speaker note: Ask: how would you build that "history" feature with only an array or a linked list? The answer is coming.
Speaker note: Every function call your computer makes right now still uses a hardware/software stack, exactly like these early machines did.
Speaker note: LIFO = Last In, First Out. Keep this cafeteria picture in mind for every operation today.
Speaker note: These three short names are standard across every language and textbook; learn them now, they never change.
Speaker note: An ADT describes what a structure does, not how — this table holds whether it is built from an array or a linked list.
Speaker note: Nothing else in memory ever moves — only the single integer top changes.
Speaker note: Normal example: 10 pushes (12, 7, 25, 3, 18, 9, 30, 14, 5, 21), then 4 pops — watch top and the array update one step at a time.
Speaker note: Check first, refuse if full, then two writes — top moves, the value lands. Two steps, always.
Speaker note: Same shape as push, mirrored: check empty, read the top slot, move top down.
Speaker note: Last pushed (21) comes back first, then 5, 14, 30 — last in, first out.
Speaker note: This constant-time guarantee is the entire point of a stack — reaching the middle needs a different structure.
Speaker note: Writing outside array bounds in C does not raise a friendly error — it corrupts nearby memory silently.
Speaker note: A 10-slot stack takes 11 pushes (overflow on the last one), then 13 pops (underflow after draining) — watch both checks fire.
Speaker note: Valid indices run 0..CAP-1, so the stack is full the moment top reaches CAP-1, not one step later.
Speaker note: Let the class answer before revealing — index 0 is a real, valid slot.
Speaker note: -1 is not a valid index, so it can only ever mean "no elements".
Speaker note: Exactly the same node-and-pointer idea from Week 2, restricted to touching one end.
Speaker note: Watch malloc create a node, then three pointer rewrites move top — no capacity limit anywhere.
Speaker note: New node points at the old top, then top moves to the new node — three assignments, always.
Speaker note: tmp holds the old top just long enough to read its value and free it after top has already moved on.
Speaker note: The trade for unlimited capacity is a little extra memory per element and worse cache locality.
Speaker note: free(tmp); return tmp->data; reads memory already given back — sometimes it "works", sometimes it crashes.
Speaker note: Both push and pop are O(1) either way; the difference is capacity and memory locality, not speed class.
Speaker note: Each push adds 1 to top, each pop subtracts 1 — do the arithmetic together.
Speaker note: This is exactly the bookkeeping the push/pop code we just read performs, one step at a time.
Speaker note: Three classic algorithms, all built on the same tiny stack interface: check brackets, evaluate postfix, convert infix to postfix.
Speaker note: Ask the class to compute A + B * C by hand — everyone silently applies precedence without noticing.
Speaker note: RPN calculators are still sold today; the algorithm on the next slides is exactly what runs inside them.
Speaker note: Postfix and prefix need no parentheses and no precedence table at evaluation time — that work was already done once.
Speaker note: "Most recently opened" should immediately make everyone think of a stack — that phrase is the whole algorithm.
Speaker note: Three distinct ways to fail; a correct checker must catch all three, not just the first.
Speaker note: Watch the mismatch: a `]` arrives while `(` sits on top — no match, reject immediately.
Speaker note: A tiny helper: does this closing bracket pair with this opening bracket?
Speaker note: The very last line is the one people forget: the string can end with unmatched openers still on the stack.
Speaker note: One pass, one stack, done — this is the shape almost every stack algorithm today will take.
Speaker note: A common bug: checking only case 1 and forgetting the final `return top == -1;`.
Speaker note: One unmatched opening parenthesis — walk through what the stack looks like at the very end.
Speaker note: This is exactly failure case 3 from the previous slide.
Speaker note: Ask the class to predict the result before the animation runs.
Speaker note: Every number is pushed; every operator pops two values, applies itself, and pushes the result back.
Speaker note: A small dispatcher — nothing surprising, just the four arithmetic operators.
Speaker note: b comes off first (right operand), a second (left operand) — order matters for minus and divide.
Speaker note: Calculators and compilers evaluate expressions exactly this way, in real time, on huge inputs.
Speaker note: This is the single most common bug students write in this algorithm.
Speaker note: Think about what each algorithm is actually producing at the end.
Speaker note: This distinction — collapsing values vs. reordering symbols — is worth restating slowly.
Speaker note: Prefix is the mirror image of postfix in every respect — direction of scan, and which operand comes off first.
Speaker note: Normal example: 11 tokens, no errors. The "hard" example actually errors out — more tokens is not automatically a valid expression.
Speaker note: Getting the pop order backwards silently breaks every non-commutative operator: minus and divide.
Speaker note: This is the classic first "compiler-shaped" algorithm most students ever write.
Speaker note: Every operand goes straight to output; every operator first flushes stronger waiting operators, then is pushed.
Speaker note: A tiny precedence table — multiply/divide bind tighter than plus/minus.
Speaker note: The final while-loop is the "flush" step: whatever is left on the stack still has to reach the output.
Speaker note: Same shape, same bound, as every other stack algorithm we have seen today.
Speaker note: A-B-C must become (A-B)-C, which needs equal-precedence operators to also be popped first.
Speaker note: Give the class thirty seconds, then reveal and compare to the algorithm's own trace.
Speaker note: Walk through this trace line by line if the class looks unsure.
Speaker note: Three already-familiar steps instead of a brand-new algorithm — that is the whole trick.
Speaker note: Same normal example as infix-to-postfix, A+B*C-D+E*F, so the two outputs can be compared side by side.
Speaker note: Compare the postfix and prefix outputs for a same-precedence chain like A+B+C+... to see the rule in action.
Speaker note: The connection that makes recursion click: every function call, recursive or not, pushes a real stack frame.
Speaker note: A function that calls itself on a smaller version of the same problem, until a case simple enough to answer directly.
Speaker note: We are about to meet exactly the memory structure that runs out — the call stack.
Speaker note: This is the smallest possible recursive function — everything about base cases shows up here first.
Speaker note: Normal example: countdown from 10. Edge cases n=0 and n=-4 both hit the base case immediately.
Speaker note: This is the exact bug that turned "countdown from -4" into an infinite loop before the fix.
Speaker note: You have been using a stack every time you called a function — you just could not see it until today.
Speaker note: Normal example: fact(10), 10 frames deep — each waits on the next, then frames unwind in reverse order.
Speaker note: Two lines: a base case that stops the recursion, and a recursive call on a strictly smaller problem.
Speaker note: Small output, but the call-stack machinery behind it is the real subject of this section.
Speaker note: Recursion often reads more clearly than a loop, but it is never free of memory cost.
Speaker note: This is why the "hard" example in the picker stops at 12 — one call short of the overflow.
Speaker note: This crash has a name you already know from Section 1: stack overflow — just applied to the call stack instead.
Speaker note: Decrementing by 2 from an odd starting n that expects to hit 0 is a classic version of this bug.
Speaker note: Count them together: fact(3), fact(2), fact(1), fact(0).
Speaker note: None of these frames have returned yet — that is exactly why they are still on the stack.
Speaker note: -1 never equals 1 on the way down through -2, -3, -4...
Speaker note: A wrong base-case condition is just as dangerous as a missing one.
Speaker note: The standard first example of a problem that is easy to solve recursively yet fundamentally exponential.
Speaker note: The legend: monks moving 64 golden disks, and the world ends when they finish. Not a bad time estimate, as we'll see.
Speaker note: Steps 1 and 3 are the same problem, just smaller, with the rods relabeled — a perfect recursion.
Speaker note: Normal example: 4 disks, 15 moves. No explicit stack needed in the code — the call stack itself remembers "from, to, via".
Speaker note: Four lines, and the recursion structure is identical in spirit to fact() — smaller problem, act, smaller problem.
Speaker note: Fifteen moves for four disks — we will see exactly why that number in a moment.
Speaker note: No implementation trick fixes exponential growth — only a smaller n does.
Speaker note: The monks' prophecy about the world ending was, in a sense, a reasonable time estimate.
Speaker note: The call stack that tracked "from, to, via" here is the same call stack DFS will use to track "where to backtrack".
Speaker note: Apply the formula from two slides ago.
Speaker note: Doubling the disks by one adds roughly double the moves, minus one.
Speaker note: Think about what the "destination" and "spare" are for the smaller sub-problem.
Speaker note: This rotation is the part students find hardest to trace by hand — the animation makes it visible.
Speaker note: The mirror image of the stack: same two operations, opposite ends, different name — FIFO instead of LIFO.
Speaker note: Ask: who leaves the supermarket line first — the newest arrival, or the one who has waited longest?
Speaker note: Stack: one end. Queue: two ends, one for each operation — that is the entire conceptual jump.
Speaker note: We will build this ADT three different ways, each with its own trade-off.
Speaker note: Something goes wrong with the unused space at the front as elements are dequeued — the animation shows it.
Speaker note: Normal example: fill 8 cells, remove 3, then two more enqueues still fail — front never reuses the cells dequeue frees.
Speaker note: Simple and O(1), but rear never comes back, no matter how many cells dequeue frees near the front.
Speaker note: Cells 0, 1, 2 are empty, yet the queue insists it is full — that is the drift problem.
Speaker note: Shifting every element after each dequeue would fix it, but turns O(1) dequeues into O(n) — not acceptable.
Speaker note: Look again at what enqueue actually checks.
Speaker note: This sets up the circular queue perfectly.
Speaker note: The wasted space was only wasted because we were thinking of the array as a straight line.
Speaker note: Normal example: 10-cell ring, moderate mixing, one wrap-around — watch rear reuse the cells dequeue freed at the front.
Speaker note: The only change from the naive version: rear wraps with modulo, and count tracks true fullness.
Speaker note: Same mirror shape as enqueue — front also wraps with modulo now.
Speaker note: count resolves the ambiguity directly instead of relying on clever index tricks.
Speaker note: This is the queue implementation you would actually use in a real bounded buffer.
Speaker note: If only rear wraps and not front, the ring breaks silently after the first wrap-around.
Speaker note: Both "just became empty" and "just became full" can show front == rear.
Speaker note: This is why count is not optional bookkeeping — it is the only thing resolving the ambiguity.
Speaker note: Same overflow-removal trade as the linked stack, but this time we need a pointer to each end.
Speaker note: With one node, front and rear point to the same node — watch that special case at the very start.
Speaker note: The empty-queue case sets both pointers to the new node; otherwise only rear moves.
Speaker note: If the queue just became empty, rear must also be reset to NULL, or the next enqueue writes through garbage.
Speaker note: A single node is both the front and the rear — both pointers must point to it.
Speaker note: Compare where each structure adds and where it removes.
Speaker note: Without rear, enqueue would need to walk the entire list to find the last node — O(n), not O(1).
Speaker note: A deque behaves like a stack and a queue at the same time, depending only on which operations you call.
Speaker note: Built here on a doubly linked list, each end getting its own pair of pointer rewrites.
Speaker note: Watch push_front insert at the opposite end from push_back — something a plain queue could never do.
Speaker note: push_front is the mirror image of this function, touching front/prev instead of back/next.
Speaker note: pop_front mirrors this exactly, touching front/next instead of back/prev.
Speaker note: In C there is no standard deque, so we build one; in Java, java.util.ArrayDeque already gives us this.
Speaker note: Trace one call at a time.
Speaker note: Front-inserts build backwards from the left; back-inserts build forwards on the right.
Speaker note: This needs no new code today — just several of the queues we already built, plus a small selection rule.
Speaker note: The scheduler serves higher queues first, falling through to lower ones only when higher ones are empty.
Speaker note: Normal example: 12 processes evenly spread across three classes. admit() enqueues by level; pick_next() always tries level 0 first.
Speaker note: Real schedulers add aging or time-slicing so a lower level is never starved forever.
Speaker note: Look at what each individual level actually is.
Speaker note: You will meet its close relative, the priority queue, built on a heap, next week.
Speaker note: All three obey the exact same LIFO rule — only the storage and the capacity limit differ.
Speaker note: The circular queue is the one you would actually ship; the naive array queue is a teaching stepping stone.
Speaker note: Both generalize the plain queue — one by relaxing which end you touch, one by adding priority.
Speaker note: Four very different-looking problems, all solved by the exact same tiny stack interface.
Speaker note: If a student remembers only one sentence from today, this is the one worth remembering.
Speaker note: These are the same five exercises listed at the end of the written notes, with worked answer sketches.
Speaker note: These mirror the self-check quiz at the end of the week notes, one question per slide.
Speaker note: Ask, wait, then advance.
Speaker note: The plate-stack picture from Section 1 is the whole idea.
Speaker note: Ask, wait, then advance.
Speaker note: The waiting-line picture from Section 5 is the whole idea.
Speaker note: Think about the valid index range.
Speaker note: Waiting for top == CAP would already be one slot past the array's end.
Speaker note: Recall the "right operand first" rule.
Speaker note: This is exactly why 8 2 - means 8 - 2, not 2 - 8.
Speaker note: This is the drift problem, restated as a question.
Speaker note: The queue "drifts" right until it hits the end of the array.
Speaker note: Think about the front == rear ambiguity.
Speaker note: After a wraparound, front == rear no longer decides the question by itself.
Speaker note: Recall the very first code slide of Section 3.
Speaker note: Every recursive function needs at least one reachable base case.
Speaker note: Compare it to the LIFO rule from Section 1.
Speaker note: Just like the most recently pushed element of any stack is the next one popped.
Speaker note: Recall the recurrence from Section 4.
Speaker note: For n = 64, that is about 585 billion years at one move per second.
Speaker note: Think about which ends each structure is allowed to touch.
Speaker note: A plain stack only ever touches its top; a plain queue only adds at one end and removes at the other.
Speaker note: Solve the left subtree, visit the node, solve the right subtree — exactly Hanoi's recursion shape, on a new shape of data.
Speaker note: These are the same references listed at the end of the week's written notes.
Speaker note: The historical references (Lucas, Łukasiewicz) are what today's "short history" slides drew on.