Implement Stack using Two Queues

Version A (efficient push):

• 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 (efficient pop):

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

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

queue<int> q1, q2;
int i = 0;

void push(int v) {
  if( q1.empty() && q2.empty() ) {
     q1.push(v);
     i = 0;
  }
  else {
     if( i == 0 ) {
        while( !q1.empty() ) q2.push(q1.pop());
        q1.push(v);
        i = 1-i;
     }
     else {
        while( !q2.empty() ) q1.push(q2.pop());
        q2.push(v);
        i = 1-i;
     }
  }
}

int pop() {
   if( q1.empty() && q2.empty() ) return -1;
   if( i == 1 ) {
      if( !q1.empty() )
           return q1.pop();
      else if( !q2.empty() )
           return q2.pop();
   }
   else {
      if( !q2.empty() )
           return q2.pop();
      else if( !q1.empty() )
           return q1.pop();
   }
}

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

As has been mentioned, wouldn't a single queue do the trick? It's probably less practical but is a bit slicker.

push(x):
enqueue(x)
for(queueSize - 1)
   enqueue(dequeue())

pop(x):
dequeue()

Here's one more solution:

for PUSH : -Add first element in queue 1. -When adding second element and so on, Enqueue the element in queue 2 first and then copy all the element from queue 1 to queue2. -for POP just dequeue the element from the queue from you inserted the last element.

So,

public void push(int data){
if (queue1.isEmpty()){
    queue1.enqueue(data);
}  else {
queue2.enqueue(data);
while(!queue1.isEmpty())
Queue2.enqueue(queue1.dequeue());
//EXCHANGE THE NAMES OF QUEUE 1 and QUEUE2

} }

public int pop(){
int popItem=queue2.dequeue();
return popItem;
}'

There is one problem, I am not able to figure out, how to rename the queues???

Below is a very simple Java solution which supports the push operation efficient.

Algorithm -

1. Declare two Queues q1 and q2.

2. Push operation - Enqueue element to queue q1.

3. Pop operation - Ensure that queue q2 is not empty. If it is empty, then dequeue all the elements from q1 except the last element and enqueue it to q2 one by one. Dequeue the last element from q1 and store it as the popped element. Swap the queues q1 and q2. Return the stored popped element.

4. Peek operation - Ensure that queue q2 is not empty. If it is empty, then dequeue all the elements from q1 except the last element and enqueue it to q2 one by one. Dequeue the last element from q1 and store it as the peeked element. Enqueue it back to queue q2 and swap the queues q1 and q2. Return the stored peeked element.

Below is the code for above algorithm -

class MyStack {

    java.util.Queue<Integer> q1;
    java.util.Queue<Integer> q2;
    int SIZE = 0;

    /** Initialize your data structure here. */
    public MyStack() {
        q1 = new LinkedList<Integer>();
        q2 = new LinkedList<Integer>();

    }

    /** Push element x onto stack. */
    public void push(int x) {
        q1.add(x);
        SIZE ++;

    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        ensureQ2IsNotEmpty();
        int poppedEle = q1.remove();
        SIZE--;
        swapQueues();
        return poppedEle;
    }

    /** Get the top element. */
    public int top() {
        ensureQ2IsNotEmpty();
        int peekedEle = q1.remove();
        q2.add(peekedEle);
        swapQueues();
        return peekedEle;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();

    }

    /** move all elements from q1 to q2 except last element */
    public void ensureQ2IsNotEmpty() {
        for(int i=0; i<SIZE-1; i++) {
            q2.add(q1.remove());
        }
    }

    /** Swap queues q1 and q2 */
    public void swapQueues() {
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
}

Efficient solution in C#

public class MyStack {
    private Queue<int> q1 = new Queue<int>();
    private Queue<int> q2 = new Queue<int>();
    private int count = 0;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
    }

    /**
     * Push element x onto stack.
     */
    public void Push(int x) {
        count++;
        q1.Enqueue(x);
        while (q2.Count > 0) {
            q1.Enqueue(q2.Peek());
            q2.Dequeue();
        }
        var temp = q1;
        q1 = q2;
        q2 = temp;
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int Pop() {
        count--;
        return q2.Dequeue();
    }

    /**
     * Get the top element.
     */
    public int Top() {
        return q2.Peek();
    }

    /**
     * Returns whether the stack is empty.
     */
    public bool Empty() {
        if (count > 0) return false;
        return true;
    }
}

template <typename T>
class stackfmtoq {
    queue<T> q1;
    queue<T> q2;
public:
    void push(T data) {
        while (!q2.empty()) {
            q1.push(q2.front());
            q2.pop();
        }
        q2.push(data);
        while (!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }
    }
    T pop() {
        if (q2.empty()) {
            cout << "Stack is Empty\n";
            return NULL;
        }
        T ret = q2.front();
        q2.pop();
        return ret;
    }
    T top() {
        if (q2.empty()) return NULL;
        return q2.front();
    }
};

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class ImplementationOfStackUsingTwoQueue {

    private static Deque<Integer> inboxQueue = new LinkedList<>();
    private static Queue<Integer> outboxQueue = new LinkedList<>();
    
    public void pushInStack(Integer val){
        inboxQueue.add(val);
    }
    
    public void popFromStack(){
        
        if(outboxQueue.isEmpty()){
            while(!inboxQueue.isEmpty()){
                outboxQueue.add(inboxQueue.pollLast());
            }
        }
    }
    
    public static void main(String[] args) {
        
        ImplementationOfStackUsingTwoQueue obj = new ImplementationOfStackUsingTwoQueue();
        
        obj.pushInStack(1);
        obj.pushInStack(2);
        obj.pushInStack(3);
        obj.pushInStack(4);
        obj.pushInStack(5);
        System.out.println("After pushing the values in Queue" + inboxQueue);
        
        obj.popFromStack();
        System.out.println("After popping the values from Queue" + outboxQueue);    
    }
}

A different approach which is easy to understand and implement could be:

1. Add operation --> Always add elements in the empty queue and after adding that element move all other elements from other non-empty queue to this queue.
2. Pop operation --> whichever queue is not empty perform remove/poll on it and return.
3. Top operation --> Whichever queue is not empty perform peek on it and return.
4. Print --> Whichever queue is not empty print it.