In this blog, we will discuss one of the famous data structures “implement stack using queue” which is very fascinating for understanding the concept of linear data structures like stacks. Implementing stack using queue can be easily achieved if you are aware of stack and queue and its operations.
Don’t worry we will discuss stack and queue first, then we will move to our topic i.e. “implement stack using queue”. Let’s move to see how to implement stack using queue.
What is a Stack?
Stack is a linear data structure in which a user can insert and delete an element from the same end which is known as a top.
Stack data structure follows LIFO property i.e. Last in first out.
In LIFO, the element which was inserted last will be the element which was removed first.
In stack, the process of insertion is called push operation and the process of deletion of the element from the stack is known as pop.
And, we can easily keep track of the last element using a pointer called top.
What is a Queue?
Queue is a linear data structure by nature. First in, First out, or FIFO, is the queue’s guiding principle. To put it another way, we may say that what goes in first is what comes out first.
The insertion and deletion in the queue is done from both ends i.e. from front and rear end. Insertion in the queue is done from the rear end whereas the deletion in the queue is done from the front end.
Consider taking a ticket. In a line outside a theater, the individual who joins first receives the first ticket.
Now, we had a brief idea about stack and queue, let’s move to our main topic i.e. how to implement stack using queue?
How to Implement Stack using Queue?
We can implement stack by using two queues. Let stack be the S and queues be q1 and q2.
We can implement stack by two ways:
Approach 1: To Implement Stack using Queue by Making the Push Operation Costly:
The idea is to keep newly entered elements at the front of ‘q1’ so that pop operation dequeues from ‘q1’. ‘q2’ is used to put every new element in front of ‘q1’.
Follow the below steps to implement the push(s, x) operation:
- Enqueue x to q2.
- One by one dequeue everything from q1 and enqueue to q2.
- Swap the queues of q1 and q2.
Follow the below steps to implement the pop(s) operation:
- Dequeue an item from q1 and return it.
Code implementation:
#include <bits/stdc++.h>
using namespace std;
class Stack {
queue<int> q1, q2;
int curr_size;
public:
Stack()
{
curr_size = 0;
}
void push(int x)
{
curr_size++;
q2.push(x);
while (!q1.empty()) {
q2.push(q1.front());
q1.pop();
}
queue<int> q = q1;
q1 = q2;
q2 = q;
}
void pop()
{
if (q1.empty())
return;
q1.pop();
curr_size--;
}
int top()
{
if (q1.empty())
return -1;
return q1.front();
}
int size()
{
return curr_size;
}
};
int main()
{
Stack s;
s.push(1);
s.push(2);
s.push(3);
cout << "current size: " << s.size()
<< endl;
cout << s.top() << endl;
s.pop();
cout << s.top() << endl;
s.pop();
cout << s.top() << endl;
cout << "current size: " << s.size()
<< endl;
return 0;
}
Approach 2: To Implement Stack using Queue by Making the Pop Operation Costly:
Below is the idea to solve the problem:
The new element is always enqueued to q1. In pop() operation, if q2 is empty then all the elements except the last, are moved to q2. Finally, the last element is dequeued from q1 and returned.
Follow the below steps to implement the push(s, x) operation:
- Enqueue x to q1 (assuming the size of q1 is unlimited).
Follow the below steps to implement the pop(s) operation:
- One by one dequeue everything except the last element from q1 and enqueue to q2.
- Dequeue the last item of q1, the dequeued item is the result, store it.
- Swap the names of q1 and q2
- Return the item stored in step 2.
Code Implementation:
#include <bits/stdc++.h>
using namespace std;
class Stack {
queue<int> q1, q2;
int curr_size;
public:
Stack()
{
curr_size = 0;
}
void pop()
{
if (q1.empty())
return;
while (q1.size() != 1) {
q2.push(q1.front());
q1.pop();
}
q1.pop();
curr_size--;
queue<int> q = q1;
q1 = q2;
q2 = q;
}
void push(int x)
{
q1.push(x);
curr_size++;
}
int top()
{
if (q1.empty())
return -1;
while (q1.size() != 1) {
q2.push(q1.front());
q1.pop();
}
int temp = q1.front();
q1.pop();
q2.push(temp);
queue<int> q = q1;
q1 = q2;
q2 = q;
return temp;
}
int size()
{
return curr_size;
}
};
int main()
{
Stack st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
cout << "current size: " << st.size()
<< endl;
cout << st.top() << endl;
st.pop();
cout << st.top() << endl;
st.pop();
cout << st.top() << endl;
cout << "current size: " << st.size()
<< endl;
return 0;
}
Approach 3:
To Implement Stack Using Queue and making this only queue act like a stack. The idea behind this is, we push the 1st element in the queue. After the first element we’ll push the next element and then again push the first element and finally pop the first element.
According to FIFO property, the second element that was pushed will be at the front end and then we pushed that element again and its copy has popped out so this is act like a stack and we do this for every element.
push(s, x) x is the element to be pushed and s is stack
- Let the size of q be s.
- Enqueue x to q
- One by one Dequeue s items from the queue and enqueue them.
pop(s) Removes an item from stack
- Dequeue an item from q
Code Implementation:
#include <bits/stdc++.h>
using namespace std;
class Stack {
queue<int> q;
public:
void push(int data);
void pop();
int top();
bool empty();
};
void Stack::push(int data)
{
int s = q.size();
q.push(data);
for (int i = 0; i < s; i++) {
q.push(q.front());
q.pop();
}
}
void Stack::pop()
{
if (q.empty())
cout << "No elements\n";
else
q.pop();
}
int Stack::top() { return (q.empty()) ? -1 : q.front(); }
bool Stack::empty() { return (q.empty()); }
int main()
{
Stack st;
st.push(40);
st.push(50);
st.push(70);
cout << st.top() << "\n";
st.pop();
cout << st.top() << "\n";
st.pop();
cout << st.top() << "\n";
st.push(80);
st.push(90);
st.push(100);
cout << st.top() << "\n";
st.pop();
cout << st.top() << "\n";
st.pop();
cout << st.top() << "\n";
return 0;
}
Conclusion
In this article, we had discussed different approaches to implement stack using queue. Implementing stack using queue can be done by more different approaches. Main thing is that you have to figure it out. Next question will be how to figure it out, the answer will be in your mind, you just have to figure it out how to implement the stack using queue.