Question

Briefly explain what are the chief differences between queues, dequeues and priority queue? How can you determine when it is appropriate to use a queue, a dequeue, or a priority queue? Write a simple example program using any of the 3.

Answer 1

QUEUE: It is a data structure which follows FIFO (First In First Out) property. We use queue when we don't

              want the things to be processed immediately.

Examples: We use this in CPU scheduling and Disk scheduling in order of FIFO.

DEQUE: It is also called as Double Ended Queue. It is extended version of a queue which allows insertion

              and deletion at both the ends so that it will act as both queue and stack. It supports clockwise and

              anti clockwise in O(1) time which will be useful in few applications.

Examples: We can use this to check whether a given string or number is palindrome or not.

                  We can use this for implementing A-Steal job Scheduling algorithm.

                  We can use this for undo and redo operations in several things like text editor or mails or history

                   in a browser.

PRIORITY QUEUE: It is the extended version of queue with the following properties.

                             ->Every item to be inserted into it has priority associated with it.

                            ->Insertion is performed in FIFO order and deletion is performed based on it's priority

                                i.e., the highest priority element is deleted than a lowest priority element.

                            ->If more than 1 elements have same priority then the element which came first will be

                                processed.

Examples: We use this in CPU Scheduling i.e., we've priority Scheduling in operating systems.

                  We use this where ever the priority is involved.

Overview:

->We may use Queue when we just want to implement FIFO property.

->We may use Deque when we need the properties of both the queue and stack.

->We may use the Priority Queue when we encounter priority in a problem which we've to solve.

C program for implementing Queue:

#include<stdio.h>
#include<stdlib.h>
#define MAX 50        //size of queue
void insert();
void delete();
void display();
int queue_array[MAX];
int rear = - 1;
int front = - 1;
int main()
{
    int choice;
    while (1)
    {
        printf("Enter 1 to Insert element to queue: \n");
        printf("Enter 2 to Delete element from queue: \n");
        printf("Enter 3 to Display all elements of queue: \n");
        printf("Enter 4 to Quit: \n");
        printf("Enter your choice : ");
        scanf("%d", &choice);
        switch (choice)
        {
            case 1:insert();
                   break;
            case 2:delete();
                   break;
            case 3:display();
                   break;
            case 4:
                   exit(1);
            default:
                   printf("Wrong choice \n");
        }
    }
}
void insert()
{
    int add_item;
    if (rear == MAX - 1)
    printf("Queue Overflow \n");
    else
    {
        if (front == - 1)
        front = 0;
        printf("Inset the element in queue : ");
        scanf("%d", &add_item);
        rear = rear + 1;
        queue_array[rear] = add_item;
    }
}
void delete()
{
    if (front == - 1 || front > rear)
    {
        printf("Queue Underflow \n");
        return ;
    }
    else
    {
        printf("Element deleted from queue is : %d\n", queue_array[front]);
        front = front + 1;
    }
}
void display()
{
    int i;
    if (front == - 1)

        printf("Queue is empty \n");
    else
    {
        printf("Queue is :\n");
        for (i = front; i <= rear; i++)
            printf("%d ", queue_array[i]);
        printf("\n");
    }
}

Sample output: