Skip to main content

11. Queue

 

Queue

  • Queue is a linear structure that follows the FIFO(First-in-First-out) principle.
  • Queue has two ends.
  • It contains two pointers Front pointer and Rear pointer pointing the front end and rear ends of the queue respectively.
  • It can also be defined as the list or collection in which the insertion is done from rear end whereas the deletion is done from the front end.

Applications of Queue

  • Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
  • Queues are used to transfer the data where data is not being transferred at the same rate between two processes.
  • Queues are used as buffer in most of the applications like MP3 player, CD player etc.
  • Queue are used to maintain the play list in media players in order to add and remove the songs from the play list.
  • Queues are used in operating systems for handling interrupts.

Types of Queue

There are four types of queue that are listed as:

  1. Linear Queue
  2. Circular Queue
  3. Priority Queue
  4. Double Ended Queue (DEQueue)

Linear Queue

  • Insertion takes place from the rear end.
  • Deletion takes place from the front end.
  • It strictly follows the FIFO rule.

Circular Queue

  • Insertion takes place from the rear end.
  • Deletion takes place from the front end.
  • The last element is connected to the first element.
  • It is also known as Ring Buffer.

Priority Queue

  • The elements are arranged based on the priority.
  • Insertion in priority takes place based on the arrival.
  • Deletion in the priority queue occurs occurs based on the priority.
  • Priority queue is mainly used to implement the CPU scheduling algorithms.
  • Ascending priority queue: Elements can be inserted in arbitrary order, but only smallest can be deleted first.
  • Descending priority queue: Elements can be inserted in arbitrary order, but only the largest element can be deleted first.

Double Ended Queue

  • Insertion can be done from both ends of the queue either from the front or rear.
  • Deletion can also be done from both ends of the queue either from the front or rear.
  • Input restricted dequeue: Insertion operation can be performed at only one end, while deletion can be performed from both ends.
  • Output restricted dequeue: Deletion can be performed at only one end, while insertion can be performed from both ends.

Queue ADT

In order to create a queue, we need two pointers, one pointing to the insertion end and other pointing to the deletion end. Along with that, we need the memory space to hold the elements and their data.

Some of the basic operations one queue are as:

  • enqueue(): To insert an element in a queue.
  • dequeue(): To delete an element from the queue.
  • firstVal(): To return the value which is at the first position.
  • lastVal(): To return the value which is at the last position.
  • isEmpty(): To determine whether the queue is empty or not to carry efficient dequeue operation.
  • isFull(): To determine whether the queue is full or nor to carry efficient enqueue operation.

Array ADT for implementing Queue

struct MyQueue
{
    int max;
    int front;
    int rear;
    int *Base;
} queue;

Linked List ADT for implementing Queue


struct Node
{
    int data;
    struct Node *next;
};
struct Node *front = NULL;
struct Node *rear = NULL;

Algorithm for enqueue() operation in Queue

We assume a queue whose maximum capacity is defined by MAX, front variable represents the front end and rear variable represents the rear end. Also we assume that the front and rear variables starting with the value 0 while pointing the first element.

  1. START
  2. If rear == MAX - 1
    • print "Queue is full, insertion not possible".
  3. Else
    1. If front == -1
      • Set front = front + 1
    2. Set rear = rear + 1
    3. Insert the value in the queue at index of rear.
  4. END
void enqueueArray(struct MyQueue *a)
{
    if ((*a).rear == (*a).max - 1)
        printf("\t\t\tQueue is full, enqueue is not possible...\n");
    else
    {
        if ((*a).front == -1)
            (*a).front++;
        (*a).rear++;
        printf("\t\tEnter the element to be pushed: ");
        scanf("%d", &(*a).Base[(*a).rear]);
        printf("\t\tValue is pushed successfully...");
    }
}


void enqueueLinkedList()
{
    struct Node *node = (struct Node *)malloc(sizeof(struct Node));
    if (node == NULL)
        printf("\t\t\tEnqueue is not possible...");
    else
    {
        printf("\t\tEnter the value to be pushed: ");
        scanf("%d", &(*node).data);
        (*node).next = NULL;
        if (front == NULL)
            front = node;
        else
            (*rear).next = node;
        rear = node;
        printf("\t\tValue is pushed successfully...");
    }
}

Algorithm for dequeue() operation in queue

We assume a queue in which front points the front end and rear points the rear end.

  1. START
  2. If front == -1
    • print "queue is empty, deletion not possible".
  3. Else
    1. print the value at front index of the queue as deleted value.
    2. If front == rear
      • Set front = rear = -1
    3. Else
      • Set front = front + 1
  4. END
void dequeueArray(struct MyQueue *a)
{
    if ((*a).front == -1)
        printf("\t\t\tQueue is empty, dequeue is not possible...\n");
    else
    {
        printf("\t\tPopped value: %d\n", (*a).Base[(*a).front]);
        if ((*a).front == (*a).rear)
            (*a).front = (*a).rear = -1;
        else
            (*a).front++;
    }
}


void dequeueLinkedList()
{
    int item;
    if (front == NULL)
        printf("\t\t\tQueue is empty, dequeue is not possible...");
    else
    {
        printf("\t\tPopped value: %d\n", (*front).data);
        if (front == rear)
            front = rear = NULL;
        else
            front = (*front).next;
    }
}

Comments

Post a Comment