This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/implement-stack-using-queues/.
Problem : Implement a stack using 2 queues and standard operations (enqueue, dequeue, isempty, size)Solution
A similar problem has been blogged here, where we implement a queue using 2 stacks.
There should be TWO versions of the solution.
- Version A: The stack should be efficient when pushing an item.
- Version B: The stack should be efficient when popping an item.
In push operation, the new element is always enqueued to q1. In pop() operation, if q2 is empty then all the elements except the last, are moved to q2. Finally the last element is dequeued from q1 and returned.
push() : enqueue in queue1 pop() : while (size of queue1 is bigger than 1) pipe de-queued items from queue1 into queue2 de-queue and return the last item of queue1, then switch the names of queue1 and queue2
Method 2 - When pop is efficient, but push is costly
push(): enqueue in queue2 enqueue all items of queue1 in queue2, then switch the names of queue1 and queue2 pop(): deqeue from queue1
Example of Method 1
Lets say we want to insert 1,2,3.
Step 0:
"Stack" +---+---+---+---+---+ | | | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | | | | | | | | | | | | +---+---+---+---+---+ +---+---+---+---+---+
Step 1:
"Stack" +---+---+---+---+---+ | | | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | 1 | 2 | 3 | | | | | | | | | +---+---+---+---+---+ +---+---+---+---+---+
Step 2:While popping
"Stack" +---+---+---+---+---+ | 3 | | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | 1 | 2 | | | | | 3 | | | | | +---+---+---+---+---+ +---+---+---+---+---+
Step 3:
"Stack" +---+---+---+---+---+ | 3 | 2 | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | 1 | | | | | | 3 | 2 | | | | +---+---+---+---+---+ +---+---+---+---+---+
and so on. Finally we take out 1, and put it in B.
Example of Method 2
Lets say we want to insert 1,2,3.
Step 0:
"Stack" +---+---+---+---+---+ | | | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | | | | | | | | | | | | +---+---+---+---+---+ +---+---+---+---+---+
Step 1:
"Stack" +---+---+---+---+---+ | 1 | | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | 1 | | | | | | | | | | | +---+---+---+---+---+ +---+---+---+---+---+
Step 2:
"Stack" +---+---+---+---+---+ | 2 | 1 | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | | | | | | | 2 | 1 | | | | +---+---+---+---+---+ +---+---+---+---+---+
Step 3:
"Stack" +---+---+---+---+---+ | 3 | 2 | 1 | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | 3 | 2 | 1 | | | | | | | | | +---+---+---+---+---+ +---+---+---+---+---+
Reference - stackoverflow.
Thanks.
0 comments:
Post a Comment