Java Program To Implement Stack Using Two Queues

Chapter: Interview Programs Last Updated: 30-10-2016 16:37:02 UTC

Program:

            /* ............... START ............... */
                
import java.util.*;

class stackUsingQueue {
	Queue<Integer> q;
	Queue<Integer> tmp;

	/* Constructor */
	public stackUsingQueue() {
		q = new LinkedList<Integer>();
		tmp = new LinkedList<Integer>();
	}

	/* Function to push an element to the stack */
	public void push(int data) {
		/*
		 * if no element is present in queue q then enqueue the new element into
		 * q
		 */
		if (q.size() == 0)
			q.add(data);
		else {
			/*
			 * if elements are present in q then dequeue all the elements to
			 * temporary queue tmp
			 */
			int l = q.size();
			for (int i = 0; i < l; i++)
				tmp.add(q.remove());
			/* enqueue the new element into q */
			q.add(data);
			/*
			 * dequeue all the elements from temporary queue tmp to q
			 */
			for (int i = 0; i < l; i++)
				q.add(tmp.remove());
		}
	}

	/* Function to remove top element from the stack */
	public int pop() {
		if (q.size() == 0)
			throw new NoSuchElementException("Underflow Exception");
		return q.remove();
	}

	/* Function to check the top element of the stack */
	public int peek() {
		if (q.size() == 0)
			throw new NoSuchElementException("Underflow Exception");
		return q.peek();
	}

	/* Function to check if stack is empty */
	public boolean isEmpty() {
		return q.size() == 0;
	}

	/* Function to get the size of the stack */
	public int getSize() {
		return q.size();
	}

	/* Function to display the status of the stack */
	public void display() {
		System.out.print("\nStack = ");
		int l = getSize();
		if (l == 0)
			System.out.print("Empty\n");
		else {
			Iterator it = q.iterator();
			while (it.hasNext())
				System.out.print(it.next() + " ");
			System.out.println();
		}
	}
}

public class JavaStackImplementUsingTwoQueues {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		stackUsingQueue suq = new stackUsingQueue();
		/* Perform Stack Operations */
		System.out.println("Stack Using Two Queues Test\n");
		char ch;
		do {
			System.out.println("\nStack Operations");
			System.out.println("1. push");
			System.out.println("2. pop");
			System.out.println("3. peek");
			System.out.println("4. check empty");
			System.out.println("5. size");
			int choice = scan.nextInt();
			switch (choice) {
			case 1:
				System.out.println("Enter integer element to push");
				suq.push(scan.nextInt());
				break;
			case 2:
				try {
					System.out.println("Popped Element = " + suq.pop());
				} catch (Exception e) {
					System.out.println("Error : " + e.getMessage());
				}
				break;
			case 3:
				try {
					System.out.println("Peek Element = " + suq.peek());
				} catch (Exception e) {
					System.out.println("Error : " + e.getMessage());
				}
				break;
			case 4:
				System.out.println("Empty status = " + suq.isEmpty());
				break;
			case 5:
				System.out.println("Size = " + suq.getSize());
				break;
			default:
				System.out.println("Wrong Entry \n ");
				break;
			}
			/* Display Stack */
			suq.display();
			System.out.println("\nDo you want to continue (Type y or n) \n");
			ch = scan.next().charAt(0);
		} while (ch == 'Y' || ch == 'y');
	}
}
                /* ............... END ............... */
        

Output

Stack Using Two Queues Test
 
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
4
Empty status = true
 
Stack = Empty
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
1
Enter integer element to push
5
 
Stack = 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
1
Enter integer element to push
99
 
Stack = 99 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
1
Enter integer element to push
73
 
Stack = 73 99 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
1
Enter integer element to push
50
 
Stack = 50 73 99 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
1
Enter integer element to push
1
 
Stack = 1 50 73 99 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
1
Enter integer element to push
24
 
Stack = 24 1 50 73 99 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
5
Size = 6
 
Stack = 24 1 50 73 99 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
3
Peek Element = 24
 
Stack = 24 1 50 73 99 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
2
Popped Element = 24
 
Stack = 1 50 73 99 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
2
Popped Element = 1
 
Stack = 50 73 99 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
2
Popped Element = 50
 
Stack = 73 99 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
2
Popped Element = 73
 
Stack = 99 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
1
Enter integer element to push
2
 
Stack = 2 99 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
2
Popped Element = 2
 
Stack = 99 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
2
Popped Element = 99
 
Stack = 5
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
2
Popped Element = 5
 
Stack = Empty
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
3
Error : Underflow Exception
 
Stack = Empty
 
Do you want to continue (Type y or n)
 
y
 
Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size
4
Empty status = true
 
Stack = Empty
 
Do you want to continue (Type y or n)
 
n

Notes:

  • Stack is a particular kind of abstract data type or collection in which the principal (or only) operations on the collection are the addition of an entity to the collection, known as push and removal of an entity, known as pop. The relation between the push and pop operations is such that the stack is a Last-In-First-Out (LIFO) data structure.
  • Queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure.
  • Stack can be implemented using two queues. Algorithm is as follows :
  • Create two queues : 'q' and 'tmp' as in the program given below
  • For push operation :
  • if size of q = 0 then
  • enqueue value into q
  • else
  • dequeue all elements from q to tmp
  • enqueue value into q
  • dequeue all elements from tmp to q
  • For pop operation :
  • if size of q = 0 then
  • throw 'underflow' exception
  • else
  • return front element of q

Tags

Implement Stack Using Two Queues, Java, Interview Programs

Similar Programs Chapter Last Updated
Java Program To Find Frequency Of Character In String Interview Programs 28-09-2017
Java Program To Find Power Of Number Using While Loop Interview Programs 30-08-2017
Java Program To Count Divisors Of Integer Number Interview Programs 24-06-2017
Java Program To Sort N Names In Ascending Order Interview Programs 24-06-2017
Java Program To Count Total Number Of Words In String Interview Programs 24-06-2017
Java Program To Print All Prime Numbers From 1 to N Interview Programs 24-06-2017
Java Program To Extract Digits / Numbers From String Interview Programs 22-09-2018
Java First Repeated Character In String Interview Programs 16-05-2017
Java String Character Repetition Count Interview Programs 15-05-2017
Java Program To Check Vowel Or Not Interview Programs 25-09-2018
Java Program To Check Alphabet Or Not Interview Programs 06-04-2017
Java Program To Find First Repeated And Non Repeated Character In String Interview Programs 25-03-2017
Java Spiral Matrix Interview Programs 22-09-2018
Java Program To Reverse A Number Using Strings Interview Programs 13-02-2017
Java Program To Print Diamond Star Pattern Interview Programs 16-12-2016
Java Program To Print Pyramid Pattern Of Star Interview Programs 16-12-2016
Java Program To Find Second Largest Number In Array Interview Programs 04-12-2016
Java Depth First Search Interview Programs 04-12-2016
Java Breadth First Search Interview Programs 04-12-2016
Java Linked List Length Recursive Solution Interview Programs 17-11-2016
Java Linked List Length Iterative Solution Interview Programs 17-11-2016
Java Linked List Node Deletion At Given Position Interview Programs 17-11-2016
Java Linked List Node Delete Interview Programs 17-11-2016
Java Sum Of Digits Using Recursion Interview Programs 06-11-2016
Java Program To Reverse Vowels Of String Interview Programs 05-11-2016
Java Program To Remove Vowels From String Interview Programs 05-11-2016
Java Find Top Two Maximum Numbers In Array Interview Programs 05-11-2016
Java QuickSort Example Interview Programs 05-11-2016
Java Binary Tree Spiral Level Traversal Interview Programs 04-11-2016
Java Binary Tree Preorder Traversal Interview Programs 04-11-2016

1 2 3 4 5