Category: Stacks and Queues

Stack using queues

admin / / Data Structures, Stacks and Queues

© Parineeth M R

Question 12. Implement a stack using queues

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

A stack can be implemented using two internal queues Q1 and Q2. There are two ways to achieve this: one where the push operation is more efficient than the pop operation and the other where the pop operation is more efficient than the push operation.

Case 1: Push is more efficient than pop
When an element is pushed to the stack, the element is enqueued in Q1

When an element is popped from the stack, dequeue the first N-1 elements from Q1 (N is the number of elements currently present in Q1) and enqueue them in Q2, one element at a time. Dequeue the last element from Q1 and return it as the element popped from the stack. Now rename Q1 as Q2 and Q2 as Q1.

For instance, let us say that the elements A, B and C are added to the stack. Then A, B, C will be enqueued into Q1 as shown in the diagram below

Now if an element must be popped from the stack, dequeue A and B from Q1, then enqueue A and B in Q2. Finally dequeue the last element in Q1 which is C and return it as the popped element. Once this is done, the state of Q1 and Q2 are shown below

In the last step of the pop operation, Q1 is renamed as Q2 and Q2 is renamed as Q1 as shown below

The code for implementing a stack class using queues where push is efficient is given below

C/C++


template <class T> class StackUsingQueues 
{
	private:
	queue<T> *q1;
	queue<T> *q2;

	public:
	StackUsingQueues() { 
		q1 = new queue<T>();
		q2 = new queue<T>();
	}

	~StackUsingQueues() {
		delete q1;
		delete q2;
	}

	
	bool empty() {
		/*Stack is empty only if both queues are empty*/
		if (q1->empty() && q2->empty())
			return true;

		return false;
	}


	void push(T new_element) {
		/*Add element to the end of queue q1*/
		q1->push(new_element);
	}

 

	T pop() {
		/*If stack is empty, then throw an exception*/
		if (empty())
			throw exception();

		T e;
		/*Remove all elements from q1 and add it to q2 except the last item*/
		while (q1->size() > 1) {
			e = q1->front();
			q1->pop();
			q2->push(e);
		}

		/*Remove the last element in q1. It will contain the top of stack*/
		e = q1->front();
		q1->pop();

		/*Swap the queues q1 and q2*/
		queue<T> *temp = q1;
		q1 = q2;
		q2 = temp;

		return e; /*Return the top of the stack*/
	}

};

Java


class StackUsingQueues <T> {
	private Queue<T> q1;
	private Queue<T> q2;

	public StackUsingQueues () {
		q1 = new LinkedList<T>();
		q2 = new LinkedList<T>();
	}

	public boolean isEmpty() {
		/*Stack is empty if q1 is empty*/
		if (q1.isEmpty())
			return true;
		return false;
	}
	
	public void push(T newElement) {
		/*Add elements only to queue q1*/
		q1.add(newElement);
	}

	public T pop() {
		if (isEmpty()) 
			return null;

		/*Remove all elements from q1 and add it to q2 except the last item*/
		T e;
		while (q1.size() > 1) {
			e = q1.remove();
			q2.add(e);
		}
		
		/*Remove the last element in q1. It will contain the top of stack*/
		e = q1.remove();
 
		/*Swap q1 and q2*/
		Queue<T> temp = q1;
		q1 = q2;
		q2 = temp;
		
		return e; /*Return the top of the stack*/
	}

}

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 StackUsingQueues(object):
	def __init__(self):
		#Create the internal queues
		self.q1 = queue.Queue()
		self.q2 = queue.Queue()

	def empty(self): 
		#Stack is empty if q1 is empty
		if (self.q1.empty()):
			return True
		return False
	
	def push(self, new_element): 
		#Add elements only to queue q1
		self.q1.put(new_element)
	
	def pop(self): 
		if (self.q1.empty()):
			return None

		#Remove all elements from q1 and add it to q2 except the last item
		while (self.q1.qsize() > 1): 
			e = self.q1.get()
			self.q2.put(e)
		
		#Remove the last element in q1. It will contain the top of stack
		e = self.q1.get()

		#Swap q1 and q2
		self.q1, self.q2 = self.q2, self.q1

		return e #Return the top of the stack

Case 2: Pop is more efficient than push

When an element is pushed to the stack, the element is enqueued in Q1. All the elements of Q2 are dequeued and enqueued in Q1. Rename Q1 as Q2 and Q2 as Q1. So Q2 will always contain elements in the reverse order of insertion.
When an element is popped from the stack, a dequeue operation is performed on Q2 to obtain the element at the top of the stack.

Queue using stacks

admin / / Data Structures, Stacks and Queues

© 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