24/180: Implement Queue using Stacks

So basically we have two methods by which we can implement queue using stacks.

1. By Making Enqueue operation costly
2. By Making Dequeue operation costly

Let’s see which one we should choose.

Method 1: By making enqueue operation costly. This method makes the oldest element always at the top of stack 1 so that dequeue operation just pops from stack1. To put the element at the top of stack1, stack2 enqueue(q, x)

1. While stack1 is not empty, push everything from stack1 to stack2.
2. Push x to stack1 (assuming size of stacks is unlimited)
3. Push everything back to stack 1.
4. Here time complexity will be O(n). dequeue(q), if stack1 is empty then error. Pop an item from stack1 and return it. Here time complexity will be O(1)

static class Queue{
   static Stack<Integer> s1 = new Stack<Integer>();
   static Stack<Integer> s2 = new Stack<Integer>();
   static void enQueue(int x){
       while(!s1.isEmpty()){
         s2.push(s1.pop());
       }
       s1.push(x);
       while(!s2.isEmpty()){
          s1.push(s2.pop());
       }
    }
   static int deQueue(){
     if(s1.isEmpty()){
        System.out.println("Q is empty");
        System.exit(0);
     }
     int x = s1.peek();
     s1.pop();
     return x;
    }
}
Time complexity:
Push Operation O(N)
Pop Operation O(1)
Auxiliary Space O(N)

Method 2 : By making deQueue operation costly. In enqueue element is entered at the top of stack 1. In dequeue operation if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.

enqueue(q,x)

1. Push x to stack1 (assuming size of stack is unlimited). Here time complexity will be o(1)

dequeue(q)

1. If both stacks are empty then error.
2. If stack2 is empty, while stack 1 is not empty, push everything from stack1 to stack 2.
3. Pop the element from stack2 and return it.

Method 2 is better that method 1 as it moves all the elements twice in enqueue operation, while method 2 moves the element once, and moves element only if stack 2 is empty. So amortized complexity of dequeue operation becomes o(1)

public class Queue{
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    static void push(Stack<Integer> top_ref, int new_data){
         top_ref.push(new_data);
    }
    static int pop(Stack<Integer> top_ref){
       if(top_ref.isEmpty()){
          System.out.println("Stack Underflow");
       }  
       return top_ref.pop(); 
    }
    static void enQueue(Queue q, int x){
     push(q.stack1, x);
    }
    static int deQueue(Queue q){
     int x;
     if(q.stack1.isEmpty() && q.stack2.isEmpty()){
      System.out.println("Q is empty");
      System.exit(0);
      }
     if(q.stack2.isEmpty()){
        while(!q.stack1.isEmpty()){
         x = pop(q.stack1);
         push(q.stack2, x);
        }
       x = pop(q.stack2);
       return x;
    }
}