Wednesday, February 19, 2014

Implement a stack using 2 queues

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.
Method 1 - When push is efficient and pop is costly
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