Queue using stacks

© Parineeth M R

Question 11. Implement a queue using stacks


To implement a queue using stacks, we have to perform the enqueue and dequeue operations of the queue using the push and pop operations supported by the stacks.

Let us say that we internally use stack S1 to implement a queue. When elements are added to the queue, they are pushed onto the internal stack S1. However when we have to remove an element from the queue, if we pop the element from S1, we will be returning the most recently added element instead of the element first added to the queue. We solve this problem by using an additional internal stack S2 that stores the elements to be removed from the queue in correct order. So S2 should store the elements in reverse order of S1. By popping each element from S1 and immediately pushing it into S2, S2 will store the elements in reverse order of S1. To remove an element from the queue, we will have to just pop the element from S2.

For instance, let us say that elements A, B and C are added to the queue. Then S1 will contain A, B and C while S2 will be empty as shown in the diagram below.

Now if an element has to be removed from the queue, since S2 is empty, each element of S1 is popped and immediately pushed into S2 as shown in the diagram below.

The top of stack S2 (which is element A) is then popped to remove the element from the queue.

It is important to note that, elements should be popped from S1 and pushed into S2 only when S2 is completely empty. For instance, after A is removed, let the element D be added to the queue. D is first added to S1. Suppose D is popped from S1 and pushed to S2 even before S2 is empty, then the state of the stacks is shown below

Clearly this results in an incorrect behavior since the next element that will be removed from the queue is D as D is at the top of S2 whereas the correct element to be removed from the queue is the element B. The code for a queue class using stacks is given below:

C/C++


template <class T> class QueueUsingStacks 
{
	private:
	stack<T> s1;
	stack<T> s2;

	public:
	QueueUsingStacks() {

	}

	void add(T new_element) {
		/*Add elements only to stack s1*/
		s1.push(new_element);
	}

	T remove() {
		T e;
		if(s2.empty()) {
			/*We remove elements only from stack s2. So
			if s2 is empty, then pop all the elements from s1 and  
			push them into s2.*/
			while(!s1.empty()) {
				e = s1.top();
				s1.pop();
				s2.push(e);
			}
		}

		if (s2.empty())
			throw exception();
		
		/*If s2 is not empty, then remove the element from top of s2.
		This element corresponds to the head of the queue*/
		e = s2.top();
		s2.pop();
		return e;
	}

	bool empty() {
		/*Queue is empty only if both stacks are empty*/
		if (s1.empty() && s2.empty())
			return true;
		return false;
	}
	
};


Java


class QueueUsingStacks <T> {
	private Stack<T> s1;
	private Stack<T> s2;

	public QueueUsingStacks () {
		s1 = new Stack<T>();
		s2 = new Stack<T>();
	}

	public void add(T newElement) {
		/*Add elements only to stack s1*/
		s1.push(newElement);
	}

	public T remove() {
		T e;
		if(s2.isEmpty()) {
			/*We remove elements only from stack s2. So
			if s2 is empty, then pop all the elements from s1 and  
			push them into s2.*/
			while(!s1.isEmpty()) {
				e = s1.pop();
				s2.push(e);
			}
		}
		
		/*If s2 is not empty, then remove the element from top of s2.
		This element corresponds to the head of the queue*/
		e = null;
		if(!s2.isEmpty())
			e = s2.pop();

		return e;
	}

	public boolean isEmpty() {
		/*Queue is empty only if both stacks are empty*/
		if (s1.isEmpty() && s2.isEmpty())
			return true;
		return false;
	}
	
}


Python


#Queue in Python 2.7 has been renamed to queue. So handling this so that code
#is portable on all versions of Python
try: 
	import queue
except ImportError:
	import Queue as queue


class QueueUsingStacks(object):
	def __init__(self):
		#Create the internal stacks
		self.s1 = queue.LifoQueue()
		self.s2 = queue.LifoQueue()

	def add(self, new_element): 
		#Add elements only to stack s1
		self.s1.put(new_element)
	
	def remove(self): 
		if(self.s2.empty()) :
			#We remove elements only from stack s2. So
			#if s2 is empty, then pop all the elements from s1 and  
			#push them into s2.
			while(not self.s1.empty()) :
				e = self.s1.get()
				self.s2.put(e)
			
		#If s2 is not empty, then remove the element from top of s2.
		#This element corresponds to the head of the queue
		e = None
		if(not self.s2.empty()):
			e = self.s2.get()

		return e
	

	def empty(self): 
		#Queue is empty only if both stacks are empty
		if (self.s1.empty() and self.s2.empty()):
			return True
		return False