Stacks & Queues — Chapter Quiz · Data Structures & Algorithms

Question 1

1

Which problem is a monotonic stack particularly well suited for?

ABinary search on a sorted arrayBFinding the next greater element for every element in O(n)CComputing prefix sumsDMerging two sorted arrays

A monotonic (decreasing) stack keeps candidate elements while popping those that have found their "next greater" answer. Each element is pushed and popped at most once — O(n) total.

Question 2

2

Why is using Array.shift() for a queue in JavaScript problematic?

Ashift() is not available on arraysBshift() is O(n) because every element must be re-indexed after removal from the frontCshift() only works on sorted arraysDshift() mutates the original array prototype

Removing from the front of a JS array requires shifting all remaining elements down by one index. For large queues this becomes a bottleneck. Use a linked-list queue or a circular buffer for O(1) dequeue.

Question 3

3

How does the 'queue via two stacks' technique achieve amortized O(1) enqueue and dequeue?

AElements are sorted on enqueueBOne stack handles enqueue; the other handles dequeue. When the dequeue stack is empty, all elements are moved from the enqueue stack — each element is moved at most onceCBoth stacks are always kept in sync on every operationDA hash map is used to avoid O(n) movement

Each element crosses from the enqueue stack to the dequeue stack exactly once. The total cost of n operations is O(n), so the amortized per-operation cost is O(1).

Question 4

4

A deque (double-ended queue) supports:

AO(1) insertions and deletions at both the front and the backBO(1) random access by indexCO(log n) insertions at the front onlyDAutomatic sorting on every insertion

A deque generalises both a stack and a queue. It supports push and pop from either end in O(1), making it useful for sliding window maximum/minimum problems.

Question 5

5

Which data structure is best for implementing a browser's forward/back navigation history?

AMin-heapBQueue (FIFO)CStack (LIFO)DHash map

Each "back" press pops the current URL off a back-stack. Each new navigation pushes onto the back-stack. A second stack can manage the forward history. This is the classic two-stack browser history pattern.

Question 6

6

A circular buffer (ring buffer) of fixed capacity N can perform both enqueue and dequeue in O(1) time without shifting elements.

TTrueFFalse

A circular buffer uses two indices, head and tail, that wrap around modulo N. Enqueue increments tail; dequeue increments head. No data movement is needed — O(1) for both operations.

Question 7

7

In the classic 'valid parentheses' problem, you push opening brackets onto a stack and ___ the top when you see a closing bracket.

When a closing bracket arrives, pop the top of the stack and check that it matches the expected opener. If the stack is empty at the end, all brackets were balanced.

Question 8

8

Which of the following are valid use-cases for a stack? (Select all that apply)

Select all that apply.

ATracking function call frames at runtime (the call stack)BUndo/redo functionality in a text editorCBreadth-first search traversal of a graphDEvaluating postfix (RPN) expressions

Stacks power call frames, undo history, and postfix evaluation. BFS uses a queue (FIFO), not a stack — DFS uses a stack.

Test what you learned.