Data Structures Stacks and Queues 2

Question 1

What does a deque (double-ended queue) support that a standard queue does not?

Accepted Answer

Insertion and deletion at both front and back

Answer

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?

Accepted Answer

An implicit call stack drives recursive DFS; iterative DFS uses an explicit stack

Answer

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?

Accepted Answer

O(n)

Answer

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?

Accepted Answer

Validating balanced parentheses in an expression

Answer

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?

Accepted Answer

O(V)

Answer

BFS stores at most O(V) vertices in the queue at any time since each vertex is enqueued at most once.

Data Structures Practice Test

Data Structures Practice Test

Data Structures Stacks and Queues 2