Queue in Data Structure and Implementation in Java

Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). One end is used to insert data (enqueue) and other end is used to remove data (dequeue). A real world example of the queue can be atm line which follows First In First Out strategy.

Operations on Queue:

Mainly the following four basic operations are performed on queue: Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition. Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition. Front: Get the front item from queue. Rear: Get the last item from queue. Below diagram shows queue implementation. Queue Implementation In Array

Array implementation Of Queue:

For implementing queue, we need to keep track of two indices, front and rear. We enqueue an item at the rear and dequeue an item from front. If we simply increment front and rear indices, then there may be problems, front may reach end of the array. The solution to this problem is to increase front and rear in circular manner (See this for details)
/**
 * 
 */
package queue;
import stack.Array_Stack_Impl;
import java.util.Scanner;
/**
 * @author namdeva
 * 
 */
public class ArrayQueue_Impl {
    static int capacity = 0;
    int queue[] = new int[capacity];
    int front = 0;
    int rare = 0;
    int count=0;

Add method -

public void add(int data) throws QueueException{
        if(rare>capacity){
            throw new QueueException("Queue_Over_Flow");
        }else{
            queue[rare]=data;
            rare++;
            count++;
        }
    }

Remove method -

public int remove() throws QueueException{
        int value;
        if(count<=0){
            throw new QueueException("Queue_Under_Flow");
        }else{
        value=queue[front];
        queue[front]=0;
            front++;
            count--;
        }
        return value;
    }

isEmpty mehtod -

public boolean isEmpty(){
        boolean flag=false;
        if(count==0){
            flag=true;
        }
        return flag;
    }
    public void display(){
        int local=front;
        if(count==0){
            System.out.println("No element to dispaly");
            return;
        }
        while(local<rare){
            System.out.print(queue[local]+" ");
            local++;
        }
        System.out.println("");
    }
    public static void main(String args[]) throws QueueException{
        Scanner sc = new Scanner(System.in);
        System.out.println("Please initialize the size of queue");
        capacity = sc.nextInt();
        ArrayQueue_Impl queue = new ArrayQueue_Impl();
        queue.add(5);
        queue.add(15);
        queue.add(25);
        queue.add(35);
        queue.add(45);
        queue.add(55);
        queue.remove();
        queue.remove();
        queue.remove();
        queue.remove();
        queue.remove();
        queue.display();
        System.out.println(queue.isEmpty());
        sc.close();
    }
}

Exception Handling -

class QueueException extends Exception {
    QueueException(String s) {
        super(s);
    }
}
 

Leave a Comment

%d bloggers like this: