FIFO queue using Stacks
You have two stacks available to you; now you have to implement a FIFO queue using the two stack's and support Enqueue and Dequeue operations in the best possible time complexity. You can assume that the Stack supports push(), pop(), peep() and size() opertions and they are available to you
use two stacks A and B.
ReplyDeleteuse A for push and B for pop except when B is empty,then pop all element from A and push in B.The last left element is element to be popped.
Incoming items get pushed onto stack1, and are all popped off onto stack2 when stack2 is empty. So the first item gets pushed onto stack1, the immediately popped off and pushed onto stack2, ready for output. Subsequent items stack up on stack1 until stack2 is popped, at which point the last item goes on stack2, then the next-to-last, and so on until stack1 is empty again. Now all of the items are restacked on stack2, with the newest at the bottom and the oldest at the top. New pushes continue to build up on stack1, waiting for stack2 to become empty again, and stack2 just produces the items in the original order until it's empty, at which point we repeat the unstack-restack process.
ReplyDelete