Implement Stack using Two Queues

Question

A similiar question was asked earlier there, but the question here is the reverse of it, using two queues as a stack. The question...

Given two queues with their standard operations (enqueue, dequeue, isempty, size), implement a stack with its standard operations (pop, push, isempty, size).

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.

I am interested in the algorithm more than any specific language implementations. However, I welcome solutions expressed in languages which I am familiar (Java, C#, Python, VB, Javascript, Php). Thanks in advance.

Answer 1

Version A:

• push:
  • enqueue in queue1
• pop:
  • while size of queue1 is bigger than 1, pipe dequeued items from queue1 into queue2
  • dequeue and return the last item of queue1, then switch the names of queue1 and queue2

Version B:

• push:
  • enqueue in queue2
  • enqueue all items of queue1 in queue2, then switch the names of queue1 and queue2
• pop:
  • deqeue from queue1

Answer 2

The easiest (and maybe only) way of doing this is by pushing new elements into the empty queue, and then dequeuing the other and enqeuing into the previously empty queue. With this way the latest is always at the front of the queue. This would be version B, for version A you just reverse the process by dequeuing the elements into the second queue except for the last one.

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 |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Answer 3

Here's my answer - where the 'pop' is inefficient. Seems that all algorithms that come immediately to mind have N complexity, where N is the size of the list: whether you choose to do work on the 'pop' or do work on the 'push'

The algorithm where lists are traded back and fourth may be better, as a size calculation is not needed, although you still need to loop and compare with empty.

you can prove this algorithm cannot be written faster than N by noting that the information about the last element in a queue is only available through knowing the size of the queue, and that you must destroy data to get to that element, hence the 2nd queue.

The only way to make this faster is to not to use queues in the first place.

from data_structures import queue

class stack(object):
    def __init__(self):
        q1= queue 
        q2= queue #only contains one item at most. a temp var. (bad?)

    def push(self, item):
        q1.enque(item) #just stick it in the first queue.

    #Pop is inefficient
    def pop(self):
        #'spin' the queues until q1 is ready to pop the right value. 
        for N 0 to self.size-1
            q2.enqueue(q1.dequeue)
            q1.enqueue(q2.dequeue)
        return q1.dequeue()

    @property
    def size(self):
        return q1.size + q2.size

    @property
    def isempty(self):
        if self.size > 0:
           return True
        else
           return False

Answer 4

I don't think that's write FlipMCf. Your "spin" doesn't reverse the order.

Answer 5

Curious, why 2 queues? can't we use circular queue and just change pointers?

Answer 6

Thanks a lot for this answer. Best approach one can have..