Implementation of Queue using one Stack in C++

February 24, 2023

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 two stacks in C++

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.

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.
Implementation of queue using stack in C
DSA desktop gif
DSA mobile gif

Types of Queues in Data Structure

Application of Queue Data Structure

Insertion in Queues Program (Enqueuing)

Queues using Linked Lists

Implement Queue using two Stacks

Implementation of Queue using Linked List in C++:

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

class Queue
{
public:
  stack < int >s;
  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 0;
      }
    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;

  }
  void display ()
  {
    if (size == 0)
      {
	cout << "The Queue is empty" << endl;
	return;
      }
    int a = s.top ();
    s.pop ();
    if (!s.empty ())
      display ();
    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.display ();
  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.display ();
  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

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

Stacks

  • Introduction to Stack in Data Structure
    Click Here
  • Operations on a Stack
    Click Here
  • Stack: Infix, Prefix and Postfix conversions
    Click Here
  • Stack Representation in –
    C | C++ | Java
  • Representation of a Stack as an Array. –
    C | C++ | Java
  • Representation of a Stack as a Linked List. –
    C | C++ | Java
  • Infix to Postfix Conversion –
    C | C++ | Java
  • Infix to prefix conversion in –
    C | C++ | Java
  • Postfix to Prefix Conversion in –
    C | C++ | Java

Queues

  • Queues in Data Structures (Introduction)
    Click Here
  • Queues Program in C and implementation
    Click Here
  • Implementation of Queues using Arrays | C Program
    Click Here
  • Types of Queues in Data Structure
    Click Here
  • Application of Queue Data Structure
    Click Here
  • Insertion in Queues Program (Enqueuing) –
    C | C++ | Java
  • Deletion (Removal) in Queues Program(Dequeuing) –
    C | C++ | Java
  • Reverse a Queue –
    C | C++ | Java
  • Queues using Linked Lists –
    C | C++ | Java
  • Implement Queue using Stack –
    C | C++ | Java
  • Implement Queue using two Stacks –
    C | C++ | Java

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction –
    C | C++ | Java
  • Priority Queue Implementation using Array –
    C | C++ | Java
  • Priority Queue using Linked List –
    C | C++ | Java
  • Priority Queue Insertion and Deletion-
    C | C++ | Java

Stacks

Queues

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction – C | C++ | Java
  • Priority Queue Implementation using Array – C | C++ | Java
  • Priority Queue using Linked List – C | C++ | Java
  • Priority Queue Insertion and Deletion- C | C++ | Java