Tuesday, May 3, 2022

Stack implementation using two Queue

Stack implementation using two Queues

Push : 
  • To push elements in Stack we are using two Queues q1 and q2.
  • q1 is using as main queue.
  • q2 is using as temporary queue.
  • If queue1 is empty, add elements to q1
  • If q1 is not empty, than first add (shift) all elements from q1 to q2, add new element (current element) to q1 and copy(re-add) all elements from q2 to q1.
Pop : 
  • q1 will be use to pop elements from stack (simply remove element from q1)
Lets understand by below image.

package com.javaiq.in;

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

public class StackImplUsingTwoQueues {

	Queue<Integer> q1;
	Queue<Integer> q2;

	StackImplUsingTwoQueues() {
		q1 = new LinkedList<Integer>();
		q2 = new LinkedList<Integer>();

	 * Before add new element in q1, q1 must be empty,
	 * if q1 is not empty then shift all element of q1 to q2,
	 * after adding new element in q1, re-add all element from q2 to q1
	public void push(int i) {
		if (q1.size() == 0) {
			/* As q1 is empty so add new element into q1 */
		} else {
			int sizeOfQueue1 = q1.size();

			// Copy or shift all elements from q1 to q2
			for (int j = 0; j < sizeOfQueue1; j++) {

			/* Add new element */

			// Copy or re-add elements from q2 to q1
			for (int k = 0; k < sizeOfQueue1; k++) {

	public int pop() {
		if (q1.size() == 0)
			throw new NoSuchElementException("Underflow Exception");
		return q1.remove();
Test Program:
public static void main(String[] args) {
		StackImplUsingTwoQueues stack = new StackImplUsingTwoQueues();
		System.out.println("Removed element from stack : " + stack.pop());
		System.out.println("Removed element from stack : " + stack.pop());
Removed element from stack : 11
Removed element from stack : 15
As per the output we can see last pused element is 15, and pop element is 15.

Related Tutorial 

No comments:

Post a Comment