Queue Operations

A queue is a linear data structure that follows the FIFO (First-In-First-Out) principle. Elements are inserted at the rear and removed from the front.

Let's explore the main queue operations in theory and then implement them using C Programming.

1. Enqueue (Insertion)

Enqueue adds a new element to the rear of the queue. Before inserting, we must check if the queue is full (known as overflow).

If the queue is initially empty, we set both front and rear to 0.

Algorithm:

if REAR == MAX_SIZE - 1 then
    Output "Queue Overflow - Cannot insert new element."
else
    if FRONT == -1 then
        FRONT ← 0
    end if
    REAR = REAR + 1
    QUEUE[REAR] = ITEM
end if

• Adds a new element at the rear end of the queue.
• If the queue is full (rear == MAX_SIZE - 1), it shows an overflow message.
• If inserting the first element, front is set to 0.

2. Dequeue (Deletion)

Dequeue removes the front element from the queue. Before deletion, we must check for underflow, which occurs when the queue is already empty.

If the queue becomes empty after deletion, both front and rear are reset to -1.

Algorithm:

if FRONT == -1 or FRONT > REAR then
    Output "Queue Underflow - No element to remove."
else
    ITEM = QUEUE[FRONT]       // store or display the removed item
    FRONT = FRONT + 1
    if FRONT > REAR then
        FRONT = -1
        REAR = -1             // reset the queue
    end if
end if

• Removes the element from the front of the queue.
• If the queue is empty (front > rear or front == -1), it shows an underflow message.
• If the last element is removed, both front and rear are reset to -1.

3. Peek (Front Element Access)

This operation retrieves the front element without removing it from the queue. It helps to see what will be dequeued next.

Algorithm:

if FRONT == -1 or FRONT > REAR then
    Output "Queue is Empty - No front element."
else
    Output "Front element is: ", QUEUE[FRONT]
end if

• Shows the front element without removing it.
• If the queue is empty, it displays a message.

4. IsEmpty (Check if Queue is Empty)

This checks whether the queue has any elements. A queue is considered empty if front == -1 or front > rear.

Algorithm:

if FRONT == -1 or FRONT > REAR then
    return 1
else
    return 0
end if

5. IsFull (Check if Queue is Full)

This checks whether the queue is full. In a static array implementation, it’s full if rear == MAX - 1.

Algorithm:

if REAR == MAX_SIZE - 1 then
    return 1
else
    return 0
end if

6. Display (Access all Elements)

It first checks if the queue is empty by checking the FRONT and REAR pointers.

If not empty, it loops from FRONT to REAR and prints all the elements one by one.

Algorithm:

if FRONT == -1 or FRONT > REAR then
   Output "Queue is empty."
   Exit
end if
for i ← FRONT to REAR do
   Output Q[i]
end for

Linear Queue Implementation in C Programming

#include <stdio.h>
#define MAX_SIZE 100

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

// Check if the queue is full
int isFull() {
    return rear == MAX_SIZE - 1;
}

// Check if the queue is empty
int isEmpty() {
    return front == -1 || front > rear;
}

// Enqueue operation
void enqueue(int item) {
    if (isFull()) {
        printf("Queue Overflow - Cannot insert %d\n", item);
        return;
    }
    if (front == -1)
        front = 0;
    rear++;
    queue[rear] = item;
    printf("Inserted %d into the queue.\n", item);
}

// Dequeue operation
void dequeue() {
    if (isEmpty()) {
        printf("Queue Underflow - No element to remove.\n");
        return;
    }
    printf("Deleted %d from the queue.\n", queue[front]);
    front++;
    if (front > rear) {
        front = -1;
        rear = -1;
    }
}

// Peek operation
void peek() {
    if (isEmpty()) {
        printf("Queue is Empty - No front element.\n");
        return;
    }
    printf("Front element is: %d\n", queue[front]);
}

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

// Main function to demonstrate operations step-by-step
int main() {
    // Enqueue some elements
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();

    // Peek at front
    peek();

    // Dequeue elements
    dequeue();
    display();

    dequeue();
    dequeue();
    dequeue();  // Attempt to dequeue from empty queue

    display();
    return 0;
}

Output:

Inserted 10 into the queue.
Inserted 20 into the queue.
Inserted 30 into the queue.
Queue elements: 10 20 30
Front element is: 10
Deleted 10 from the queue.
Queue elements: 20 30
Deleted 20 from the queue.
Deleted 30 from the queue.
Queue Underflow - No element to remove.
Queue is empty.