Implementing Queue using Stacks

Last Updated on September 22, 2023 by Mayank Dham

In this tutorial, we will talk about a famous data structure problem “implement queue using stack”. Firstly, we will understand what stack and queue in data structure, then we will discuss how to implement queue using stack. Let’s take small steps and discuss how to implement queue using stack.

How to Implement Queue using Stacks

Queue: A Queue is a linear data structure. Queue follows the FIFO rule i.e. First in First out. In other words we can say the element that goes in first is the element that comes out first.
For Example A ticket Queue outside a cinema hall where the person enters the queue first will get the ticket first.

Basic Operations of Queue:

• Enqueue: This operation is used to Insert an element at the end of the queue.
• Dequeue: This operation is used to remove and return an element from the front of the queue.
• isEmpty(): This operation is used to check whether the queue is empty or not.
• isFull(): This operation is used to check whether the queue is full or not.
• Peek(): This operation is used to get the value of the element from the front of the queue.

Stack

Stack follows the principle of LIFO (Last in First out) i.e. element which is inserted at last will be removed first. The operation for insertion of elements in stack is known as Push operation and the operation for deletion of element in stack is known as Pop operation.

We can implement a queue by using two stacks.
Let queue be q and stack be s1 and s2:

Approach 1: To Implement Queue using Stack by Making Enqueue Operation Costly:

This method just makes sure that the oldest entered element is always at the top of s1. So, the dequeue operation just pops the element from s1. To put the element at top of s1 we’ll use s2.

Code Implementation

#include <bits/stdc++.h>
using namespace std;

struct Queue {
	stack<int> s1, s2;

	void Enqueue(int x)
	{
	
		while (!s1.empty()) {
			s2.push(s1.top());
			s1.pop();
		}

		s1.push(x);

		while (!s2.empty()) {
			s1.push(s2.top());
			s2.pop();
		}
	}

	int Dequeue()
	{
		if (s1.empty()) {
			cout << "Q is Empty";
			exit(0);
		}

		int x = s1.top();
		s1.pop();
		return x;
	}
};

int main()
{
	Queue q;
	q.Enqueue(1);
	q.Enqueue(2);
	q.Enqueue(3);

	cout << q.Dequeue() << '\n';
	cout << q.Dequeue() << '\n';
	cout << q.Dequeue() << '\n';

	return 0;
}

Time Complexity to implement queue using stack for push operation is O(N) and for pop operation O(1)

Space Complexity to implement queue using stack is O(N).

Approach 2: To Implement Queue using Stack by Making Dequeue Operation Costly:

In this method, the new element is entered at the top of the s1 in enqueue operation and in dequeue operation, if s2 was empty then all the elements are moved to s2 and then return the top most element of the s2.

Code Implementation

#include <bits/stdc++.h>
using namespace std;

struct Queue {
	stack<int> s1, s2;

	void Enqueue(int x)
	{
		s1.push(x);
	}

	int Dequeue()
	{
		if (s1.empty() && s2.empty()) {
			cout << "Q is empty";
			exit(0);
		}

		if (s2.empty()) {
			while (!s1.empty()) {
				s2.push(s1.top());
				s1.pop();
			}
		}

		int x = s2.top();
		s2.pop();
		return x;
	}
};

int main()
{
	Queue q;
	q.Enqueue(1);
	q.Enqueue(2);
	q.Enqueue(3);

	cout << q.Dequeue() << '\n';
	cout << q.Dequeue() << '\n';
	cout << q.Dequeue() << '\n';

	return 0;
}

Time complexity to implement queue using stack for push operation is O(1 ) and for pop operation is O(N).
Space complexity to implement queue using stack is O(N).

Conclusion
With the help of this tutorial, we had discussed thoroughly about how to implement queue using stack. Queue implementation using stack is not a difficult task if you know about stack and queue, and how to find an approach to implement queue using stack. Practice more questions to become a master in data structures.