Implementation of Queue using one Stack in C++

Implementation of Queue using one Stack


In DSA, we use several algorithms with several data structures to soe problems. To understand the several data structures we turn them into one another using several different algorithm. Here is an article about the implementation of a queue using only one stack. 

Implementation of Queue using one stack | PrepInsta
Queue using a stack
Queue vs Stack

Stack vs Queue?

Stack is a data structure where you get Last in First out implementation, and queue is with first in first out implementation.

So, it seems impossible to turn a stack into a queue. Though by basic using of two stacks we can implement a queue very easily : Queue By 2 stacks.

Stack Vs Queue

Here goes the algorithm: 

Here we are making a class named Queue, and the objects of the class can be used as real queue type data structure. Now as we need to turn a stack into a queue, the builtin stack class from C++ Standard Template Library is used (Stack in C++ STL). Here is how to get it done.

  • Firstly, we are going to take one stack. Now stack can push value in the top and pop from there.
  • So the top of the stack is going to be treated as the rear or back of the queue. So pushing value in the queue is easy, pushing value in the stack.
  • For Pop, If the stack is empty, the queue can not pop anything.
  • Now, the pop function or dequeue function is a trick with recursion. 
  • We know recursion uses stack memory to store recursively called functions. Now suppose in the Pop Function, we pop out one element in the stack, and keep base condition after that.
  • The base condition is here as: if the stack is empty, we know the last popped value is the last value in the stack. And the last value in the stack is the front of the queue. So only then we return the value without pushing it back to the stack,
  • Otherwise, we recursively call pop function again, store the value of it in another variable, and after that push the popped out value for that calling in the stack. By this, when the recursion will totally end, the values will be pushed in the order they were popped out, just deleting the last value in the stack.
  • The same way can be used to check the front value too,  using a recursive function.
  • There may be a function called empty, saying if the size is 0 or not.
  • Otherwise we can track how many nodes are there in the queue, using the size variable in the class.
Queue using a stack

The code to implement this:

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

class Queue
{
  public:
  stack<ints;
  int size;
  Queue() {size=0;}
  void Push(int i)
  {
    cout<<“Pushing the element : “<<i<<endl;
    s.push(i);size++;
  }
  int pop()
  {
    if(size==0) {cout<<“The Queue is empty”<<endl;return;}
    int a=s.top();s.pop();
    if(!s.empty()) {int b=pop();s.push(a);return b;}
    else {cout<<“Popping “<<a<<endl;size–;}
    return a;
    /* // Or You can write:
    if(s.empty()) {cout<<“Popping “<<a<<endl;return a;}
    int b=pop();
    s.push(a);
    return b;
    */
  }
  void Show()
  {
    if(size==0) {cout<<“The Queue is empty”<<endl;return;}
    int a=s.top();s.pop();
    if(!s.empty()) Show();
    cout<<a<<” “;
    s.push(a);
  }
  int front()
  {
    if(size==0) {cout<<“The Queue is empty”<<endl;}
    int b,a=s.top();s.pop();
    if(!s.empty()) {int b=front();s.push(a);return b;}
    else b=a;
    s.push(a);
    return a;
  }
  bool empty()
  {
    return size==0;
  }
};

int main()
{
  Queue q;
  q.Push(1);q.Push(5);q.Push(2);q.Push(11);
  q.Show();cout<<endl;
  cout<<“The front most value right now is : “<<q.front()<<endl;
  q.pop();q.pop();
  q.Push(12);q.Push(8);
  cout<<“The front most value right now is : “<<q.front()<<endl;
  q.Show();cout<<endl;
}

Output:

Pushing the element : 1
Pushing the element : 5
Pushing the element : 2
Pushing the element : 11
1 5 2 11
The front most value right now is : 1
Popping 1
Popping 5
Pushing the element : 12
Pushing the element : 8
The front most value right now is : 2
2 11 12 8

If you want to create a queue using 2 Stacks : Queue using two string 

Article is contributed by Rahit Saha