Java Program to Implement Stack using Two Queues

»
This is a Java Program to implement a stack using two queues.

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.

advertisement

However a 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

Here is the source code of the Java program to implement a stack using two queues. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
  1. /*
  2.  *  Java Program to Implement Stack using Two Queues
  3.  */
  4.  
  5. import java.util.*;
  6.  
  7. /* Class stackUsingQueue */
  8. class stackUsingQueue
  9. {
  10.     Queue<Integer> q ;
  11.     Queue<Integer> tmp ;
  12.  
  13.     /* Constructor */
  14.     public stackUsingQueue()
  15.     {
  16.         q = new LinkedList<Integer>();
  17.         tmp = new LinkedList<Integer>();
  18.     }    
  19.     /*  Function to push an element to the stack */
  20.     public void push(int data)
  21.     {
  22.         /* if no element is present in queue q then
  23.          * enqueue the new element into q  */         
  24.         if (q.size() == 0)
  25.             q.add(data);
  26.         else
  27.         {
  28.             /* if elements are present in q then
  29.              * dequeue all the elements to 
  30.              * temporary queue tmp */             
  31.             int l = q.size();
  32.             for (int i = 0; i < l; i++)
  33.                 tmp.add(q.remove());                
  34.             /* enqueue the new element into q */
  35.             q.add(data);        
  36.             /* dequeue all the elements from
  37.              * temporary queue tmp to q */                 
  38.             for (int i = 0; i < l; i++)
  39.                 q.add(tmp.remove());
  40.         }
  41.     }    
  42.     /*  Function to remove top element from the stack */
  43.     public int pop()
  44.     {
  45.         if (q.size() == 0)
  46.             throw new NoSuchElementException("Underflow Exception");        
  47.         return q.remove();
  48.     }    
  49.     /*  Function to check the top element of the stack */
  50.     public int peek()
  51.     {
  52.         if (q.size() == 0)
  53.             throw new NoSuchElementException("Underflow Exception");            
  54.         return q.peek();
  55.     }        
  56.     /*  Function to check if stack is empty */
  57.     public boolean isEmpty()
  58.     {
  59.         return q.size() == 0 ;
  60.     }
  61.     /*  Function to get the size of the stack */
  62.     public int getSize()
  63.     {
  64.         return q.size();
  65.     }    
  66.     /*  Function to display the status of the stack */
  67.     public void display()
  68.     {
  69.         System.out.print("\nStack = ");
  70.         int l = getSize();
  71.         if (l == 0)
  72.             System.out.print("Empty\n");
  73.         else
  74.         {
  75.             Iterator it = q.iterator();
  76.             while (it.hasNext())
  77.                 System.out.print(it.next()+" ");
  78.             System.out.println();
  79.         }
  80.     }
  81. }
  82. /*  Class StackImplementUsingTwoQueues  */
  83. public class StackImplementUsingTwoQueues
  84. {    
  85.     public static void main(String[] args)
  86.     {
  87.         Scanner scan = new Scanner(System.in);      
  88.         stackUsingQueue suq = new stackUsingQueue();                  
  89.         /* Perform Stack Operations */          
  90.         System.out.println("Stack Using Two Queues Test\n");  
  91.         char ch;     
  92.         do 
  93.         {
  94.             System.out.println("\nStack Operations");
  95.             System.out.println("1. push");
  96.             System.out.println("2. pop");
  97.             System.out.println("3. peek");
  98.             System.out.println("4. check empty");
  99.             System.out.println("5. size");            
  100.             int choice = scan.nextInt();
  101.             switch (choice) 
  102.             {
  103.             case 1 : 
  104.                 System.out.println("Enter integer element to push");
  105.                 suq.push( scan.nextInt() );                 
  106.                 break;                          
  107.             case 2 : 
  108.                 try
  109.                 {
  110.                     System.out.println("Popped Element = "+ suq.pop() );
  111.                 }
  112.                 catch (Exception e)
  113.                 {
  114.                     System.out.println("Error : " + e.getMessage());
  115.                 }        
  116.                 break;                         
  117.             case 3 : 
  118.                 try
  119.                 {
  120.                     System.out.println("Peek Element = "+ suq.peek() );
  121.                 }
  122.                 catch (Exception e)
  123.                 {
  124.                     System.out.println("Error : " + e.getMessage());
  125.                 }
  126.                 break;                         
  127.             case 4 : 
  128.                 System.out.println("Empty status = "+ suq.isEmpty() );
  129.                 break;                
  130.             case 5 : 
  131.                 System.out.println("Size = "+ suq.getSize() ); 
  132.                 break;            
  133.             default :  
  134.                 System.out.println("Wrong Entry \n ");
  135.                 break;
  136.             }                 
  137.             /* Display Stack */        
  138.             suq.display();            
  139.             System.out.println("\nDo you want to continue (Type y or n) \n");
  140.             ch = scan.next().charAt(0);            
  141.         } while (ch == 'Y'|| ch == 'y');                 
  142.     }
  143. }

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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.