Micro-questions over the stacks and queues module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The one rule
1. What is a collection, and what separates a stack from a queue?
Answer
A collection is any structure holding a group of items. What separates them is the single rule deciding which item comes out next.
2. What does LIFO stand for, and give two examples.
Answer
Last in, first out — the most recently added item is removed first. A stack of plates; pressing undo repeatedly.
3. What does FIFO stand for, and give two examples.
Answer
First in, first out — the item waiting longest is removed first. A queue at a counter; a printer working through jobs.
4. In one sentence, how do the two ADTs relate?
Answer
They are the same ADT with one rule changed, and everything else follows from it.
B. The vocabulary
5. What are push and pop?
Answer
Adding to and removing from a stack. Push puts the item on top; pop takes it off the top.
6. What are enqueue and dequeue?
Answer
Adding to and removing from a queue. Enqueue joins the back; dequeue takes from the front.
7. What is peek, and what is it called on each?
Answer
Looking at the item that would come out next without removing it. Often top on a stack and front on a queue.
8. Why is peek useful?
Answer
When you must decide what to do based on what is next, before committing to taking it — as in the iterative post-order traversal and every monotonic-stack problem.
9. What is underflow?
Answer
Trying to remove from an empty collection. Every implementation must decide what to do — raise an error or return a “nothing here” value — and must say which.
10. What is overflow, and where does it apply?
Answer
Trying to add to a collection with no room left. Only applies to fixed-capacity implementations.
11. What is a circular buffer?
Answer
Also a ring buffer — a fixed-capacity queue inside a flat array, where front and back wrap around using %. It avoids ever shifting elements, which is what keeps operations .
C. Stacks
12. How do you build a stack in Python, and what are the costs?
Answer
A plain list with .append() — amortised — and .pop() — , because both act on the end of the array where nothing needs shifting.
13. Name four places stacks appear in production.
Answer
The function call stack (active calls, locals, return addresses); undo/redo; balanced parentheses validation; depth-first search.
14. What connects all four?
Answer
Each needs the most recent thing back first — the innermost call, the last action, the last opened bracket, the deepest branch.
D. Queues
15. What is the pop(0) trap?
Answer
queue.pop(0) on a Python list is — it removes index 0 and shifts every remaining item left by one. It looks like an operation and is not.
16. What is the correct Python queue?
Answer
collections.deque, with .append() to enqueue and .popleft() to dequeue — both genuinely , because it is a doubly linked structure of blocks.
17. Why does a queue built on a plain array need a ring buffer?
Answer
Because removing from the front of a contiguous array shifts everything. Wrapping the front index around with % moves the index instead of the data.
18. Write the two wraparound lines.
Answer
self.tail = (self.tail + 1) % self.capacity # on enqueue
self.head = (self.head + 1) % self.capacity # on dequeue19. Why does a circular queue track size separately?
Answer
Because head == tail is ambiguous — it means both empty and full. Keeping a count disambiguates it. (The alternative is deliberately wasting one slot.)
E. Costs
20. Give the cost table for all four implementations.
Answer
| Structure | Insert | Delete | Peek | Space |
|---|---|---|---|---|
| Stack (array) | amortised | |||
Queue (deque) | ||||
Queue (list.pop(0)) | ||||
| Circular buffer |
21. Why is the stack’s insert amortised rather than exact?
Answer
Because it sits on a dynamic array, and the occasional append triggers a resize copy.
F. The ADTs
22. List the stack ADT.
Answer
push(item), pop(), peek(), is_empty(), size() — all .
23. List the queue ADT.
Answer
enqueue(item), dequeue(), front(), is_empty(), size() — all .
24. Do the ADTs say anything about memory or layout?
Answer
No. You can build either on an array or on a linked list and the ADT does not change.
25. What operation do both deliberately refuse, and why is that the point?
Answer
There is no get(i) — no reaching into the middle. By refusing random access, they guarantee the order things come out in, and that guarantee is what makes them useful for reasoning.
26. What guarantee does each buy, and what depends on it?
Answer
Stack: most recent first — DFS, undo histories, the call stack, bracket matching. Queue: oldest first — BFS exploring level by level, and a fair print queue.
27. State the choice in one sentence.
Answer
Choosing a stack or a queue is choosing a guarantee, not choosing a container.
G. Traps
28. What causes a stack overflow?
Answer
Recursive calls filling the call stack — most often infinite recursion, but also a legitimately deep traversal on a degenerate structure.
29. What happens if you pop without checking is_empty()?
Answer
An index error at runtime. Underflow must be handled explicitly, not assumed away.
30. You need at both ends. What do you use?
Answer
A deque (double-ended queue) — which is what Python’s collections.deque actually is, and why it serves as both stack and queue.
31. Summarise the pair in one sentence.
Answer
Two containers that refuse random access in exchange for a promise about ordering — LIFO for recency, FIFO for fairness.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Stacks and Queues — the module
- Depth-First Traversals — Question Bank — the stack in use
- BFS — Question Bank — the queue in use
- Monotonic Stack — the pattern built on peek
Software engineering
Infrastructure & security
Computer science
Hardware & engineering