Question

Describe how to implement queue adt using two stacks as instant variables, such that all queue operations execute in amortized o(1) time. give a formal proof of the amortized bound.

Answer 1

Enqueue:

Push the new element onto inbox

Dequeue:

If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox

Pop and return the top element fromoutbox

Using this method, each element will be in each stack exactly once - meaning each element will be pushed twice and popped twice, giving amortized constant time operations.