Stack using two Queues in Java

This post explains Stack data structure implementation using two queues in Java. The implementation uses Stack and Queue classes available from java.util package.

Prerequisites :

Knowledge of Java, data structures, stack data structure and the operations that can be performed on it. Basics of queues and knowledge of FIFO implementation is required.

Explanation :

The basic idea is to perform stack ADT operations using two queues. The queues used for this implementation are from java.util package.

If you want to learn more about the operations that can be performed on the stack visit java.util.Stack common operations

Algorithm :

1. Declare two queues q1 and q2.
2. For the push operation, enqueue an element to q1.
3. For the pop operation –
   • Check if the queue q2 is not empty.
   • If it is empty, then dequeue all the elements from q1 except the last element and enqueue it to q2.
   • Dequeue the remaining element from q1 and store it as the popped element in a variable.
   • Swap the queues q1 and q2.
   • Return the stored popped element.
4. For peek operation –
   • Check if the queue q2 is not empty.
   • If it is empty, then dequeue all the elements from q1 except the last element and enqueue it to q2.
   • Dequeue the remaining element from q1 and store it as the peeked element in a variable.
   • Enqueue the above peeked element to q2.
   • Swap the queues q1 and q2.
   • Return the stored peeked element.

Implementation of above algorithm :

import java.util.LinkedList;
import java.util.Queue;

public class StackUsing2Queues {

	java.util.Queue<Integer> q1;
	java.util.Queue<Integer> q2;
	int SIZE;

	public StackUsing2Queues() {
		q1 = new LinkedList<Integer>();
		q2 = new LinkedList<Integer>();
		SIZE = 0;

	}

	/** Push element x onto stack. */
	public void push(int x) {
		q1.add(x);
		SIZE++;

	}

	/** Removes the element on top of the stack and returns that element. */
	public int pop() {
		ensureQ2IsNotEmpty();
		int poppedEle = q1.remove();
		SIZE--;
		swapQueues();
		return poppedEle;
	}

	/** Get the top element. */
	public int top() {
		ensureQ2IsNotEmpty();
		int peekedEle = q1.remove();
		q2.add(peekedEle);
		swapQueues();
		return peekedEle;
	}

	/** Returns whether the stack is empty. */
	public boolean empty() {
		return q1.isEmpty() && q2.isEmpty();

	}

	/** Ensure that queue q2 is not empty */
	public void ensureQ2IsNotEmpty() {
		for (int i = 0; i < SIZE - 1; i++) {
			q2.add(q1.remove());
		}
	}

	/** Swap queues q1 and q2 */
	public void swapQueues() {
		Queue<Integer> temp = q1;
		q1 = q2;
		q2 = temp;
	}

	public static void main(String[] args) {
		StackUsing2Queues s = new StackUsing2Queues();
		s.push(1);
		s.push(2);
		s.push(3);
		System.out.println(s.top());
		s.pop();
		System.out.println(s.top());
		s.push(4);
		System.out.println(s.top());

	}
}

Code output :

3
2
4

Here is the link to the above code on my github profile, Stack using 2 queues.

If this post helped you to learn something new please do share and like it. Your feedback is highly appreciated.