Stack using 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.