Implementation of Queue using two Stacks

Queue Implementation using Two Stacks in C++: Here, we are going to implement a C++ program to implement Queue using two Stacks.
Submitted by Radib Kar, on September 25, 2018

Queue:

A queue is a data structure for storing data where the order in which data arrives is important. The queue is implemented as FIFO (First in First Out).

The queue is an ordered list in which insertions are done at one end (rear) and deletions are done from another end (front). The first element that got inserted is the first one to be deleted (basic principle of FIFO).

The main Queue operations are:

EnQueue (int data): Insertion at rear end
int DeQueue(): Deletion from front end

Stack:

A stack is also another data structure which is implemented as LIFO.

The stack is an ordered list where insertion and deletion are done from the same end, top. The last element that entered first is the first one to be deleted (the basic principle behind the LIFO).

The main stack operations are:

push (int data): Insertion at top
int pop(): Deletion from top

Implementing Queue using stack

A queue can be implanted using stack also. We need two stacks for implementation. The basic idea behind the implementation is to implement the queue operations (enqueue, dequeue) with stack operations (push, pop).

Implementation:

Let s1 and s2 be the two stacks used for implanting the queue.

struct queue{
	struct stack *s1; // this stack is for enqueue operation
	struct stack *s2; // this stack is for dequeue operation 
}

Enqueue algorithm:

Just push to stack s1

void Enqueue(struct queue *q, int data){
	push(q->s1,data); //data pushed to stack s1
}

Dequeue algorithm

Dequeue operation is little expansive here, we need to check few things like whether stack s2 is empty or not (stack s2 is for dequeuer operation). The basic idea is if s2 is empty we transfer all element of s1 to s2 and pop s2. The popped element is same as the dequeued one. Whenever we transfer all element from s1 to s2, the top element of s2 becomes the first one to enter s1 thus popping s2 deletes/returns the first element that was enqueued, maintaining the queue property FIFO.

Let's check the algorithm:

If the stack s2 is not empty then pop from s2.
If stack s2 is empty, then transfer all elements from s1 to s2 and pop from s2.
If stack1 is empty throw an error. (underflow problem)

int Dequeue(struct queue *q1){
	if (!isempty( q->s2))             //checking whether s2 is empty or not
		return pop(q->s2); // if s2 is not empty return popped element
	else{
		while(!isempty(q->s1))
			push(q->s2,pop(q->s1)); //transfer all element from s1 to s2
		return pop(q->s2);
	}
}

Time complexity analysis:

Enqueuer operation : O(1)
Dequeue operation: O(1) (amortized complexity)

C++ implementation using STL

// header file to include all libraries
#include <bits/stdc++.h>
using namespace std;

struct Queue {
	stack<int> s1, s2; // stl used

	// Enqueue an item to the queue
	void enQueue(int x)
	{
		// Push item into the first stack
		s1.push(x);
	}

	// Dequeue an item from the queue
	int deQueue()
	{
		// if both stacks are empty
		if (s1.empty() && s2.empty()){
			cout << "Queue is empty";
			exit(0);
		}

		// if s2 is empty, move elements from s1
		if (s2.empty()) {
			while (!s1.empty()) {
				s2.push(s1.top());  // using stl operation top()
				s1.pop();
			}
		}

		// return the top item from s2
		int x = s2.top();
		s2.pop();
		return x;
	}
};

// main function
int main()
{
	Queue q;

	int x,count=0;
	cout<<"press 0 to stop push operaton, else enqueue integers"<<endl;
	cin>>x;
	
	while(x){
		q.enQueue(x);
		count++;
		cin>>x;
	}
	cout<<"dequeueing...."<<endl;
	while(count){
		cout<<q.deQueue()<<endl;
		count--;
	}
	cout<<"execution successful"<<endl;

	return 0;
}

Output

press 0 to stop push operaton, else enqueue integers
10
20
5
7
0
dequeueing...
10
20
5
7
execution successful

Explanation:

10,20,5,7,0 are the input taken from console and 10,20,5,7 are enqueued. Enqueue operation stopped as soon as user gave input 0.

Then dequeue operation started and the dequeue order is FIFO 10,20,5,7