Data Structures Stacks and Queues 2 — Questions and Answers
Question 1: What does a deque (double-ended queue) support that a standard queue does not?
- O(1) random access
- Insertion and deletion at both front and back (Correct answer)
- Priority-based ordering
- Infinite capacity
Correct answer: Insertion and deletion at both front and back
A deque allows O(1) insertion and deletion at both ends, making it more flexible than a standard queue which only allows rear insertion and front deletion.
Question 2: How is a stack used in the depth-first search (DFS) of a graph?
- DFS uses a queue, not a stack
- A stack stores visited nodes to track the traversal frontier
- An implicit call stack drives recursive DFS; iterative DFS uses an explicit stack (Correct answer)
- A stack stores adjacency lists for each node
Correct answer: An implicit call stack drives recursive DFS; iterative DFS uses an explicit stack
Recursive DFS uses the program's call stack implicitly; iterative DFS explicitly pushes unvisited neighbors onto a stack to simulate the same behavior.
Question 3: What is the time complexity of finding the maximum element in a sliding window of size k using a deque-based algorithm?
- O(n log n)
- O(n×k)
- O(n) (Correct answer)
- O(k log n)
Correct answer: O(n)
The deque-based sliding window maximum algorithm processes each element at most twice (once added, once removed), achieving O(n) overall time.
Question 4: Which problem can be solved using a stack to track unmatched opening brackets?
- Finding the shortest path in a graph
- Validating balanced parentheses in an expression (Correct answer)
- Sorting an array in place
- Finding the median of a data stream
Correct answer: Validating balanced parentheses in an expression
Push opening brackets onto a stack; when a closing bracket is encountered, pop and verify it matches the top — the expression is balanced if the stack is empty at the end.
Question 5: What is the space complexity of BFS using a queue on a graph with V vertices and E edges?
- O(1)
- O(E)
- O(V) (Correct answer)
- O(V+E)
Correct answer: O(V)
BFS stores at most O(V) vertices in the queue at any time since each vertex is enqueued at most once.
Question 6: How does a priority queue differ from a standard queue?
- Priority queue allows duplicate values; standard queue does not
- Elements are dequeued by priority rather than arrival order (Correct answer)
- Priority queue uses a stack internally
- Priority queue only supports integer elements
Correct answer: Elements are dequeued by priority rather than arrival order
A priority queue dequeues the element with the highest (or lowest) priority first, regardless of when it was inserted, unlike a FIFO queue.
Data Structures Stacks and Queues 2
What does a deque (double-ended queue) support that a standard queue does not?