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.
  1. Push :
  • Add the input x to the right end of the deque q1.
  1. 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.
  1. 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.
  1. 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

 



Thanks for feedback.



Read More....
Reverse a stack using recursion
Stack Introduction Program
Balanced Brackets: Check for balanced brackets in an expression