Queue Using Stacks

Problem statement:

Problem is straightforward, we have to implement a queue using stack.

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


#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 for push operation is O(N) and for pop operation O(1)
Space Complexity is O(N).

Approach 2: 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.



#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 of push operation is O(1 ) and for pop operation is O(N).
Space complexity is O(N).

This article tried to discuss Implementation of Queue using stacks. Hope this blog helps you understand the concept. To practice problems feel free to check MYCODE | Competitive Programming.

Leave a Reply

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