Queue in Data Structure

What is Queue?
  • Queue is linear data structure.
  • Queue works with the principle FIFO(First In First Out). It means the element is inserted first is taken out first.
  • The elements in a queue are added at one end called the REAR and removed from the other end called the FRONT.
  • In the computer’s memory, queue can be implemented using both array and linked lists.
Application of Queue
  • Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
  • Queues are used as buffers on MP3 players and portable CD players, iPod playlist.
  • Queues are used in operating system for handling interrupts.
Array representation of Linear Queue

Queue can be easily represented using linear arrays, every queue has front and rear variables that point to the position from where deletion and insertions can be done, respectively.

Queue in data structure
The array representation of Queue
Algorithm for insert an element in a queue
Step 1: If Rear=Max-1
     write overflow 
      Goto step 4
Step 2: If Front=-1 and Rear=-1
       Set Front=Rear=0
       Else
       Set Rear=Rear+1
Step 3: Set Queue[Rear]=Num
Step 4: Exit
Algorithm for delete an element in a queue
Step 1: If Front=-1 or Front>Rear
       write underflow
       else
       Set val=Queue[front]
       Set Front=Front+1;
Step 2: Exit;
Program for Linear Queue
#include<stdio.h>
#include<stdlib.h>
#define size 4
int queue[size];
int front=-1;
int rear=-1;
void insert()
{
    int data;
    if(rear==size-1)
    {
        printf("Queue is full");
    }
    else
    {
            if(rear==-1&&front==-1)
                   front=0;
            printf("\nEnter data which you want to insert in queue:");
            scanf("%d",&data);
            rear=rear+1;
            queue[rear]=data;

    }
}
void delete1()
{
    if((rear==-1&&front==-1)||front>rear)
    {
        printf("\nQueue is empty");
    }
    else
        {
             printf("Deleted element =%d",queue[front]);
             front=front+1;
        }
}
void show()
{
    int i;
    for(i=front;i<=rear;i++)
        printf("%d,",queue[i]);
}
void main()
{
        int choice;
        while(1)
        {
            printf("\nSelect choice:\nPress 1: insert\nPress 2: Delete\nPress 3: Show\nPress 4: Exit ");
            printf("__Enter your choice :");
            scanf("%d",&choice);
            switch(choice)
            {
                case 1:
                    insert();
                    break;
                case 2:
                    delete1();
                    break;
                case 3:
                    show();
                    break;
                case 4:
                    exit(0);
                default:
                    printf("Invalid choice");
            }
        }
}

Output:

Linear Queue output
Output of Linear Queue Program
Drawback of Linear Queue

In queue, insertion are always done at one end is called rear and deletion are always done from other end is called front.

Linear Queue

Now, if you want to insert another value, it will not be possible because the queue is completely full.

Liner Queue

Consider a scenario in which two elements are deleted. Suppose we want to insert a new element in the queue even space is available, we can’t insert because the overflow condition(Rear=max-1) still holds true. This is the drawback of linear queue.

Array Representation for Circular Queue

The drawback of linear queue is solved in circular queue. In the circular queue, the first index comes right after the last index. The circular queue will be full when Front=0 and Rear=max-1 or Front=Rear+1. A circular queue is implemented in the same manner as a linear queue is implemented. The only difference will be in the code that performs insertion and deletion operations.

Array Representation of Circular Queue
Algorithm for insert an element in circular queue
Step 1: If Front=0 and Rear=Max-1 or Front=Rear+1
    write Overflow
     Goto Step 4
Step 2: If Front=-1 and Rear==-1
   Set Front=Rear=0
    else
   Rear=(Rear+1)%Max
Step 3: Set Queue[Rear]=Value
Step 4: End
Algorithm for Delete an element in circular queue
Step 1: If Front=-1 and Rear=-1
    write Underflow
   Goto Step 4
Step 2: val=Queue[Front]
Step 3: If Front=Rear
   Set Front=Rear=-1
   else
   Front=(Front+1)%Max
Step 4: End
C Program for Circular Queue
#include<stdio.h>
#include<stdlib.h>
#define size 3
int queue[size];
int front=-1;
int rear=-1;
void insertq()
{
    int data;
    if((front==0&&rear==size-1)||front==rear+1)
    {
        printf("Queue is full\n");
    }
    else if(rear==-1&&front==-1)
     {
             rear=0;
            front=0;
            printf("\nEnter value which you want to insert in queue:");
            scanf("%d",&data);
            queue[rear]=data;
    }
    else{
        printf("\nEnter value which you want to insert in queue:");
        scanf("%d",&data);
        rear=(rear+1)%size;
        queue[rear]=data;
    }
}
void deleteq()
{
    if(rear==-1&&front==-1)
    {
        printf("\nQueue is empty\n");
    }
    else if(front==rear)
    {
         printf("Deleted element =%d\n",queue[front]);
        front=-1;
        rear=-1;
    }
    else
        {
             printf("Deleted element =%d\n",queue[front]);
             front=(front+1)%size;
        }
}
void show()
{

    if(front==-1)
        printf("Queue is empty\n");
    else
    {
             int i=front;
             printf("Elements of Queue : ");
             if(front<=rear)
             {
                      while(i<=rear)
                           printf("%d,",queue[i++]);
             }
             else
             {
                  while(i<=size-1)
                    printf("%d,",queue[i++]);
                  i=0;
                  while(i<=rear)
                    printf("%d,",queue[i++]);
             }
             printf("\n");
     }
}

void main()
{
    int choice;
    while(1)
    {
        printf("\nSelect choice:\nPress 1: insert\nPress 2: Delete\nPress 3: Show\nPress 4: Exit");
        printf(" __Enter your choice :");
        scanf("%d",&choice);
        switch(choice)
        {
            case 1:
                insertq();
                break;
            case 2:
                deleteq();
                break;
            case 3:
                show();
                break;
            case 4:
                exit(0);
            default:
                printf("Invalid choice\n");
        }
    }
}

Output :

Output of Circular Queue
Output of Circular Queue
Question of circular Queue

Question : Let COLOURS[0,3] be a circular queue data structure. Note the actual physical capacity of the queue is only 3 despite the declaration of the array ar[0,3]. The operations illustrated below

  1. Insert ‘Orange’ into COLOUR[0,3]
  2. Insert ‘Blue’ into COLOUR[0,3]
  3. Insert ‘White’ into COLOUR[0,3]
  4. Insert ‘Red’ into COLOUR[0,3]
  5. Delete twice from COLOUR[0,3]
  6. Insert ‘Yellow’ into COLOUR[0,3]
  7. Insert ‘Violet’ into COLOUR[0,3]

Solution :

#include<stdio.h>
#include<stdlib.h>
#define size 4
char queue[size][20];
int front=-1;
int rear=-1;
void insert()
{
    if((front==0&&rear==size-1)||front==rear+1)
    {
        printf("Queue is full\n");
    }
    else if(rear==-1&&front==-1)
     {
             rear=0;
            front=0;
            printf("\nEnter Colour name which you want to insert :");
            scanf("%s",queue[rear]);

    }
    else
    {
        rear=(rear+1)%size;
        printf("\nEnter Colour name which you want to insert :");
        scanf("%s",queue[rear]);
    }
}
void delete1()
{
    if(rear==-1&&front==-1)
    {
        printf("\nQueue is empty");
    }
    else if(front==rear)
    {
         printf("Deleted element =%s\n",queue[front]);
        front=-1;
        rear=-1;
    }
    else
        {
             printf("Deleted element =%s\n",queue[front]);
             front=(front+1)%size;
        }
}
void show()
{
     if(front==-1)
        printf("Queue is empty\n");
    else
    {
             int i=front;
             printf("Colours in Queue : ");
             if(front<=rear)
             {
                      while(i<=rear)
                           printf("%s,",queue[i++]);
             }
             else
             {
                  while(i<=size-1)
                    printf("%s,",queue[i++]);
                  i=0;
                  while(i<=rear)
                    printf("%s,",queue[i++]);
             }
             printf("\n");
     }
}
void main()
{
    int choice;
    while(1)
    {
        printf("\nSelect choice:\nPress 1: insert colour\nPress 2: Delete colour\nPress 3: Show colour\nPress 4: Exit");
        printf(" __Enter your choice :");
        scanf("%d",&choice);
        switch(choice)
        {
        case 1:
            insert();
            break;
        case 2:
            delete1();
            break;
        case 3:
            show();
            break;
        case 4:
            exit(0);
        default:
            printf("Invalid choice");
        }
    }
}

Output :

1
2

Leave a Comment

Your email address will not be published.