Describe how to implement a queue using two stacks so that t

Describe how to implement a queue using two stacks, so that the amortized running time for dequeue and enqueue is O(1), assuming that the stacks support constant-time push, pop, and size methods. What is the worst-case running time of the enqueue() and dequeue() methods in this case?

Solution

Implementation of a queue using two stacks:
A queue using two stacks such that the amortized running time for dequeue and enqueue is O(1) is implemented as

Algorithm Eneque(e):

                Stack1.push()

Algorithm Deque():

Algorithm Eneque(e):

                Stack1.push(e)

Algorithm Deque():

                if stack2.isEmpty() then

                                while stack1.size() > 1 do

                                                e = stack1.pop()

                                                stack2.push(e)

                                e = stack1.pop()

                                return e

else

e = stack2.pop()

                                return e

From the above it is obvious that Eneque() operation is O(1). If the stack2 is not empty then Deque() operation will take O(1) time and when stack2 is empty it takes O(n) time.

Thus, total time of n pop() operations is 1 + 1 + .. + 1 +n    where there are n ‘1’s

Therefore, amortized time is T(n)/n

                                                i.e. 2n/n

Thus, amortized time for deque is O(1).