Unit 15: Stacks, Queues, and Deques
Two disciplines for what comes out next, last in first out and first in first out, and the double-ended structure that does both.
6 topics · 21 questions
Each topic is a path, not a menu: work down it in order and every question builds on the one above. Click any of them to watch the answer draw itself.
The Stack ADT: Last In, First Out
- How it worksHow does a stack only ever let you push onto the top or pop from the top, never the bottom?
- Worked exampleTrace push(3), push(7), push(1), pop(), pop() on an initially empty stack and find its final contents.
- Common mistakeWhy isn't a stack able to remove an item from its middle or its bottom directly?
Your turn1 of 2
push(3), push(7), push(1) are called on an empty stack, then pop() is called 2 times. How many elements remain on the stack?The Queue ADT: First In, First Out
- How it worksHow does a queue add every new item to the back while only ever removing from the front?
- Worked exampleTrace enqueue(3), enqueue(7), enqueue(1), dequeue(), dequeue() on an initially empty queue.
- Common mistakeWhy isn't a queue's front the same end that new items get added to?
Your turn1 of 2
enqueue(3), enqueue(7), enqueue(1) are called on an empty queue, then dequeue() is called 2 times. How many elements remain in the queue?Implementing a Stack or Queue with an Array Versus a Linked List
- How it worksHow does removing from the front of an array-backed queue force every remaining element to shift left?
- Worked exampleTrace dequeue on an array-backed queue [3, 7, 1, 9] and find how many elements have to shift.
- Going furtherWhat changes once the same queue is implemented with a linked list tracking both a front and a back?
- Worked exampleTrace dequeue on a linked-list-backed queue with a tracked back pointer removing from 3 → 7 → 1.
- Ties togetherHow does swapping an array for a linked list trade shifting cost for extra memory per element?
Your turn1 of 2
Dequeue on an array-backed queue removes the front element, forcing the remaining 6964 elements to shift left by one spot. How many elements need to shift for one such dequeue?Deques: Double-Ended Queues
- How it worksHow does a deque support push and pop operations on both its front and its back?
- Worked exampleTrace push_front(1), push_back(2), push_front(0), pop_back() on an initially empty deque.
- Ties togetherHow does a deque let one single structure act as both a stack and a queue depending on which end you use?
Your turn1 of 2
A deque starts empty. push_front is called 35 times and push_back is called 33 times, with no pops. How many total elements does the deque hold?Using a Stack to Check Balanced Parentheses
- How it worksHow does pushing every open bracket and popping on every close bracket catch a mismatch the moment it happens?
- Worked exampleTrace checking the expression ( [ ) ] for balance using a stack.
- Going furtherWhat happens to the stack check once the expression also allows curly braces alongside parentheses and brackets?
- Going furtherWhat happens to the stack check when the expression ( ] mismatches bracket types entirely?
Your turn1 of 2
Checking balanced parentheses pushes every open bracket and pops on every close bracket. An expression has 70 open brackets and all are matched by a close bracket later. How many total push operations does checking this expression perform?The Call Stack Is Itself a Stack
- How it worksHow does calling a function push a frame the same way push adds to a stack, and returning pop it like pop does?
- Common mistakeWhy isn't the fact that functions return in the reverse order they were called a coincidence?
- Ties togetherHow does understanding a stack ADT make it obvious why the most recently called function always returns first?
Your turn1 of 2
A chain of 15 nested function calls, each waiting on the next, all return in the exact reverse order they were called, since the call stack is itself a stack. Which call, counting from 1 as the first called, returns first?