Implement a stack using single queue

Difficulty Level Easy
Frequently asked in Amazon Fourkites Google Infosys MAQ Microsoft
Queue StackViews 3237

Problem Statement

The problem “Implement a stack using single queue” asks us to implement a stack (LIFO) data structure using a queue (FIFO) data structure.

Here LIFO means Last In First Out while FIFO means First In First Out.

Implement a stack using single queue

Example

push(10)
push(20)
top()
pop()
push(30)
pop()
top()
Top : 20
Pop : 20
Pop : 30
Top : 10
push(1)
push(2)
top()
pop()
Top : 2
Pop : 2

Explanation

Let us suppose we have a queue, and now we start adding elements into it. So for adding or inserting the elements into it. We’ll call the push function.

push(1) —————> current state of queue -> 1

push(2) —————> current state of queue -> 2,1

For doing this, we will remove all the elements which were previously in the queue. Then we insert our new element in the empty queue. Afterward we again push the removed elements in the same order.

Looking at the top/front of the queue, thus gives us 2 as result.

q.top() = 2

Let’s remove the top element. So we are removing 2 from the queue.

So after the removal, the current state of queue = 1.

Algorithm to Implement a stack using single queue

  1. Initialize a class stack with a queue data structure of integer type as a private member. We also define push, pop, top, and empty as it’s public member functions.
  2. Create the function empty(). Return true if the queue is empty else return false.
  3. push() accepts an integer value. Create an integer variable and store the size of the queue in the variable and push/insert the integer variable in the queue.
  4. Traverse from 0 to the previous size of the queue. Keep on inserting the current front of the queue to itself and removing it.
  5. Create the function pop() which checks if there is no element in the queue then print “No elements” and return -1. Else pop/remove the top/front element.
  6. We create function top() which returns -1 if there is no element in the queue else return the front of the queue.

Code

C++ Program to Implement a stack using single queue

#include<bits/stdc++.h> 
using namespace std; 
  
class Stack{ 
    queue<int>q;
    
public: 
    void push(int val); 
    int pop(); 
    int top(); 
    bool empty(); 
}; 
  
void Stack::push(int val){ 
    int s = q.size(); 
  
    q.push(val); 
  
    for(int i=0; i<s; i++){ 
        q.push(q.front()); 
        q.pop(); 
    } 
} 
  
int Stack::pop(){ 
    if(q.empty()){ 
        cout<<"No elements\n";
        return -1;
    }    
    else{
        int x = q.front();
        q.pop();
        return x;
    }  
} 
  
int  Stack::top(){ 
    return (q.empty())? -1 : q.front(); 
} 
  
bool Stack::empty(){ 
    return (q.empty()); 
} 
  
int main(){ 
    Stack s;
    
    s.push(10); 
    s.push(20); 
    cout<<"Top : "<<s.top()<<endl; 
    cout<<"Pop : "<<s.pop()<<endl; 
    s.push(30); 
    cout<<"Pop : "<<s.pop()<<endl;
    cout<<"Top : "<<s.top()<<endl; 

    return 0; 
}
Top : 20
Pop : 20
Pop : 30
Top : 10

Java Program to Implement a stack using single queue

import java.util.LinkedList; 
import java.util.Queue; 
  
class stack{ 
    Queue<Integer> q = new LinkedList<Integer>(); 
      
    void push(int val){ 
        int size = q.size(); 
          
        q.add(val); 
          
        for(int i=0; i<size; i++){ 
            int x = q.remove(); 
            q.add(x); 
        } 
    } 
      
    int pop(){ 
        if (q.isEmpty()){ 
            System.out.println("No elements"); 
            return -1; 
        } 
        int x = q.remove(); 
        return x; 
    } 
      
    int top(){ 
        if (q.isEmpty()) 
            return -1; 
        return q.peek(); 
    } 
      
    boolean isEmpty(){ 
        return q.isEmpty(); 
    } 
  
    public static void main(String[] args){ 
        stack s = new stack(); 
        
        s.push(10); 
        s.push(20); 
        System.out.println("Top : " + s.top()); 
        System.out.println("Pop : " + s.pop()); 
        s.push(30); 
        System.out.println("Pop : " + s.pop()); 
        System.out.println("Top : " + s.top());
        
    } 
}
Top : 20
Pop : 20
Pop : 30
Top : 10

Complexity Analysis

Time Complexity

push() function is taking O(n) time while pop() and top() functions require constant time only i.e. O(1). Because for pushing an element we remove and add the number of elements which were already present in it. This makes the operation to run in polynomial time.

Space Complexity

O(n) because we are using space to store n number of elements.

Translate »