Last Updated on June 6, 2023 by Mayank Dham
In this article, we explore the implementation of stacks using queues and the interplay between push vs pop operations. Stacks, based on the Last-In-First-Out (LIFO) principle, and queues, based on the First-In-First-Out (FIFO) principle, have distinct characteristics. However, by manipulating queues intelligently, we can mimic stack behavior. We discuss different approaches, including making either the push vs pop operation costly as well as utilizing a queue as a stack. Join us as we delve into the push vs pop dynamics and unravel the art of implementing data structures.
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 in C?
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.
C program to implement stack using queue
#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.
C program to implement stack using queue
#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: Making Queue act like a Stack
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
C program to implement stack using queue
#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 discussed different approaches to implement stack using queues. Implementing stacks using queues can be done by a more different approach. 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 out how to implement the stack using a queue.
Frequently Asked Questions (FAQs)
Q1.Why would we want to implement a stack using queues?
Implementing a stack using queues can be useful when we have a requirement to use stack operations but only have access to queue data structures. It allows us to leverage the functionalities of a stack while working with queues.
Q2.What is the difference between the "push" and "pop" operations in stack and queue implementations?
In stack implementation, "push" refers to inserting an element onto the top of the stack, while "pop" refers to removing the topmost element. In queue implementation, "push" inserts an element at the rear, while "pop" removes the frontmost element.
Q3.How does the "push" operation become costly in implementing a stack using queues?
In one approach, the "push" operation becomes costly by requiring additional steps to enqueue elements in such a way that the last inserted element is always at the front. This involves dequeuing and enqueuing elements between two queues.
Q4.What is the alternative approach to implementing a stack using queues?
Another approach involves making the "pop" operation costly. In this method, elements are initially enqueued normally, but during the "pop" operation, all but the last element are moved to a second queue before dequeuing the top element.
Q5.Can a queue be made to act like a stack without using two queues?
Yes, it is possible to make a queue act like a stack by repeatedly pushing the first element to the rear end. This process mimics the behavior of a stack, as the most recently pushed element is always at the front and gets popped first.