What is a Queue? The FIFO Principle

Imagine a waiting line at a ticket counter or a queue of cars at a drive-thru. The person who arrives first is the first one to be served. This "First-In, First-Out" (FIFO) principle is exactly how a queue data structure operates.

• First-In, First-Out (FIFO): The element that was added first will be the first one to be removed.
• Real-world applications: Task scheduling in operating systems, printer queues, handling website requests, breadth-first search (BFS) algorithms, and more.

Key Queue Operations

A queue typically supports the following core operations:

• enqueue: Adds an element to the rear (or back) of the queue.
• dequeue: Removes and returns the element from the front (or head) of the queue.
• peek (or front): Returns the element at the front of the queue without removing it.
• isEmpty: Checks if the queue contains any elements.
• isFull: Checks if the queue has reached its maximum capacity (relevant for array-based implementations).

Choosing an Implementation: Arrays vs. Linked Lists

Queues can be implemented using either arrays or linked lists. Both have their pros and cons:

• Array-Based Queue:
  • Pros: Simple to implement for fixed-size queues, good cache locality, no overhead for pointers per element.
  • Cons: Fixed size (potential for overflow if capacity is exceeded), can lead to inefficient space utilization if not implemented as a circular queue.
• Linked List-Based Queue:
  • Pros: Dynamic size (grows and shrinks as needed), no need to worry about fixed capacity.
  • Cons: More memory overhead per element due to pointers, slightly more complex implementation with node management.

For this tutorial, we will focus on implementing a circular array-based queue, which efficiently utilizes the array space and overcomes the basic array queue's limitations of linear shifting or wasted space.

Understanding the Circular Array Queue

In a simple array-based queue, when elements are dequeued, space is freed at the front, but new elements can only be added at the rear. This can lead to the queue becoming "full" even if there's available space at the beginning of the array. A circular queue solves this by allowing the rear to "wrap around" to the beginning of the array when it reaches the end.

We use two pointers (indices):

• front: Points to the first element in the queue.
• rear: Points to the last element in the queue.

The key to circular behavior is the modulo operator (%). When incrementing front or rear, we use (index + 1) % MAX_SIZE to make it wrap around to 0 if it exceeds MAX_SIZE - 1.

Initial State:

When the queue is empty, we typically set front = -1 and rear = -1.

isEmpty Condition:

The queue is empty if front == -1.

isFull Condition:

The queue is full if (rear + 1) % MAX_SIZE == front. This condition implies that if we add one more element, rear would point to where front is, indicating no more space (we need at least one empty slot to differentiate between full and empty).

enqueue Logic:

1. Check if the queue is full. If so, report an error.
2. If empty (front == -1), set front = 0.
3. Increment rear circularly: rear = (rear + 1) % MAX_SIZE.
4. Add the element at queue_array[rear].

dequeue Logic:

1. Check if the queue is empty. If so, report an error.
2. Get the element at queue_array[front].
3. If front == rear (only one element was in the queue), reset to empty state: front = -1, rear = -1.
4. Otherwise, increment front circularly: front = (front + 1) % MAX_SIZE.
5. Return the retrieved element.

C Code Implementation: Circular Queue

Let's put these concepts into practice with a complete C implementation.

#include <stdio.h>
#include <stdlib.h> // For EXIT_SUCCESS

// Define the maximum size of the queue
#define MAX_SIZE 5

// Global array to store queue elements
int queue_array[MAX_SIZE];
// Pointers for front and rear of the queue
int front = -1;
int rear = -1;

/**
 * @brief Checks if the queue is empty.
 * @return 1 if the queue is empty, 0 otherwise.
 */
int isEmpty() {
    return (front == -1);
}

/**
 * @brief Checks if the queue is full.
 * @return 1 if the queue is full, 0 otherwise.
 */
int isFull() {
    return ((rear + 1) % MAX_SIZE == front);
}

/**
 * @brief Adds an element to the rear of the queue.
 * @param item The element to be added.
 */
void enqueue(int item) {
    if (isFull()) {
        printf("Queue Overflow! Cannot enqueue %d.\n", item);
        return;
    }
    if (isEmpty()) {
        front = 0; // Initialize front when the first element is added
    }
    rear = (rear + 1) % MAX_SIZE; // Move rear circularly
    queue_array[rear] = item;
    printf("Enqueued: %d\n", item);
}

/**
 * @brief Removes and returns the element from the front of the queue.
 * @return The element removed from the front of the queue.
 *         Returns -1 if the queue is empty (or another suitable error indicator).
 */
int dequeue() {
    if (isEmpty()) {
        printf("Queue Underflow! Cannot dequeue.\n");
        return -1; // Indicate error
    }
    int dequeued_item = queue_array[front];
    if (front == rear) {
        // Only one element in the queue, reset to empty state
        front = -1;
        rear = -1;
    } else {
        front = (front + 1) % MAX_SIZE; // Move front circularly
    }
    printf("Dequeued: %d\n", dequeued_item);
    return dequeued_item;
}

/**
 * @brief Returns the element at the front of the queue without removing it.
 * @return The element at the front of the queue.
 *         Returns -1 if the queue is empty.
 */
int peek() {
    if (isEmpty()) {
        printf("Queue is empty! Cannot peek.\n");
        return -1; // Indicate error
    }
    printf("Front element: %d\n", queue_array[front]);
    return queue_array[front];
}

/**
 * @brief Displays all elements in the queue.
 */
void display() {
    if (isEmpty()) {
        printf("Queue is empty.\n");
        return;
    }
    printf("Queue elements: ");
    int i = front;
    while (1) {
        printf("%d ", queue_array[i]);
        if (i == rear)
            break;
        i = (i + 1) % MAX_SIZE;
    }
    printf("\n");
}

int main() {
    printf("--- Queue Operations Demonstration ---\n");

    display(); // Queue is empty

    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();

    peek();

    dequeue(); // Dequeue 10
    display();

    enqueue(40);
    enqueue(50); // Queue is full now (10, 20, 30, 40, 50 in logical order)
    display();

    enqueue(60); // Attempt to enqueue when full
    display();

    dequeue(); // Dequeue 20
    dequeue(); // Dequeue 30
    display();

    enqueue(60); // Enqueue 60 (replaces the old 20 slot)
    enqueue(70); // Enqueue 70 (replaces the old 30 slot)
    display();

    dequeue(); // Dequeue 40
    dequeue(); // Dequeue 50
    dequeue(); // Dequeue 60
    dequeue(); // Dequeue 70
    display();

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

    return EXIT_SUCCESS;
}

Explanation of the Code:

• Global Variables: We use global variables queue_array, front, and rear for simplicity. In a more complex application, these would typically be encapsulated within a struct.
• MAX_SIZE: Defines the capacity of our queue. Remember, for a circular array of size `N`, we can effectively store `N-1` elements if we use the `(rear + 1) % MAX_SIZE == front` condition for `isFull`. This leaves one slot intentionally unused to distinguish a full queue from an empty one when `front` and `rear` are equal. Alternatively, you could use a `count` variable.
• enqueue Logic: It handles the initial `front = 0` assignment when the queue goes from empty to having one element. It then updates `rear` circularly and adds the element.
• dequeue Logic: It retrieves the item at `front`. If it's the last element, `front` and `rear` are reset to `-1`. Otherwise, `front` is updated circularly.
• peek: A straightforward function that just returns the element at `front` without modifying the queue.
• display: This utility function iterates from `front` to `rear` circularly to show the current elements in the queue, which is very helpful for debugging and understanding queue behavior.
• main Function: Demonstrates various queue operations, including enqueueing, dequeuing, peeking, and handling overflow/underflow scenarios.

Advantages and Limitations of this Implementation

Advantages:

• Efficient Space Usage: The circular nature ensures that the entire array space is utilized, unlike a simple linear array queue that might "fill up" prematurely due to `front` advancing.
• Constant Time Operations: enqueue, dequeue, isEmpty, isFull, and peek all execute in O(1) time complexity, meaning their performance doesn't degrade as the number of elements grows.
• Simplicity: Relatively easy to understand and implement compared to dynamic data structures.

Limitations:

• Fixed Size: The primary limitation is its fixed capacity. If you need a queue that can grow or shrink indefinitely, a linked list implementation would be more appropriate.
• Type Restriction: This implementation is for `int` data type. For other types, you would need to modify the array type or use `void` pointers and typecasting, or a generic approach in C.

Conclusion

You've now successfully implemented a circular queue using arrays in C! Understanding how queues work and how to build them from scratch is a fundamental skill in programming. The circular array implementation provides an efficient way to manage a fixed-size queue, making good use of memory and offering constant-time operations.

While this implementation is robust for many scenarios, remember that for dynamic sizing requirements, a linked-list based queue would be the next logical step to explore. Continue practicing these fundamental data structures to build a strong foundation in C programming.