A double-ended queue supports operations like adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue) and removeRear(removing item from the bottom 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? (Assume ‘m’ to be the size of the stack and ‘n’ to be 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)
Answer:B
A double-ended queue supports operations like adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue) and removeRear(removing item from the bottom 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? (Assume ‘m’ to be the size of the stack and ‘n’ to be 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)
Explanation: addFront is nothing more than a standard push process. The operation of pushing is of O. (1). AddRear, on the other hand, is O(n) because it requires two push(pop()) operations on all stack elements.