Queue Data Structure

Queue Data Structure:

Queue is an abstract data structure, similar to Stacks. Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.

A real-world example of queue can be a queue of people at the ticket windows and bus-stops where the person who comes enters first, exits first. More real-world examples can be seen as vehicles at toll gate etc.

Queue can be implemented using Arrays, Linked-lists, Pointers and Structures.

For the sake of simplicity here queues are implemented using one-dimensional array.

Basic Operations

Queue operations may adding an item, remove an item, display etc.,

enqueue() or insert() − adding an element at the rear end of the queue

Algorithm for Enqueue :

insert(Q, front, rear, item)

Step 1:If rear>= Size -1 Print “Queue overflow” Return.

Step 2: increment rear = rear+1

Step 3:insert the element Q[rear]=item

Step 4: check front if queue is empty 

            if front =-1 then 

                  front=0

Step 5: Exit

dequeue() or remove() – removing an element from the front end of the queue

Algorithm for Dequeue :

delete (Q, front, rear)
Step 1:if front=-1 then 
              Print “Queue underflow” 
              Return.
Step 2: remove the element item = Q[front]
Step 3: if front=rear then 
                      rear=front=-1 
            else 
                      front=front+1
Step 4:return(item)

Additional Operations:

• isfull() − Checks if the queue is full.
• isempty() − Checks if the queue is empty.

Exceptions:

• Queue Overflow: occurs when an insert operation is performed on a Queue which is already full.
• Queue Underflow: Occurs when a delete operation is performed on an empty queue.

Java implementation of Queue:

//Program to implement Queue operations using Arrays

import  java.util.*;

class Queue

{

long que[];

    int front,rear;

    public Queue(int size)

    {

        que=new long[size];

        front=rear=-1;

    }

    public boolean isFull()

    {

        return (rear>=que.length-1);

    }

    public boolean isEmpty()

    {

        return (front==-1);

    }

    public void insert(long item)

    {

        if(isFull())

        {

            System.out.println("Queue is Full");

            return;

        }

        que[++rear]=item;

        if(front==-1)

            front++;

    }

    public void delete()

    {

        if(isEmpty())

        {

            System.out.println("Queue is Empty");

            return;

        }

        long item=que[front];

        if(front==rear)

            front=rear=-1;

        else

            front++;

        System.out.println("Removed element from Queue is :"+item);

    }

    public void display()

    {

        System.out.print("Queue :[ ");

        for(int i=front;i<=rear && !isEmpty();i++)

            System.out.print(que[i]+" ");

        System.out.println("]");

    }

}

public class QueueApp

{

  public static void main(String args[])

  {

    Scanner  s=new Scanner(System.in);

    Queue  Q=new Queue(5);

    long item;

    while(true)

    {

      System.out.println("********** MENU **********");

      System.out.println("1. Insert\n2. Delete\n3. Display\n4. Exit");

      System.out.println("Please enter your option:");

      int choice =s.nextInt();

      switch(choice)

      {

        case 1:

          System.out.println("Enter an element into the Queue:");

          item=s.nextLong();

          Q.insert(item);

          break;

        case 2:

          Q.delete();

          break;

        case 3:

          Q.display();

          break;

        case 4:

          System.exit(0);

        default:

          System.out.println("Wrong option");               

            }

        }

    }

}