Home » Data Structure

Implementation of Stack using two Queues

Stack implementation using two Queues: Here, we are going to implement a stack using two queues using C++.
Submitted by Radib Kar, on September 26, 2018

Stack and Queue at a glance...

Stack:

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). That means it is a data structure which is implemented as LIFO.

The main stack operations are (basic ADT operations)...

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

Queue:

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). That means it is a data structure which is implemented as FIFO.

The main Queue operations are (basic ADT operations)...

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

Implementation of a stack using two queues

Likewise, a queue can be implemented with two stacks, a stack can also be implemented using two queues. The basic idea is to perform stack ADT operations using the two queues.

So, we need to implement push(),pop() using DeQueue(), EnQueue() operations available for the queues.

Implementation:

Let q1 and q2 be the two queues...

struct stack{
	struct queue *q1;
	struct queue *q2;
}

Algorithm to implement push and pop:

Push operation algorithm:

1. Check whether q1 is empty or not. If q1 is empty then EnQueue the element to q2.
2. Otherwise EnQueue to q1.

push(struct stack *s,int data){
	if(isempty(s->q1))
		EnQueue(s->q2,data);
	else
		EnQueue(s->q1,data);
}

Pop operation algorithm

The basic idea is to transfer n-1 elements (let n be the total no of elements) to other queue and delete the last one from a queue to perform the pop operation.

1. If q1 is not empty then transfer n-1 elements from q1 to q2 and DeQueue the last element and return it.
2. If q2 is not empty then transfer n-1 elements from q2 to q1 and DeQueue the last element and return it.

int pop(struct stack *s){
	int count,size;
	if(isempty(s->q2)){
		size=Size(s->q1);
		count=0;
		while(count<size-1){
			//transferring n-1 elements
			EnQueue(s->q2,DeQueue(s->q1));
			count++;
		}
		//last element to be popped
		return DeQueue(s->q1);
	}
	else{
		size=Size(s->q2);
		count=0;
		while(count<size-1){
			EnQueue(s->q1,DeQueue(s->q2));
			count++;
		}
		return DeQueue(s->q1);
	}
}

Time complexity analysis:

1. Push: O(1)
2. Pop: O(n) , since transferring n-1 elements

Implementation code using C++ (using STL)

#include <bits/stdc++.h>

using namespace std;

struct Stack{
	queue<int> q1,q2;

	void push(int x){
		if(q1.empty()){
			q2.push(x);    //EnQueue operation using STL
		}
		else{
			q1.push(x);    //EnQueue operation using STL
		}
	}

	int pop(){
	int count,size,item;
	if(q2.empty()){
		size=q1.size();            //size=no of elements;
		count=0;
		while(count<size-1){         //transfering n-1 elements
			q2.push(q1.front());     // DeQueue operation using STL
			q1.pop();
			count++;
		}
		item=q1.front();
		q1.pop();
		return item;                 //popping out the element
	}
	else{
		size=q2.size();
		count=0;
		while(count<size-1){
			q1.push(q2.front());
			q2.pop();
			count++;
		}
		item=q2.front();
		q2.pop();
		return item;
		}
	}
};

int main()
{
	cout<<"implementing stack with two queues"<<endl;

	cout<<"enter any integer to push and 0 to stop pushing"<<endl;

	Stack s;
	int x,count=0;
	
	cin>>x;
	
	while(x){
		s.push(x);
		cin>>x;
		count++;
	}
	
	cout<<"now popping......."<<endl;

	while(count){
		cout<<s.pop()<<endl;
		count--;
	}
	
	cout<<"executed successfully!!!"<<endl;

	return 0;
}

Output

implementing stack with two queues
enter any integer to push and 0 to stop pushing
1
2
3
0
now popping.......
3
2
1
executed successfully!!!