Essential Guide to Queues: What They Are and How They Work

Introduction

Whether you're at a railway reservation counter, waiting in line at the movie theater, or submitting print jobs to a network printer, forming a queue is the universal solution to bring order to chaos. By patiently awaiting your turn, you increase the likelihood of receiving better service. Additionally, queues help in maintaining fairness and reducing conflicts among customers. Moreover, queues facilitate a sense of orderliness and civility in public spaces, contributing to a smoother and more pleasant experience for everyone involved.

Applications of queues

Applications of queues as a data structure are even more common than those of stacks. When performing tasks on a computer, it is often necessary to wait your turn before accessing a device or process. Within a computer system, there may be queues of tasks waiting for the printer, disk storage, or CPU in a time-sharing system. Within a single program, there may be multiple requests that need to be kept in a queue, or one task may create other tasks that must be handled in turn by keeping them in a queue.

Queues in Data Structures

Queue is a linear data structure that permits insertion of new element at one end and deletion of an element at the other end. The end at which the deletion of an element take place is called front, and the end at which insertion of a new element can take place is called rear.

Consider a queue of people waiting at a bus stop. Each new person who arrives takes their place at the end of the line, and when the bus comes, the people at the front of the line board first. The first person in the line is the first person to leave.

• The deletion or insertion of elements can take place only at the front or rear end of the list respectively.

• The first element that gets added into the queue is the first one to get removed from the list.

• Hence, a queue is also referred to as a first-in-first-out (FIFO) list.

Operations on queue

1. Enqueue() :

   • If the queue is full, it prints an error message.

   • Otherwise, it increments the rear index and adds the value to the queue array.

   • If the queue was empty before adding the value, the front index is set to 0.

void enqueue(int value)
{
    if (isFull())
        printf("\nQueue is Full!!");
    else
    {
        if (front == -1)
            front = 0;
        rear++;
        queue[rear] = value;
        printf("Inserted -> %d", value);
    }
}

2. Dequeue() :

   • If the queue is empty, it prints an error message.

   • Otherwise, it prints the value at the front index and increments the front index.

   • If the front index becomes greater than the rear index after removing an element, both indices are set to -1 to indicate that the queue is empty.

void dequeue()
{
    if (isEmpty())
        printf("\nQueue is empty!!");
    else
    {
        printf("Deleted value = %d", queue[front]);
        front++;
        if (front > rear)
        {
            front = rear = -1;
        }
    }
}

3. Peek() :

   • This function prints the front element of the queue without removing it.

   • If the queue is empty, it prints an error message.

void peek()
{
    if (isEmpty())
        printf("Queue is empty");
    else
        printf("Front element is %d", queue[front]);
}

4. isEmpty() :

   • This function checks if the queue is empty by comparing the front and rear indices.

   • If they are equal, the queue is empty and the function returns 1.

   • Otherwise, it returns 0.

int isEmpty()
{
    if (front == rear)
        return 1;
    else
        return 0;
}

5. isFull() :

   • This function checks if the queue is full by comparing the rear index with the maximum size of the queue.

   • If they are equal, the queue is full and the function returns 1.

   • Otherwise, it returns 0.

int isFull()
{
    if (rear == MAX - 1)
        return 1;
    else
        return 0;
}

Code

#include <stdio.h>
#define MAX 5
int queue[MAX];
int front = -1;
int rear = -1;

int isEmpty()
{
    if (front == rear)
        return 1;
    else
        return 0;
}

int isFull()
{
    if (rear == MAX - 1)
        return 1;
    else
        return 0;
}

void enqueue(int value)
{
    if (isFull())
        printf("\nQueue is Full!!\n");
    else
    {
        if (front == -1)
            front = 0;
        rear++;
        queue[rear] = value;
        printf("Inserted -> %d\n", value);
    }
}

void dequeue()
{
    if (isEmpty())
        printf("\nQueue is empty!!\n");
    else
    {
        printf("Deleted value = %d\n", queue[front]);
        front++;
        if (front > rear)
        {
            front = rear = -1;
        }
    }
}

void peek()
{
    if (isEmpty())
        printf("Queue is empty");
    else
        printf("Front element is %d\n", queue[front]);
}

void display() {
    if(isEmpty()) {
        printf("Queue is Empty!!!");
    } else {
        printf("\nQueue elements are: ");
        for (int i = front; i <= rear; i++) {
            printf("%d  ", queue[i]);
        }
    }
    printf("\n");
}

int main()
{
    dequeue(); // Queue is empty!!
    enqueue(1); // Inserted -> 1
    enqueue(2); // Inserted -> 2
    enqueue(3); // Inserted -> 3
    enqueue(4); // Inserted -> 4
    enqueue(5); // Inserted -> 5
    enqueue(6); // Queue is Full!!
    peek();     // Front element is 1
    display();  // Queue elements are: 1  2  3  4  5 
    dequeue();  // Deleted value = 1
    dequeue();  // Deleted value = 2
    dequeue();  // Deleted value = 3
    display();  // Queue elements are: 4  5  
    return 0;
}

Thank you! I am glad you made it to the end of this article. I hope you got to learn something :)