Saturday, October 18, 2014

Circular Queue (Fixed Size) Java Implementation

This program implements Circular Queue of Fixed Size.

1. In the beginning, front and end are equal to 0.
2. When we add an item, we increment end to the index next to the index at which we have inserted the new item.
3. Queue is empty if [ front == end ] (Note that end gets incremented to the next index after each insertion, so end is pointing to the index next to the index of the last inserted item)
4. Queue is full if  [ previousIndex(front) == end ]

Source:

import java.util.Scanner;
 
public class CircularQueue {
    private int queue[] = new int[5];
    private int front = 0, end = 0;
     
    private int getNextIndex(int index){
        return (index+1==queue.length)?0:index+1;
    }
    
    private int getPreviousIndex(int index){
        return (index-1==-1)?queue.length-1:index-1;
    }
    
    public boolean isFull(){   
          return getPreviousIndex(front)==end; //End points to (index+1) where index is the last inserted item's index
    }
    
    public boolean isEmpty(){ 
        return front == end; //End points to (index+1) where index is the last inserted item's index
    }
    
    public void enqueue(int add){
        if(isFull()){ System.out.println("Error: Queue is full!"); return;}
        queue[end] = add; 
        end = getNextIndex(end); 
    }
    
    public void dequeue(){
        if(isEmpty()){ System.out.println("Error: Queue is empty!   "); return; }
        front = getNextIndex(front);
    }
    
    public void printQueue(){
        System.out.print("\nPrinting Queue: ");
        if(isEmpty()) {System.out.println("Queue is empty!"); return;}  
        for(int i = front; ; i = getNextIndex(i)){ 
            System.out.print(queue[i]+" ");
            if(i==end-1)break;
        }
        System.out.println();
    }
    
    public void consoleUI(){
        Scanner scan = new Scanner(System.in);
        int choice = 0;
        int item = 0;
        while(true){
           System.out.println("1. Insert\n2. Remove\n3. Is Empty?\n4. Is Full?\n5. Print Queue Contents");
           choice = scan.nextInt();
           
           switch(choice){
               case 1:
                   item = scan.nextInt();
                   while(item!=-999){
                       enqueue(item);
                       item = scan.nextInt();
                   }
                   break;
               case 2:  dequeue(); printQueue(); break;
               case 3:  System.out.println(isEmpty()); break;
               case 4:  System.out.println(isFull()); break;
               case 5:  printQueue(); break;
           }
        }
    }
    
    public static void main(String[] args){
        CircularQueue cq = new CircularQueue();
        cq.consoleUI();
    }
}
 
Sample Run:

1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
1
1 2 3 4
5
Error: Queue is full!
-999
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
2
Printing Queue: 2 3 4
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
2
Printing Queue: 3 4
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
1
5 6
7
Error: Queue is full!
-999
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
5
Printing Queue: 3 4 5 6
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
3
false
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
4
true
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
2
Printing Queue: 4 5 6
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
2
Printing Queue: 5 6
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
2
Printing Queue: 6
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
5
Printing Queue: 6
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
3
false
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
4
false
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
1
7
8
9
10
Error: Queue is full!
-999
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
5
Printing Queue: 6 7 8 9
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
3
false
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents
4
true
1. Insert
2. Remove
3. Is Empty?
4. Is Full?
5. Print Queue Contents

No comments:

Post a Comment