Queue in C

Working of Queue Data Structure

A queue is a linear data structure that follows the First In, First Out (FIFO) principle, meaning the element that is added first is removed first. Key operations for a queue include:

• Enqueue: Adds an element to the end of the queue.
   
• Dequeue: Removes the element from the front of the queue.
   
• Peek/Front: Returns the element at the front without removing it.
   
• IsEmpty: Checks if the queue is empty.

Representation of Queue in C

In C, a queue can be represented using arrays or linked lists. Here’s a basic example of how to represent a queue using an array:

Array Representation

Explanation:

• Initialization: The initializeQueue function sets both front and rear to -1.
   
• Enqueue: Adds an item to the rear of the queue, provided it is not full.
   
• Dequeue: Removes an item from the front of the queue, provided it is not empty.
   
• Display: Shows all items from the front to the rear of the queue.

Implementation of a Queue in C

The implementation of a queue can vary based on the requirements. For simplicity, arrays are commonly used, but linked lists are also utilized for dynamic size needs.

Array Implementation

Here's a brief overview of how you might implement a queue using an array.

• C

C

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

#define MAX 100 // Maximum number of elements in the queue

// Queue structure
typedef struct {
    int front, rear, size;
    int array[MAX];
} Queue;

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

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

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

// Function to add an element to the queue
void enqueue(Queue *q, int item) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX;
    q->array[q->rear] = item;
    q->size++;
}

// Function to remove an element from the queue
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int item = q->array[q->front];
    q->front = (q->front + 1) % MAX;
    q->size--;
    return item;
}

// Function to display the queue
void displayQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    int i;
    for (i = 0; i < q->size; i++) {
        printf("%d ", q->array[(q->front + i) % MAX]);
    }
    printf("\n");
}

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

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("Queue after enqueuing 10, 20, 30: ");
    displayQueue(&q);

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

    printf("Queue after dequeuing an element: ");
    displayQueue(&q);

    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Queue after enqueuing 10, 20, 30: 10 20 30 
Dequeued: 10
Queue after dequeuing an element: 20 30 

• Time Complexity: O(1) for both enqueue and dequeue operations due to simple index manipulations.
   
• Space Complexity: O(n), where n is the maximum number of elements in the queue.

Linked List Implementation

Here's a brief overview of how you might implement a queue using a linked list:

• C

C

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

// Node structure
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// Queue structure
typedef struct {
    Node *front, *rear;
} Queue;

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

// Function to add an element to the queue
void enqueue(Queue *q, int item) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = item;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
        return;
    }
    q->rear->next = newNode;
    q->rear = newNode;
}

// Function to remove an element from the queue
int dequeue(Queue *q) {
    if (q->front == NULL) {
        printf("Queue is empty\n");
        return -1;
    }
    Node *temp = q->front;
    int item = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return item;
}

// Function to display the queue
void displayQueue(Queue *q) {
    Node *temp = q->front;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

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

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("Queue after enqueuing 10, 20, 30: ");
    displayQueue(&q);

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

    printf("Queue after dequeuing an element: ");
    displayQueue(&q);

    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Queue after enqueuing 10, 20, 30: 10 20 30 
Dequeued: 10
Queue after dequeuing an element: 20 30 

Explanation

• Initialization: initializeQueue sets front and rear to NULL.
   
• Enqueue: Adds a new node to the rear.
   
• Dequeue: Removes the node from the front.

Implementation of Queue Using Stacks

A queue can be implemented using two stacks. The basic approach involves:

• Enqueue Operation: Push the new element onto stack 1.
   
• Dequeue Operation: If stack 2 is empty, transfer all elements from stack 1 to stack 2 to reverse their order, then pop the top element from stack 2.
   

This method ensures that enqueue operations are O(1), while dequeue operations can be O(n) in the worst case, but amortized to O(1) over multiple operations.

Types of Queues

There are various types of queues, each suited for different applications:

• Simple Queue: Follows the basic FIFO model.
   
• Circular Queue: Reuses memory by wrapping around when it reaches the end of the queue.
   
• Priority Queue: Processes elements based on priority instead of the order they were added.
   
• Double-Ended Queue (Deque): Allows insertion and removal of elements from both ends.
   
• Blocking Queue: Used in concurrent programming, where operations wait until conditions like empty or full are met.
   

Each type of queue serves unique purposes depending on the system or application requirements.

Basic Operations of Queue in C

Here's a table summarizing the queue operations, their description, time complexity, and space complexity:

Advantages

• Order Preservation: Maintains the order of elements.
   
• Simple Implementation: Easy to implement using arrays or linked lists.
   
• Efficient Operations: Enqueue and dequeue operations are efficient and straightforward.

Disadvantages

• Fixed Size (Array): In array implementation, the size is fixed, which can be limiting.
   
• Memory Usage (Linked List): Linked list implementation uses extra memory for pointers.

Applications of Queue Data Structure

Queues are widely used in real-world applications, including:

• Task Scheduling: Operating systems manage tasks and schedule them using queues.
   
• Handling Requests: Servers process incoming tasks in order using queues.
   
• Data Buffering: Queues are used in data buffering for smooth playback in streaming services.
   
• Breadth-First Search (BFS): Graph algorithms use queues to explore nodes in BFS.
   
• Print Queue Management: Printers manage print jobs using queues, processing them in the order they arrive.

Real-Time Applications of Queue

Queues are essential in real-world applications where data follows the First In, First Out (FIFO) principle. They help manage tasks efficiently in various domains, ensuring smooth processing and resource allocation.

• Operating Systems (Task Scheduling): Used in CPU and disk scheduling to manage multiple processes.
• Print Spooling: Ensures print jobs are processed in the order they are received.
• Call Centers: Manages customer service calls, ensuring fair and efficient handling.
• Network Data Transmission: Used in routers and switches to manage packet flow and prevent congestion.
• Messaging Queues: Supports asynchronous communication in distributed systems and microservices.
• Job Scheduling in Cloud Computing: Manages user requests and resource allocation efficiently.
• Traffic Management Systems: Regulates traffic flow at toll booths and signalized intersections.
• E-commerce Order Processing: Manages online orders and processes them sequentially.
• Ticketing Systems: Ensures first-come, first-served processing for movie, train, or event bookings.
• Breadth-First Search (BFS) in Graphs: Helps in exploring nodes layer by layer in shortest path algorithms.

Frequently Asked Questions

What is the difference between a queue and a stack?

 A queue uses FIFO (First-In-First-Out) order, while a stack uses LIFO (Last-In-First-Out) order.

How can we avoid the issue of queue overflow in an array-based implementation? 

By using dynamic arrays or circular queues to manage space efficiently.

Can a queue be implemented using a stack?

Yes, a queue can be implemented using two stacks by reversing the order of operations.

Is queue a LIFO or FIFO?

A Queue follows the FIFO (First In, First Out) principle, whereas a Stack follows LIFO (Last In, First Out).

Conclusion

In this article, we explored the concept of queues in C, covering their characteristics, implementation, and key operations. Understanding the concept of queues is essential for managing data efficiently in various applications. Mastering their implementation not only enhances your programming skills but also prepares you for both academic and professional challenges.