Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach 1 -By making push() operation costly
2.1.
Algorithm 
2.2.
C++ Implementation 
2.3.
C++
3.
Approach 2 -By making pop() operation costly
3.1.
Algorithm 
3.2.
C++ Implementation 
3.3.
C++
4.
Approach 3- Making Queue act like a Stack
4.1.
Algorithm
4.2.
C++ Implementation 
4.3.
C++
5.
Frequently Asked Questions
5.1.
In the implementation of stacks using queues, which approach is better - making push operation costly or making pop operation costly? Why?
5.2.
How many different kinds of operations are possible with a stack?
5.3.
What are the possible stack implementation error cases?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Implementation of stacks using queues

Author Yukti Kumari
2 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Have you ever wondered how computers keep track of things in the right order? Stacks and queues are two fundamental data structures that help us do just that. But what if we told you there's a sneaky way to build a stack using a queue?

In this blog, we'll discuss stacks and queues, and explore how they work and why they're important. Then, we'll unveil the surprising trick of implementing a stack using queues! 

Implementation of stacks using queues

There are several approaches for the implementation of stacks using queues. We will see each of them one by one.

Recommended Topic, Binary to Hex Converter,C Static Function

Approach 1 -By making push() operation costly

In this method, we will use two queues for the implementation of stacks using queues. 

The idea is to keep the last entered element at the front of the queue. Why?  Because the stack is a Last in First out data structure while in the queue, the elements are removed from the front end. So, when we will do a pop operation, then the last entered element will be the first one to be removed as we will ensure that it is kept at the front of the queue.

Algorithm 

  • Push Operation  

    To push a new element in the stack, move all the elements from the first queue to the second queue and then enqueue the new element into the first queue. Finally, move all the elements from the second queue back to the first queue. 

    This is done to ensure that the newly entered element lies at the front of the queue.
     

Time Complexity – 

It is O(n), where n is the number of elements in the stack. 

All the elements are dequeued from the first queue one by one and then enqueued into the second queue and again moved back to the first queue. So, if there are n elements in the first queue initially, then the series of operations performed on each of them are – 

  1. dequeue from the first queue
     
  2. enqueue to the second queue
     
  3. dequeue from the second queue
     
  4. enqueue to the first queue
     

And we know that each enqueue/dequeue operation is O(1). So, total number of operations performed = n*(4*O(1)) + O(1) (to enqueue a new element), which is O(n). 
 

Alternative Way: 

  • Enqueue new element to the second queue, say Q2
     
  • Dequeue all the n elements from the first queue, say Q1, and enqueue them into Q2.
     
  • Swap the queues Q1 and Q2 to avoid copying all the elements from Q2 to Q1. 

 

  • Pop Operation – 

    To pop an element from the stack, dequeue the element at the front of the first queue.
     

Time Complexity – 

It is O(1) because we do only one dequeue operation.

Space Complexity –  It is O(n) as we use two additional queues for the implementation of stack functions.

Let’s take an example to understand the implementation of stacks using queues easily- 

Suppose we are given a series like this - 

5, 7, 3, P

where P means the pop operation has to be performed and integer value means push operation.

 

Initially, we have two empty queues Q1 and Q2, like this - 

Two Empty Queues

 

Step 1: Enqueue 5 to Q1. 

Enque 5 to Q1

 

Step 2: Next, we have to enqueue 7 such that it remains at the front end of Q1. 

Dequeue 5 from Q1 and enqueue it into Q2. And enqueue 7 to Q1.

Enqueue 7

Now, dequeue 5 from Q2 and enqueue it to Q1.

Dequeue 5 from q2

 

Step 3: Now, to enqueue 3, we will move 7 and 5 from Q1 to Q2 and enqueue 3 to Q1.

Enqueue 3 to Q1

Now, move 7 and 5 from Q2 to Q1.

Move 7 and 5 from Q2 to Q1

 

Step 4: Next, we have P in the series, meaning we need to pop from the stack. 

To do this, simply perform a dequeue operation on Q1, which will remove 3.

Dequeue operation on Q1


You can also read about dynamic array in c and Short int in C Programming

C++ Implementation 

  • C++

C++

/*
C++ code for implementation of stacks using queues - Push- O(n) and Pop - O(1)
*/
#include <iostream>
#include <queue>
#include <vector>
#include <cstdlib>
using namespace std;


// Define and implement a stack class using two queues
class Stack
{
   queue<int> q1, q2;


public:
   // Insert a new element into the stack
   void push(int data)
   {
       // Move all the elements from the q1 to q2
       while (!q1.empty())
       {
           q2.push(q1.front());
           q1.pop();
       }


       // enqueue the new element into q1
       q1.push(data);
       cout << "Pushed: " << data << endl;


       // Move all the elements back to q1 from q2
       while (!q2.empty())
       {
           q1.push(q2.front());
           q2.pop();
       }
   }


   // Remove the top element from the stack
   void pop()
   {
       // check if the q1 is empty
       if (q1.empty())
       {
           cout << "Stack Underflow\n";
           return;
       }


       // else return the front element from q1
       int front = q1.front();
       q1.pop();
       cout << "Popped: " << front << endl;
   }
};


int main()
{
   vector<int> data = {5, 7, 31, 4, 2};


   // insert the elements into the stack
   Stack s;
   for (int key : data)
   {
       s.push(key);
   }
   cout << endl;
   for (int i = 0; i <= data.size(); i++)
   {
       s.pop();
   }


   return 0;
}

Output:

Pushed: 5
Pushed: 7
Pushed: 31
Pushed: 4
Pushed: 2


Popped: 2
Popped: 4
Popped: 31
Popped: 7
Popped: 5
Stack Underflow

 

Click on the following link to read further: Features of C Language

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 2 -By making pop() operation costly

Algorithm 

  • Push Operation  To push an element to the stack, simply enqueue the element into the first queue q1.
     

Time Complexity – It is O(1) as the enqueue operation in a queue is O(1).
 

  • Pop Operation   Since we enqueue all the elements into the first queue, the last entered element lies at the rear end of the first queue. So, to ensure the Last In First out property of stack, the element at the rear end should be removed.
     

We do this by moving all the elements from the first queue,q1, to the second queue,q2, except the last element. Finally, remove this last element from q1 and move the elements back from q2 to q1. 

Time Complexity –  It is O(n) as for every pop operation, we move the elements of the first queue twice between the first and second queue.
 

Space Complexity –  It is O(n) as we use two additional queues for the implementation of stack functions.

Let’s take an example to understand the implementation of stacks using queues by following approach 2 – 

Consider we are given the following series of operations - 

5,3,1,P

Initially, we have two empty queues Q1 and Q2.

 

Step 1: Enqueue 5 to the first queue i.e., Q1.

Enqueue 5

 

Step 2: Enqueue 3 into the queue Q1.

Enqueue 3

 

Step 3:  Enqueue 1 into the queue Q1.

Enqueue 1

 

Step 4: Next, we need to do a pop operation.

Pop Operation

Move all the elements except 1 from Q1 to Q2.

 

Moving all elements from Q1 to Q2 except 1

Pop 1 from Q1. 

Finally, move  5 and 3 back to Q1.

Must Read Stack Operations

C++ Implementation 

  • C++

C++

/*
C++ code for implementation of stacks using queues - Push- O(1) and Pop - O(n)
*/


#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstdlib>
using namespace std;


// Define and implement a stack class using two queues
class Stack
{
   queue<int> q1, q2;


public:
   // Insert a new element into the stack
   void push(int data)
   {
       // Push the new element into q1
       q1.push(data);
       cout << "Pushed: " << data << endl;
   }


   // Remove the top element from the stack
   void pop()
   {
       // if the first queue is empty
       if (q1.empty())
       {
           cout << "Stack Underflow\n";
           return;
       }


       /*Move all elements except the last from q1 to q2*/
       int front;
       while (!q1.empty())
       {
           if (q1.size() == 1)
           {
               front = q1.front();
           }
           else
           {
               q2.push(q1.front());
           }


           q1.pop();
       }


       /* moving all elements back to q1 from q2*/
       while (!q2.empty())
       {
           q1.push(q2.front());
           q2.pop();
       }


       /* `swap(q1, q2)` can also be done instead of the above loop*/


       cout << "Popped: " << front << endl;
   }
};


int main()
{
   vector<int> data = {5, 7, 31, 4, 2};


   // insert the elements into the stack


   Stack s;
   for (int key : data)
   {
       s.push(key);
   }
   cout << endl;
   for (int i = 0; i <= data.size(); i++)
   {
       s.pop();
   }


   return 0;
}


Output:

Pushed: 5
Pushed: 7
Pushed: 31
Pushed: 4
Pushed: 2


Popped: 2
Popped: 4
Popped: 31
Popped: 7
Popped: 5
Stack Underflow

Read about Application of Queue in Data Structure here.

Approach 3- Making Queue act like a Stack

This approach uses a single queue to mimic the behavior of a stack. The key idea lies in manipulating the order elements are added and removed from the queue. 

Algorithm

Here's how it works:

  1. Pushing: When adding an element to the "stack," we perform two steps:
    • Add the element to the back of the queue (normal queue behavior).
    • Loop: Starting from the front of the queue, we repeatedly dequeue an element, enqueue it back at the end, and continue until we reach the newly added element.

This loop essentially "reverses" the order of elements in the queue, placing the new element at the front, mimicking a push operation in a stack.

2. Popping: Popping an element is straightforward. We simply dequeue and remove the element from the front of the queue, just like a standard queue operation.

C++ Implementation 

  • C++

C++

#include <queue>
#include<iostream>
using namespace std;

class Stack {
private:
std::queue<int> data;

public:
// Push operation
void push(int value) {
data.push(value);
// Reverse the queue order to place the new element at the front
int size = data.size();
for (int i = 0; i < size - 1; i++) {
int temp = data.front();
data.pop();
data.push(temp);
}
}

// Pop operation
int pop() {
if (data.empty()) {
throw std::runtime_error("Stack underflow");
}
int top = data.front();
data.pop();
return top;
}
};

int main() {
Stack myStack;
myStack.push(10);
myStack.push(20);
myStack.push(30);

std::cout << myStack.pop() << std::endl; // Output: 30
std::cout << myStack.pop() << std::endl; // Output: 20

return 0;
}

Output

30
20

 

Important Note:

This approach achieves stack-like behavior using a queue, but it comes with a trade-off. The "push" operation becomes more complex due to the queue reversal, leading to a higher time complexity (O(n) for push compared to O(1) for a real stack). However, it demonstrates a clever way to utilize existing data structures for different purposes.

Frequently Asked Questions

In the implementation of stacks using queues, which approach is better - making push operation costly or making pop operation costly? Why?

The answer depends on the use case. When there are more push operations than pop operations, making the push operation costly may not be desired, so the second approach of making pop operation costly will be better as time complexity will improve.

How many different kinds of operations are possible with a stack?

A stack mainly supports three operations: PUSH: Inserting an element into the stack is done using the push operation. POP: The topmost element in the stack can be deleted with the pop operation. PEEK: Peek is an operation that retrieves the value of the stack's topmost element without removing it.

What are the possible stack implementation error cases?

A stack implementation typically has two error cases. The first mistake is pushing something onto a full stack, and the second is popping something off of an empty stack.

Conclusion

In this article, we learnt the implementation of stacks using queues. We saw different approaches with a detailed explanation and implementation and compared them based on their time and space complexities. 

Implementation based questions help you have a clear understanding of the data structures used and are also asked in technical interviews.

You can also see the implementation of stacks using arrays and linked lists here.

Check out this problem - Queue Implementation

Don’t stop here. Learn more about stacks, queues and various other concepts from Coding Ninjas Studio blogs. Try practising coding problems and challenge yourself to improve your problem-solving skills here.

Previous article
Number pattern programs in C
Next article
Bubble Sort Program in C
Live masterclass