Question

We are trying to use two stacks to implement a queue. Name the two stacks as E and D. We will enqueue into E and dequeue from D. To implement enqueue(e), simply call E.push(e). To implement dequeue(), simply call D.pop(), provided that D is not empty. If D is empty, iteratively pop every element from E and push it onto D, until E is empty, and then call D.pop().

1. Considering the worst case running time, what is the performance in terms of big Oh of an enqueue operation? What is the performance in terms of big Oh of a dequeue operation?
2. To complete one task, we need perform n operations, half enqueue and half dequeue (assume no dequeue from empty queue). What is the worst case overall running time (big oh) for the whole task?

Answer 1

Enqueue operation will have a time complexity of O(1). This operation will take constant time because every time the function enqueue is called, we simply have to call push operation on stack E, which is a constant time operation.

Whereas in the case of the Dequeue operation, in the worst case, we will have pop all the elements from the stack E and push them into the stack D. Assuming there is n number of elements in the stack E, popping all of them will take O(n) time (constant time(1) * n).

Now let us consider the case of performing n operations, where half of the are enqueue and other half are dequeue. Performing n/2 enqueue operations will take (n/2)*1 time i.e. O(n/2).

For (n/2) dequeue operations, it has been mentioned that none of them is performed on an empty queue. In the worst case, time complexity will look like O(n + (n-1)+(n-2)+(n-3)+.........1+0). It is because when for the first time dequeue is called, we will pop one element from stack D so next time when deque is called, we will have one element less to push into stack D(considering that stack D is empty). So the above time complexity can be written as O(n²). So overall, we can say that the worst case time complexity for the provided case will be O(n²).