Implement a stack using queue

A stack is a linear last-in-first-out (LIFO) data structure where as a queue is a first-in-first-out (FIFO) data structure.

In this problem we have to implement a stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Intuition

We will be using a deque which is a type of queue to implement the stack. Deque or Double Ended Queue is a type of queue in which insertion and removal of elements can either be performed from the front or the rear.

Approach

1. Constructor :

• Create two empty deques q1 and q2.

2. Push :

• Add the input x to the right end of the deque q1.

3. Pop :

• While the length of the deque q1 is greater than 1

• Remove an element from the left end of the deque q1.
• Add the removed element to the right end of the deque q2.

• Remove the leftmost element of the deque q1 and swap the contents of q1 and q2.

4. Top :

• While length of q1 is greater than 1:

• Remove an element from the left end of the deque q1.
• Add the removed element to the right end of the deque q2.

• Retrieve and store the leftmost element of dequeue q1.
• Remove the top element from q1 and immediately append it to the right end of q2.
• Swap the contents of q1 and q2.

5. Empty :

• Check the length of q1. If the length of q1 is equal to 0 then return true, else return false.

Complexities

Time Complexity

• Push : O(1)
• Pop : O(n)
• Top : O(n)
• Empty : O(1)

Space Complexity: O(n)

Java Code

import java.util.*;

class StackUsingQueue{

    static class MyStack {

        private Queue<Integer> q1;
        private Queue<Integer> q2;

        public MyStack() {
            q1 = new ArrayDeque<>();
            q2 = new ArrayDeque<>();
        }


        public void push(int x) {
            q1.add(x);
        }


        public int pop() {

            while (q1.size() > 1) {
                q2.add(q1.poll());
            }

            int poppedVal = q1.poll();
            Queue<Integer> temp = q1;

            q1 = q2;
            q2 = temp;

            return poppedVal;
        }


        public int top() {

            while (q1.size() > 1) {
                q2.add(q1.poll());
            }


            int topVal = q1.peek();
            q2.add(q1.poll());
            Queue<Integer> temp = q1;

            q1 = q2;
            q2 = temp;

            return topVal;
        }


        public boolean empty() {
            return q1.isEmpty();
        }


        public int size() { return q1.size();}


    }


    public static void main(String[] args){

        MyStack s = new MyStack();

        s.push(1);
        s.push(2);
        s.push(3);

        System.out.println("current size: " + s.size());
        System.out.println("Top is: " + s.top());

        System.out.println("Popped " + s.pop());

        System.out.println("Top is: " + s.top());

        System.out.println("Popped " + s.pop());

        System.out.println("Top is: " + s.top());
        System.out.println("current size: " + s.size());

    }

}

Output

current size: 3
Top is: 3
Popped 3
Top is: 2
Popped 2
Top is: 1
current size: 1