Table of Contents
Introduction
In this article, we will work on a very interesting problem called the implementation of stacks using queues, which will require an understanding of both data structures, namely stacks and queues.
So, in case you are not familiar with stacks & queues, you might want to brush up on these topics.
We will discuss the implementation of stack using queues. We will start with a short discussion of using queues to implement stacks and then see the code for its implementation. Also, you will get to know the time and space complexities of the various stack operations for all the approaches. In the end, we will compare the different approaches based on their performance in different use cases.
Now, the question is, how is it even possible to implement stacks using queues?
After all, Stack is a Last In First Out(LIFO) data structure while Queue is First in First Out(FIFO) data structure. So, both of these are poles apart in terms of their behaviour.
There are several approaches for the implementation of stacks using queues. We will see each of them one by one.
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 –
- dequeue from the first queue
- enqueue to the second queue
- dequeue from the second queue
- 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 –
Step 1: Enqueue 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.
Now, dequeue 5 from Q2 and enqueue it to Q1.
Step 3: Now, to enqueue 3, we will move 7 and 5 from Q1 to Q2 and enqueue 3 to Q1.
Now, 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.
C++ Implementation
/*
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
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.
Step 2: Enqueue 3 into the queue Q1.
Step 3: Enqueue 1 into the queue Q1.
Step 4: Next, we need to do a pop operation.
Move all the elements except 1 from Q1 to Q2.
Pop 1 from Q1.
Finally, move 5 and 3 back to Q1.
C++ Implementation
/*
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
Frequently Asked Questions
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.
Key Takeaways
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.
Don’t stop here. Learn more about stacks, queues and various other concepts from Codestudio blogs. Try practising coding problems and challenge yourself to improve your problem-solving skills here.
By: Yukti Kumari
