C Programming Data Structures Queue And Circular Queue Complete Guide

Data Structures: Queue and Circular Queue in C Programming

Queue: A linear data structure (DS) that follows the First In, First Out (FIFO) principle. This implies that elements are added at one end, known as the back or rear, and removed from the other end, known as the front.

Circular Queue: An advanced version of a queue where the last position is connected back to the first position to form a circle. This data structure overcomes the limitation of regular queues by utilizing space more efficiently.

Structure of a Queue

• Front: Points to the element that will be dequeued first.
• Rear: Points to the element that was recently enqueued.
• Enqueue Operation: Adding an element to the rear.
• Dequeue Operation: Removing an element from the front.

Basic Operations in a Queue

1. Initialize Queue: Set front and rear to -1.
2. Enqueue: Check if the queue is full (if (rear + 1) % SIZE == front). If not, increment rear and insert the element.
3. Dequeue: Check if the queue is empty (if front == -1). If not, increment front and remove the element.
4. Peek: Retrieve the value at the front of the queue without removing it.
5. IsEmpty: Check if the queue has no elements.
6. IsFull: Check if the queue cannot accept any more elements.

Queue Implementation in C Using an array, a queue can be implemented as follows:

#include <stdio.h>
#define SIZE 10

void initialize(int* front, int* rear) {
    *front = *rear = -1;
}

int isFull(int rear) {
    return (rear + 1) % SIZE == front;
}

int isEmpty(int front) {
    return front == -1;
}

void enqueue(int queue[], int* rear, int* front, int item) {
    if(isFull(*rear)) {
        printf("Queue Overflow\n");
        return;
    }
    if(isEmpty(*front))
        *front = 0;
    *rear = (*rear + 1) % SIZE;
    queue[*rear] = item;
}

int dequeue(int queue[], int* front, int* rear) {
    int item;
    if(isEmpty(*front)) {
        printf("Queue Underflow\n");
        return -1;
    }
    item = queue[*front];
    if(*front == *rear)
        *front = *rear = -1; // Reset queue to initial state
    else
        *front = (*front + 1) % SIZE;
    return item;
}

void peek(int queue[], int front) {
    if(isEmpty(front)) {
        printf("Queue Empty\n");
    } else {
        printf("%d\n", queue[front]);
    }
}

Advantages

• Simple and efficient.
• Used in scenarios like breadth-first search.
• Ideal for operations requiring ordering of elements.

Disadvantages

• Fixed size due to array implementation.
• Waste of space when deque operations occur frequently.
• Dequeue operation requires shifting elements.

Structure of a Circular Queue

A circular queue avoids the issue of wasted space by forming a logical loop between the rear and front of the queue. This makes the use of space more efficient and prevents the requirement of shifting elements during deque operations.

Basic Operations in a Circular Queue Circular Queue operations include all standard queue operations with additional circular behavior rules:

1. Initialize Circular Queue: Similar to Queue initialization.
2. Enqueue: Add an element at rear, incrementing rear in a circular manner.
3. Dequeue: Remove an element from front, and increment front circularly.
4. Peek: Similar to Queue peek.
5. IsEmpty: Similar to Queue isEmpty.
6. IsFull: Checks (rear + 1) % SIZE == front.

Circular Queue in C Using an array to create a circular queue:

#include <stdio.h>
#define SIZE 10

struct CircularQueue {
    int items[SIZE];
    int front;
    int rear;
};

int isFull(struct CircularQueue* cq) {
    return ((cq->rear + 1) % SIZE == cq->front);
}

int isEmpty(struct CircularQueue* cq) {
    return (cq->front == -1);
}

void enqueue(struct CircularQueue* cq, int item) {
    if(isFull(cq)) {
        printf("Queue Overflow\n");
        return;
    }
    if(cq->front == -1)
        cq->front = 0;
    cq->rear = (cq->rear + 1) % SIZE;
    cq->items[cq->rear] = item;
    printf("Inserted -> %d\n", item);
}

int dequeue(struct CircularQueue* cq) {
    int item;
    if(isEmpty(cq)) {
        printf("Queue Underflow\n");
        return -1;
    }
    item = cq->items[cq->front];
    if(cq->front == cq->rear) { // Last remaining element
        cq->front = cq->rear = -1;
    } else {
        cq->front = (cq->front + 1) % SIZE;
    }
    printf("Deleted -> %d\n", item);
    return item;
}

void peek(struct CircularQueue* cq) {
    if(isEmpty(cq)) {
        printf("Queue Empty\n");
    } else {
        printf("\nFront item: %d\n", cq->items[cq->front]);
    }
}

int main() {
    struct CircularQueue cq;
    cq.front = cq.rear = -1;

    enqueue(&cq, 1);
    enqueue(&cq, 2);
    enqueue(&cq, 3);

    peek(&cq);

    dequeue(&cq);
    dequeue(&cq);
    dequeue(&cq);

    enqueue(&cq, 10);

    peek(&cq);
    return 0;
}

Advantages

• Efficient space usage.
• No need to shift elements during the dequeue process.
• Operations are constant time, O(1).

Disadvantages

• Complex compared to simple queue implementations using arrays or linked lists.
• Fixed size.
• Requires careful handling of indices to avoid overflow/underflow conditions.

Comparison

• Queue: Linear and simpler, but may waste space as front moves up after dequeuing.
• Circular Queue: Logical looping around the queue, saves space but is more complex.

Applications

Both queues and circular queues find applications in various fields such as:

• Operating Systems: For managing queues of processes.
• Networks: In scheduling packets for transmission.
• Computer Hardware: Buffer management systems often use them.
• Real-time Systems: To handle events by their arrival order.

In conclusion, while queues provide the fundamental FIFO behavior, circular queues offer enhanced memory usage capabilities essential for many dynamic applications.