Queue using Stacks

Difficulty Level Easy
Frequently asked in Accolite Adobe Amazon DE Shaw Flipkart Goldman Sachs InfoEdge InMobi MakeMyTrip MAQ Microsoft Morgan Stanley Oracle Walmart Labs
Queue StackViews 3079

In queue using a stack problem, we have to implement the following functions of a queue using the standard functions of stack data structure,

  1. Enqueue: Add an element to the end of the queue
  2. Dequeue: Remove an element from the start of the queue

Example

Input:
Enqueue(5)
Enqueue(11)
Enqueue(39)
Dequeue()  // Returns 5
Enqueue(12)
Dequeue()  // Returns 11
Dequeue()  // Returns 39
Output:
5
11
39

Algorithm

A queue can be implemented using two stacks, there are two ways to implement a queue using stacks, first by making enqueue operation costly and second by making dequeue operation costly.

Method 1 (Costly Enqueue Operation) for Queue using Stacks

Create two stack st1 and st2. Visualize the queue in st1, the top of st1 is front of the queue, and moving downwards in st1 is similar to moving ahead in the queue.

Enqueue(x)

Pushing x to the rear of the queue is the same as pushing x to the bottom of stack st1.

  1. Remove all the elements from st1 and push them to st2.
  2. Push x to st2.
  3. Remove all the elements from st2 and push them back to st1.

Time Complexity = O(n)A

Queue using Stacks

Dequeue()

Removing an element from the front of the queue is similar to removing the top of stack st1. So if st1 is not empty pop the top of st1 and return.

Time Complexity= O(1)

Overall Space Complexity of Method 1 = O(n)

JAVA Code for Queue using Stacks

import java.util.Stack;

public class QueueUsingStacks {
    // Costly Enqueue Operation
    private static Stack<Integer> st1;
    private static Stack<Integer> st2;

    private static void enqueue(int x) {
        // remove all the elements from st1 and push them to st2
        while (!st1.isEmpty()) {
            st2.push(st1.pop());
        }

        // push x to st2
        st2.push(x);

        // remove all the elements from st2 and push them back to st1
        while (!st2.isEmpty()) {
            st1.push(st2.pop());
        }
    }

    private static int dequeue() {
        if (st1.isEmpty()) {
            return -1;
        }

        // if st1 is not empty return and remove the top of st1
        return st1.pop();
    }

    public static void main(String[] args) {
        st1 = new Stack<>();
        st2 = new Stack<>();
        
        // Example
        enqueue(5);
        enqueue(11);
        enqueue(39);
        System.out.println(dequeue());
        enqueue(12);
        System.out.println(dequeue());
        System.out.println(dequeue());
    }
}
5
11
39

C++ Code

#include<bits/stdc++.h> 
using namespace std;

// Costly Enqueue Operation

stack<int> st1;
stack<int> st2;

void enqueue(int x) {
    // remove all the elements from st1 and push them to st2
    while (!st1.empty()) {
        int curr = st1.top();
        st1.pop();
        st2.push(curr);
    }
    
    // push x to st2
    st2.push(x);
    
    // remove all the elements from st2 and push them back to st1
    while (!st2.empty()) {
        int curr = st2.top();
        st2.pop();
        st1.push(curr);
    }
}

int dequeue() {
    if (st1.empty()) {
        return -1;
    }
    
    // if st1 is not empty return and remove the top of st1
    int top = st1.top();
    st1.pop();
    return top;
}

int main() {
    // Example
    enqueue(5);
    enqueue(11);
    enqueue(39);
    cout<<dequeue()<<endl;
    enqueue(12);
    cout<<dequeue()<<endl;
    cout<<dequeue()<<endl;
    
    return 0;
}
5
11
39

Method 2 (Costly Dequeue Operation) for Queue using Stacks

Create two stacks st1 and st2. Visualize queue in st1, the top of st1 represents the rear of the queue, moving upwards in st1 is similar to moving ahead in the queue.

Enqueue(x)

Pushing x to the rear of the queue is similar to pushing x to the top of stack_st1. So push x to top of st1.

Time Complexity= O(1)

Dequeue()

Removing an element from the front of the queue is similar to removing an element from the bottom of stack_st1. So, if st1 is not empty,

  1. Remove all the elements from st1 and push them to st2.
  2. Pop the top of st2 and store it in a variable top.
  3. Remove all the elements from st2 and push them back to st1.
  4. Return top

Time Complexity= O(n)

Queue using Stacks

Overall Space Complexity of Method 2 = O(n)

JAVA Code

import java.util.Stack;

public class QueueUsingStacks {
    // Costly Dequeue Operation
    private static Stack<Integer> st1;
    private static Stack<Integer> st2;

    private static void enqueue(int x) {
        // push x to top of st1
        st1.push(x);
    }

    private static int dequeue() {
        if (st1.isEmpty()) {
            return -1;
        }

        // if st1 is not empty
        // remove all the elements from st1 and push them to st2
        while (!st1.isEmpty()) {
            st2.push(st1.pop());
        }

        // pop the top of st2 and store it in a variable top
        int top = st2.pop();

        // remove all the elements from st2 and push them back to st1
        while (!st2.isEmpty()) {
            st1.push(st2.pop());
        }
        
        // return top
        return top;
    }

    public static void main(String[] args) {
        st1 = new Stack<>();
        st2 = new Stack<>();

        // Example
        enqueue(5);
        enqueue(11);
        enqueue(39);
        System.out.println(dequeue());
        enqueue(12);
        System.out.println(dequeue());
        System.out.println(dequeue());
    }
}
5
11
39

C++ Code

#include<bits/stdc++.h> 
using namespace std;

// Costly Dequeue Operation

stack<int> st1;
stack<int> st2;

void enqueue(int x) {
    // push x to top of st1
    st1.push(x);
}

int dequeue() {
    if (st1.empty()) {
        return -1;
    }
    
    // if st1 is not empty
    // remove all the elements from st1 and push them to st2
    while (!st1.empty()) {
        int curr = st1.top();
        st1.pop();
        st2.push(curr);
    }
    
    // pop the top of st2 and store it in a variable top
    int top = st2.top();
    st2.pop();
    
    // remove all the elements from st2 and push them back to st1
    while (!st2.empty()) {
        int curr = st2.top();
        st2.pop();
        st1.push(curr);
    }
    
    // return top
    return top;
}

int main() {
    // Example
    enqueue(5);
    enqueue(11);
    enqueue(39);
    cout<<dequeue()<<endl;
    enqueue(12);
    cout<<dequeue()<<endl;
    cout<<dequeue()<<endl;
    
    return 0;
}
5
11
39

Reference1     reference2

Translate »