Java Program to Implement Queue Using Two Stacks

This is a Java Program to implement a queue using two stacks.

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

However a queue can be implemented using two stacks. Algorithm is as follows :

Create two stacks : 's' and 'tmp' as in the program given below
For insert operation :
    if size of s = 0 then
        push value into s
    else
        push all popped elements from s to tmp
        push value into s
        push all popped elements from tmp to s
 
For remove operation :
    if size of s = 0 then
        throw 'underflow' exception
    else 
        return pop element from s

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

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

Queue Using Two Stacks Test
 
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
4
Empty status = true
 
Queue = Empty
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
1
Enter integer element to insert
99
 
Queue = 99
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
1
Enter integer element to insert
162
 
Queue = 99 162
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
1
Enter integer element to insert
3
 
Queue = 99 162 3
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
1
Enter integer element to insert
77
 
Queue = 99 162 3 77
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
1
Enter integer element to insert
42
 
Queue = 99 162 3 77 42
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
1
Enter integer element to insert
67
 
Queue = 99 162 3 77 42 67
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
1
Enter integer element to insert
34
 
Queue = 99 162 3 77 42 67 34
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
5
Size = 7
 
Queue = 99 162 3 77 42 67 34
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
3
Peek Element = 99
 
Queue = 99 162 3 77 42 67 34
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
2
Removed Element = 99
 
Queue = 162 3 77 42 67 34
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
2
Removed Element = 162
 
Queue = 3 77 42 67 34
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
2
Removed Element = 3
 
Queue = 77 42 67 34
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
2
Removed Element = 77
 
Queue = 42 67 34
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
2
Removed Element = 42
 
Queue = 67 34
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
2
Removed Element = 67
 
Queue = 34
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
2
Removed Element = 34
 
Queue = Empty
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
3
Error : Underflow Exception
 
Queue = Empty
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
5
Size = 0
 
Queue = Empty
 
Do you want to continue (Type y or n)
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
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 & discussions at Telegram SanfoundryClasses.