Implement Stack Using Queue

Problem statement:

Given a queue we need to implement a stack data structure.

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.

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: Making the push operation costly:

This method will make sure that the newly entered element is always at the front of q1 due to which the pop operation dequeues from q1. q2 will put every new element in front of q1.


#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: Making the pop operation costly:

In push operation, the new element will always be inserted in q1 and in pop operation if the s1 is empty then all the elements except the last element will move on to q2 therefore, the last element will be dequeued from q1 and returned.

#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:

In this approach we’ll be using only 1 queue and making this 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.

#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;
}

This article tried to discuss the Implementation of Stack Using Queue. Hope this blog helps you understand the concept. To practice more problems feel free to check MYCODE | Competitive Programming at Prepbytes.

Leave a Reply

Your email address will not be published. Required fields are marked *