We are trying to use two stacks to implement a queue. Name thetwo stacks as E and D. We will enqueue into E and dequeue from D.To implement enqueue(e), simply call E.push(e). To implementdequeue(), simply call D.pop(), provided that D is not empty. If Dis empty, iteratively pop every element from E and push it onto D,until E is empty, and then call D.pop().
- Considering the worst case running time, what is theperformance in terms of big Oh of an enqueue operation? What is theperformance in terms of big Oh of a dequeue operation?
- To complete one task, we need perform n operations, halfenqueue and half dequeue (assume no dequeue from empty queue). Whatis the worst case overall running time (big oh) for the wholetask?
