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() n assuming m is the size of the stack and is the number of elements?

1. AO(m) and O(n)
2. BO(1) and O(n)
3. CO(n) and O(1)
4. DO(n) and O(m)

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. O(1) and O(n)

Explanation

Use one stack whose top is the front. AddFront is a single push, O(1). AddRear must move all n elements to another stack, push, and move them back: O(n).