Data Structures Stacks and Queues 1 — Questions and Answers
Question 1: Which real-world scenario best illustrates LIFO (Last In, First Out) behavior?
- Waiting in a checkout line
- Undo/redo functionality in a text editor (Correct answer)
- Scheduling print jobs on a printer
- Breadth-first traversal of a graph
Correct answer: Undo/redo functionality in a text editor
Undo/redo works like a stack — the most recently performed action is always the first to be undone, exemplifying LIFO behavior.
Question 2: What is the time complexity of the push and pop operations on a stack?
- O(n) for both
- O(log n) for both
- O(1) for both (Correct answer)
- O(1) push, O(n) pop
Correct answer: O(1) for both
Both push and pop operate on the top of the stack only, requiring no traversal, making both O(1) constant time.
Question 3: How can a queue be implemented using two stacks with amortized O(1) enqueue and dequeue?
- Enqueue to stack1; dequeue pops from stack2, transferring from stack1 when stack2 is empty (Correct answer)
- Use one stack for each direction and alternate operations
- Always reverse one stack after each operation
- Store elements sorted across both stacks
Correct answer: Enqueue to stack1; dequeue pops from stack2, transferring from stack1 when stack2 is empty
Elements are pushed to stack1 on enqueue; on dequeue, if stack2 is empty, all elements are moved from stack1 to stack2, reversing the order to produce FIFO behavior.
Question 4: What is a monotonic stack used for?
- Implementing a priority queue
- Maintaining elements in strictly increasing or decreasing order to solve next-greater-element problems (Correct answer)
- Balancing parentheses in expressions
- Evaluating postfix expressions
Correct answer: Maintaining elements in strictly increasing or decreasing order to solve next-greater-element problems
A monotonic stack maintains a sorted sequence by popping elements that violate the ordering invariant, enabling O(n) solutions to next-greater and next-smaller problems.
Question 5: Which algorithm uses a stack to evaluate postfix (Reverse Polish Notation) expressions?
- Push numbers, pop two operands when an operator is found, push result (Correct answer)
- Use two stacks: one for numbers, one for operators
- Convert to infix first then evaluate
- Recursively evaluate each operator
Correct answer: Push numbers, pop two operands when an operator is found, push result
Postfix evaluation scans left to right: push operands onto a stack; when an operator is encountered, pop two operands, apply the operator, and push the result.
Question 6: What is the main advantage of a circular queue over a linear array-based queue?
- Faster enqueue time
- Reuses freed space at the front without shifting elements (Correct answer)
- Supports priority ordering
- Eliminates the need for a size variable
Correct answer: Reuses freed space at the front without shifting elements
A circular queue wraps the rear pointer around to the front when it reaches the array end, reusing vacated front positions without element shifting.
Data Structures Stacks and Queues 1
Which real-world scenario best illustrates LIFO (Last In, First Out) behavior?