A double‐ended queue (dequeue) supports adding and removing items from both…
2021
A double‐ended queue (dequeue) supports adding and removing items from both the ends of the queue. The operations supported by dequeue are AddFront(adding item to front of the queue), AddRear(adding item to the rear of the queue), RemoveFront(removing item from the front of the queue), and RemoveRear(removing item from the rear of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What’s the time complexity of performing AddFront() and AddRear() assuming m is the size of the stack and n is the number of elements?
- A.
\( O(m) \ and \ O(n)\) - B.
\(O(1) \ and \ O(n)\) - C.
\(O(n) \ and \ O(1)\) - D.
\(O(n) \ and \ O(m)\)
Attempted by 175 students.
Show answer & explanation
Correct answer: B
Answer: AddFront is O(1) and AddRear is O(n) where n is the number of elements.
Implementation idea (using only push and pop):
AddFront(x): Push x onto the top of the main stack. Time: O(1).
AddRear(x): To insert x at the bottom, pop all elements from the main stack onto a temporary stack until the main stack is empty, push x onto the now-empty main stack, then pop all elements from the temporary stack back onto the main stack. Time: O(n), where n is the number of elements moved.
Notes:
The cost of AddFront depends only on a single push and is therefore constant time.
The cost of AddRear is linear in the number of existing elements because each element must be moved twice (once off the main stack and once back).
If m refers to stack capacity and n refers to the current number of elements, the time complexity should be expressed in terms of n (the number of elements actually moved).
A video solution is available for this question — log in and enroll to watch it.