Queue in C: Theory, Code Examples, and Real-World Applications

A queue is a linear data structure that follows the FIFO (First In, First Out) principle, meaning that the first element added to the queue will be the first one to be removed. This is analogous to a line at a checkout counter where the first person to stand in line is the first to be served. Queues are widely used in various applications, including managing requests in servers, scheduling tasks in operating systems, and handling asynchronous data processing. In C, a queue can be implemented using an array or a linked list. In this article, we’ll explore how to implement and use a queue in C, its basic operations, and provide some examples.

Basic Operations of a Queue

A queue supports the following basic operations:

1. enqueue() – Adds an element to the end of the queue.
2. dequeue() – Removes the element from the front of the queue.
3. peek() – Returns the element at the front of the queue without removing it.
4. isEmpty() – Checks whether the queue is empty.
5. isFull() – Checks whether the queue is full (if implementing with an array).

Implementing a Queue Using an Array

Here’s how you can implement a simple queue in C using an array:

#include <stdio.h>
#include <stdlib.h>

#define MAX 5  // Maximum size of the queue

// Queue structure
struct Queue {
    int items[MAX];
    int front;
    int rear;
};

// Function to initialize the queue
void initializeQueue(struct Queue *q) {
    q->front = -1;
    q->rear = -1;
}

// Function to check if the queue is full
int isFull(struct Queue *q) {
    return q->rear == MAX - 1;
}

// Function to check if the queue is empty
int isEmpty(struct Queue *q) {
    return q->front == -1;
}

// Function to add an element to the queue
void enqueue(struct Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    if (q->front == -1) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = value;
    printf("Enqueued %d\n", value);
}

// Function to remove an element from the queue
int dequeue(struct Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int dequeuedValue = q->items[q->front];
    if (q->front == q->rear) { // If only one element is in the queue
        q->front = q->rear = -1;
    } else {
        q->front++;
    }
    return dequeuedValue;
}

// Function to return the front element of the queue without removing it
int peek(struct Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    return q->items[q->front];
}

// Function to display the queue elements
void display(struct Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue elements: ");
    for (int i = q->front; i <= q->rear; i++) {
        printf("%d ", q->items[i]);
    }
    printf("\n");
}

int main() {
    struct Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);
    enqueue(&q, 50);
    display(&q);

    printf("Dequeued: %d\n", dequeue(&q));
    display(&q);

    printf("Front element is: %d\n", peek(&q));

    enqueue(&q, 60);
    display(&q);

    return 0;
}

Explanation of the Code

• Queue structure: The queue is represented by a structure Queue that contains an array items[] to store the elements and two integers front and rear to track the front and rear of the queue.
• Initialization: The queue is initialized with front and rear set to -1, indicating that the queue is empty.
• enqueue(): Adds an element at the rear of the queue. If the queue is full, it displays a message.
• dequeue(): Removes the element from the front of the queue. If the queue is empty, it returns -1.
• peek(): Returns the element at the front without removing it.
• isFull() and isEmpty(): These functions check whether the queue is full or empty.
• display(): This function displays all the elements in the queue.

Time Complexity of Queue Operations

• enqueue(): O(1) – Insertion of an element takes constant time.
• dequeue(): O(1) – Removal of an element takes constant time.
• peek(): O(1) – Retrieving the front element takes constant time.
• isFull() and isEmpty(): O(1) – Checking whether the queue is full or empty also takes constant time.

Applications of Queue in C

Queues have many real-world applications:

1. CPU Scheduling: Operating systems use queues to schedule tasks in a way that processes are executed in the order they arrive.
2. Data Buffering: Queues are used to manage data that arrives in a stream, such as network packets.
3. Order Processing: For instance, in e-commerce websites, order requests can be processed in a queue, ensuring that orders are handled in the order they are received.
4. Breadth-First Search (BFS): In graph traversal algorithms, a queue is used to explore nodes level by level.

FAQs

1. What is the difference between a queue and a stack?

• A queue follows the FIFO principle (First In, First Out), while a stack follows the LIFO principle (Last In, First Out). In a stack, the last element added is the first one to be removed, whereas in a queue, the first element added is the first to be removed.

2. What happens when we try to dequeue from an empty queue?

• If you try to dequeue from an empty queue, the dequeue() function will return -1 and display an error message (“Queue is empty”).

3. How do I make a queue dynamic?

• You can implement a dynamic queue using a linked list, where the size of the queue grows and shrinks as needed without the need for a fixed array size.

4. What is the time complexity of the queue operations?

• All basic operations in a queue (enqueue, dequeue, peek, isFull, and isEmpty) have a time complexity of O(1), which means they execute in constant time.

5. Can I implement a circular queue in C?

• Yes, a circular queue is a variation of a queue that connects the last position of the array to the first, allowing for more efficient use of the array space. The implementation would require handling both the front and rear pointers in a circular manner.

With this guide, you should now have a solid understanding of queues in C, their basic operations, and how to implement them effectively. Queues are versatile data structures that are crucial in many real-world applications, and understanding them is a key skill for any C programmer.