Queue Data Structure and Its Operations

A queue is a type of data structure where elements are added at one end called the rear and removed from the other end called the front. It works on the FIFO principle – First In, First Out, which means the element that goes in first will come out first, just like a line of people waiting at a ticket counter.

Queues are used in many real-life applications, like printing tasks, CPU scheduling, call center systems, and any situation where things need to be processed in the order they arrive. Basic operations of a queue include enqueue (to add an element), dequeue (to remove an element), peek/front (to see the front element), and isEmpty (to check if the queue is empty).

What is Queue ?

A Queue is a linear data structure that stores elements in a specific order, where the insertion of elements happens at one end called the rear, and the deletion of elements happens at the other end called the front. It follows the FIFO (First-In, First-Out) principle meaning the element that is inserted first will be the first to be removed.

In simpler terms, you can imagine a queue as a line of people waiting at a ticket counter. The person who comes first will get served first, and the person who comes last will have to wait for everyone ahead of them to finish. This natural real-world scenario perfectly represents how a queue works in computer science.

The two fundamental operations of a queue are enqueue (for adding an element to the queue) and dequeue (for removing an element from the queue).

Basic Queue Operations

A queue provides a set of standard operations that allow insertion, deletion, viewing, and displaying elements effectively. These operations include:

1. Enqueue
2. Dequeue
3. Peek (Front)
4. Display

1. Enqueue

The enqueue operation is used to add an element into the queue from the rear end. Before adding a new element, the system checks for a condition called overflow.

Overflow occurs when we try to insert an element into a queue that is already full — meaning there’s no more space left to store new data. In an array-based queue, if the size of the queue is MAX, overflow happens when REAR = MAX – 1. (We use MAX – 1 because array indexing starts from 0.)

In this operation, if the queue is not full, the REAR pointer is incremented, and the new item is inserted at that position.

Example:
Imagine you’re standing in line to buy a movie ticket. Each new person joins the end of the line this is like adding an element using the enqueue operation. The first person who joins will be the first to get the ticket and leave the line, which clearly demonstrates the FIFO principle of a queue.

2. Dequeue

The dequeue operation is used to remove an element from the front of the queue. This operation works on the FIFO principle  the element that entered the queue first is also the one that leaves first.

Before removing an element, we must check for an underflow condition.
Underflow occurs when we try to remove an element from an empty queue, meaning there are no elements left to delete.

When both FRONT = -1 and REAR = -1, it indicates the queue is empty. If the queue contains elements, the FRONT pointer is incremented to point to the next element in the sequence after deletion.

Example:
Imagine you are at a bus stop where people are boarding the bus in the same order they arrived. The first person in the line boards first this is exactly like performing a dequeue operation in a queue.

3. Peek

The peek operation allows you to view the element at the front of the queue without actually removing it. This operation is often used when you want to check which element is next in line for processing.

Before performing the peek operation, it’s essential to verify whether the queue is empty. If both FRONT = -1 and REAR = -1, it means there are no elements to peek, and an appropriate message should be displayed. Otherwise, the value at the FRONT is retrieved and shown.

Example:
Think of a coffee shop where the barista looks at the next order on the screen to prepare it. The barista can see (peek) the next order but doesn’t remove it from the system yet. This ensures the correct order is prepared next while maintaining the serving order similar to the peek operation in a queue.

4. Display

The display operation prints all the elements currently present in the queue — starting from the front to the rear. This helps to visualize the current state of the queue and understand how many items are waiting to be processed.

Example:
Consider the flight information display screens at airports. They show a list of arriving and departing flights, their statuses, gates, and timings. This is similar to the display operation in a queue, where all the data (flights) currently in the system are shown to the user, helping them make informed decisions based on the displayed information.

C Program

#include <stdio.h>
#define MAX 5

int queue[MAX];
int front = -1, rear = -1;

// Enqueue operation
void enqueue(int value) {
    if (rear == MAX - 1) {
        printf("Queue Overflow\n");
    } else {
        if (front == -1) front = 0;
        rear++;
        queue[rear] = value;
        printf("%d enqueued to queue\n", value);
    }
}

// Dequeue operation
void dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue Underflow\n");
    } else {
        printf("%d dequeued from queue\n", queue[front]);
        front++;
    }
}

// Peek operation
void peek() {
    if (front == -1 || front > rear) {
        printf("Queue is empty\n");
    } else {
        printf("Front element: %d\n", queue[front]);
    }
}

// Display operation
void display() {
    if (front == -1 || front > rear) {
        printf("Queue is empty\n");
    } else {
        printf("Queue elements: ");
        for (int i = front; i <= rear; i++) {
            printf("%d ", queue[i]);
        }
        printf("\n");
    }
}

// Main function
int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    
    peek();
    dequeue();
    display();
    
    peek();
    enqueue(40);
    enqueue(50);
    enqueue(60); // Queue Overflow
    display();
    
    return 0;
}

Output

10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
Queue elements: 10 20 30
Front element: 10
10 dequeued from queue
Queue elements: 20 30
Front element: 20
40 enqueued to queue
50 enqueued to queue
Queue Overflow
Queue elements: 20 30 40 50

Explanation

The above C program implements a queue using an array. It uses an array queue[MAX] to store elements, with front pointing to the first element and rear pointing to the last. Initially, both are set to -1, meaning the queue is empty. The enqueue function adds an element at the rear if the queue is not full, updating front to 0 if it’s the first element. The dequeue function removes the element at the front if the queue is not empty and moves front forward. The peek function shows the front element without removing it, and the display function prints all elements from front to rear. The main function demonstrates all these operations while maintaining the FIFO (First In First Out) order of the queue.

Time & Space Complexity

Time Complexity

Space Complexity