It is possible to implement a deque using two stacks stack1 and stack2, by implementing the functions in the following manner:
pushback (x): push x on stack1.
pushfront (x): push x on stack2.
popfront (): if stack2 is not empty, then pop from it. Otherwise, pop the entire contents of stack1, pushing each one onto stack2. Now pop from stack2.
popback (): if stack1 is not empty, then pop from it. Otherwise, pop the entire contents of stack2, pushing each one onto stack1. Now pop from stack1.
1 2 3 4 5 6 7 8 9 10 11
Starting with an empty deque, indicate the contents of stack1 and stack2 after each of the following operations have occurred. Clearly indicate the top and bottom of each stack:
What is the worst-case runtime of each of the four functions listed above in the 2-stack implementation?
What is the amortized runtime per function call, if a user is not allowed to use popfront? What is the amortized runtime per function call, if a user is not allowed to use popback?
What sequence of operations can lead to a very poor amortized runtime, when all four functions given above can be used? What is the amortized runtime per function call?