Linear Data Structures-Queues

Introduction of Queues

A queue is a fundamental data structure in computer science that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Queues are used in a variety of applications, such as managing tasks in a printer spooler, handling requests in web servers, and simulating real-world queues like lines at a supermarket.

Characteristics of a Queue

1. FIFO Structure: The main characteristic of a queue is its FIFO nature, where the oldest element is processed first.
2. Enqueue Operation: This is the process of adding an element to the back (or tail) of the queue.
3. Dequeue Operation: This is the process of removing an element from the front (or head) of the queue.
4. Front and Rear:
   • Front: The end of the queue from where elements are removed.
   • Rear: The end of the queue where elements are added.
5. Size: Queues have a defined size, which can be fixed (static queue) or dynamic (dynamic queue).

Basic Operations

1. Enqueue: Add an element to the end of the queue.
   • If the queue is full, enqueue operations will not be possible (in a bounded queue).
2. Dequeue: Remove an element from the front of the queue.
   • If the queue is empty, dequeue operations will not be possible.
3. Peek/Front: Retrieve the front element of the queue without removing it.
4. isEmpty: Check if the queue is empty.
5. isFull: Check if the queue is full (only applicable to bounded queues).

Types of Queues

1. Simple Queue (Linear Queue):
   • Basic form of a queue with limited space.
   • As elements are dequeued, the available space cannot be reused unless the queue is reset.
2. Circular Queue:
   • The last position of the queue is connected back to the first position to make a circle.
   • This allows reusing the empty spaces created by dequeuing elements, making efficient use of storage.
3. Priority Queue:
   • Each element is assigned a priority, and the element with the highest priority is dequeued before others.
   • Priority queues can be implemented using heaps or other data structures.
4. Double-Ended Queue (Deque):
   • Allows insertion and deletion of elements from both ends (front and rear).
   • More flexible but more complex than a simple queue.

Applications of Queues

1. Task Scheduling:
   • Operating systems use queues for managing tasks and processes.
2. Print Queue:
   • Printers use queues to manage print jobs, printing documents in the order they are received.
3. Breadth-First Search (BFS):
   • Used in graph traversal algorithms, where a queue helps in exploring nodes level by level.
4. Call Center Systems:
   • Calls are queued based on the order of arrival to ensure they are handled in sequence.
5. Data Streaming:
   • Buffers use queues to manage data packets being sent or received.

Insertion ,Deletion ,and Display Operations on Queues

Queue Operations

1. Insertion (Enqueue) Operation

The enqueue operation adds an element to the rear of the queue.

How It Works

• Check if the queue is full:
  • In a circular queue, the queue is full when the next position of the rear is the front position.
• Add the element:
  • Place the element at the position pointed to by the rear.
• Update the rear pointer:
  • Move the rear pointer to the next position in a circular fashion.
• Handle the first element case:
  • If the queue was initially empty, set the front pointer to the first position.

Algorithm

void enqueue(Queue* q, int item) {
    if ((q->rear + 1) % MAX_SIZE == q->front) {
        printf("Queue is full. Cannot enqueue %d.\n", item);
        return;
    }
    
    // If queue is initially empty
    if (q->front == -1) {
        q->front = 0;
    }

    // Insert the element at the rear
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->items[q->rear] = item;
}

Step-by-Step Explanation

1. Check Full Condition: The queue is full when (rear + 1) % MAX_SIZE == front.
2. Add Element: If not full, place the new element at rear.
3. Update Rear: Use circular increment (rear + 1) % MAX_SIZE.
4. Update Front: If inserting the first element, set front to 0.

2. Deletion (Dequeue) Operation

The dequeue operation removes an element from the front of the queue.

How It Works

• Check if the queue is empty:
  • The queue is empty if the front pointer is -1.
• Remove the element:
  • Access the element at the front and update the front pointer.
• Handle the queue becoming empty:
  • If the element removed was the last one, reset front and rear to -1.

Algorithm

int dequeue(Queue* q) {
    if (q->front == -1) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1;  // Indicate queue is empty
    }

    int item = q->items[q->front];

    // Check if the queue will be empty after this dequeue
    if (q->front == q->rear) {
        q->front = -1;
        q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX_SIZE;
    }

    return item;
}

Step-by-Step Explanation

1. Check Empty Condition: If front == -1, the queue is empty.
2. Remove Element: Access and remove the element at front.
3. Update Front: Use circular increment (front + 1) % MAX_SIZE.
4. Reset Pointers: If the queue is empty after dequeue, set front and rear to -1.

3. Display Operation

The display operation shows all elements from the front to the rear of the queue.

How It Works

• Check if the queue is empty:
  • If front is -1, the queue is empty.
• Iterate from front to rear:
  • Use a loop to traverse and print elements, considering wrap-around in a circular queue.

Algorithm

void display(Queue* q) {
    if (q->front == -1) {
        printf("Queue is empty.\n");
        return;
    }

    int i = q->front;
    printf("Queue elements: ");
    while (true) {
        printf("%d ", q->items[i]);

        if (i == q->rear) {
            break;
        }
        i = (i + 1) % MAX_SIZE;
    }
    printf("\n");
}

Step-by-Step Explanation

1. Check Empty Condition: If front == -1, print “Queue is empty”.
2. Iterate and Display: Loop from front to rear using circular increment.
3. Handle Wrap-Around: Continue the loop to the beginning if needed using (i + 1) % MAX_SIZE.

Program for Array Implementation of a Queue and its Operations

#include <stdio.h>
#include <stdbool.h>

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

typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
} Queue;

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

// Function to check if the queue is full
bool isFull(Queue* q) {
    return ((q->rear + 1) % MAX_SIZE == q->front);
}

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

// Function to add an element to the queue (Enqueue)
void enqueue(Queue* q, int item) {
    if (isFull(q)) {
        printf("Queue is full. Cannot enqueue %d.\n", item);
        return;
    }

    // If the queue is initially empty, update the front pointer
    if (isEmpty(q)) {
        q->front = 0;
    }

    // Insert the element at the rear position
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->items[q->rear] = item;
    printf("Enqueued: %d\n", item);
}

// Function to remove an element from the queue (Dequeue)
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1;  // Indicate queue is empty
    }

    int item = q->items[q->front];
    printf("Dequeued: %d\n", item);

    // Check if the queue will be empty after this dequeue
    if (q->front == q->rear) {
        // If the queue becomes empty, reset the pointers
        q->front = -1;
        q->rear = -1;
    } else {
        // Move the front pointer to the next position
        q->front = (q->front + 1) % MAX_SIZE;
    }

    return item;
}

// Function to display the elements of the queue
void display(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return;
    }

    int i = q->front;
    printf("Queue elements: ");
    while (true) {
        printf("%d ", q->items[i]);

        if (i == q->rear) {
            break;
        }
        i = (i + 1) % MAX_SIZE;
    }
    printf("\n");
}

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

    // Example usage of the queue
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    display(&q);

    dequeue(&q);
    display(&q);

    enqueue(&q, 40);
    enqueue(&q, 50);
    enqueue(&q, 60);  // Attempt to enqueue when the queue is full
    display(&q);

    dequeue(&q);
    dequeue(&q);
    dequeue(&q);
    dequeue(&q);  // Attempt to dequeue when the queue is empty
    display(&q);

    return 0;
}

#define MAX_SIZE 5

typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
} Queue;

void initializeQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

bool isFull(Queue* q) {
    return ((q->rear + 1) % MAX_SIZE == q->front);
}

bool isEmpty(Queue* q) {
    return (q->front == -1);
}

void enqueue(Queue* q, int item) {
    if (isFull(q)) {
        printf("Queue is full. Cannot enqueue %d.\n", item);
        return;
    }

    if (isEmpty(q)) {
        q->front = 0;
    }

    q->rear = (q->rear + 1) % MAX_SIZE;
    q->items[q->rear] = item;
    printf("Enqueued: %d\n", item);
}

int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1;
    }

    int item = q->items[q->front];
    printf("Dequeued: %d\n", item);

    if (q->front == q->rear) {
        q->front = -1;
        q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX_SIZE;
    }

    return item;
}

display(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return;
    }

    int i = q->front;
    printf("Queue elements: ");
    while (true) {
        printf("%d ", q->items[i]);

        if (i == q->rear) {
            break;
        }
        i = (i + 1) % MAX_SIZE;
    }
    printf("\n");
}

Linked List Implementation of Queue and it’s Operations

 There are two basic operations which can be implemented on the linked queues. The operations are Insertion and Deletion. The insert operation append the queue by adding an element to the end of the queue. The new element will be the last element of the queue.

Algorithm

1. Define Node Structure:
   • Create a node structure with an integer data field and a pointer to the next node.
2. Define Queue Structure:
   • Create a queue structure with pointers to the front and rear nodes.
3. Initialize Queue:
   • Initialize the queue by setting both the front and rear pointers to NULL.
4. Enqueue Operation:
   • Create a new node with the given data.
   • If the queue is empty, set both the front and rear pointers to the new node.
   • Otherwise, add the new node at the end of the queue and update the rear pointer.
5. Dequeue Operation:
   • If the queue is empty, print an error message.
   • Otherwise, remove the node at the front of the queue and return its data. Update the front pointer.
   • If the queue becomes empty after dequeuing, set the rear pointer to NULL.
6. Peek Operation:
   • Return the data at the front of the queue without removing it.
7. Check if Queue is Empty:
   • Return true if the front pointer is NULL, otherwise return false.

Advantages of Using a Linked List for Queue

• Dynamic Size: The queue can grow and shrink as needed without a predefined size limit.
• Efficient Memory Use: No need to allocate a fixed amount of memory as in an array-based implementation.

Disadvantages

• Memory Overhead: Each node requires additional memory for the pointer to the next node.
• Complex Implementation: More complex than array-based implementations due to the need to manage pointers.

Program for Linked List Implementation of a Queue and it’s operations

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

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

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

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to initialize the queue
struct Queue* createQueue() {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    if (!queue) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

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

// Function to add an element to the queue (enqueue)
void enqueue(struct Queue* queue, int data) {
    struct Node* newNode = createNode(data);
    if (queue->rear == NULL) {
        // If queue is empty, front and rear are the same
        queue->front = queue->rear = newNode;
        return;
    }
    // Add the new node at the end of the queue and change rear
    queue->rear->next = newNode;
    queue->rear = newNode;
    printf("Enqueued: %d\n", data);
}

// Function to remove an element from the queue (dequeue)
int dequeue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1; // Returning -1 to indicate an empty queue
    }
    struct Node* temp = queue->front;
    int data = temp->data;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        // If the queue is empty, update rear to NULL
        queue->rear = NULL;
    }
    free(temp);
    printf("Dequeued: %d\n", data);
    return data;
}

// Function to get the front element of the queue
int peek(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty.\n");
        return -1; // Returning -1 to indicate an empty queue
    }
    return queue->front->data;
}

// Function to print the queue
void printQueue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty.\n");
        return;
    }
    struct Node* temp = queue->front;
    printf("Queue: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// Main function to demonstrate queue operations
int main() {
    struct Queue* queue = createQueue();

    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);

    printQueue(queue);

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

    dequeue(queue);
    dequeue(queue);

    printQueue(queue);

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

    return 0;
}

cCopy codestruct Node {
    int data;
    struct Node* next;
};

cCopy codestruct Queue {
    struct Node* front;
    struct Node* rear;
};

cCopy codestruct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

cCopy codestruct Queue* createQueue() {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    if (!queue) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

cCopy codebool isEmpty(struct Queue* queue) {
    return queue->front == NULL;
}

cCopy codevoid enqueue(struct Queue* queue, int data) {
    struct Node* newNode = createNode(data);
    if (queue->rear == NULL) {
        // If queue is empty, front and rear are the same
        queue->front = queue->rear = newNode;
        return;
    }
    // Add the new node at the end of the queue and change rear
    queue->rear->next = newNode;
    queue->rear = newNode;
    printf("Enqueued: %d\n", data);
}

cCopy codeint dequeue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1; // Returning -1 to indicate an empty queue
    }
    struct Node* temp = queue->front;
    int data = temp->data;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        // If the queue is empty, update rear to NULL
        queue->rear = NULL;
    }
    free(temp);
    printf("Dequeued: %d\n", data);
    return data;
}

cCopy codeint peek(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty.\n");
        return -1; // Returning -1 to indicate an empty queue
    }
    return queue->front->data;
}

cCopy codevoid printQueue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty.\n");
        return;
    }
    struct Node* temp = queue->front;
    printf("Queue: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

cCopy codeint main() {
    struct Queue* queue = createQueue();

    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);

    printQueue(queue);

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

    dequeue(queue);
    dequeue(queue);

    printQueue(queue);

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

    return 0;
}

Circular queues

A circular queue is a type of queue where the last position is connected back to the first position to form a circle. This allows efficient use of space, especially when the queue operates in a circular manner, i.e., when the end of the queue wraps around to the beginning.

Key Concepts

1. Circular Buffer: Unlike a linear queue, a circular queue uses a circular buffer where the rear of the queue wraps around to the front if there is space available.
2. Pointers: Two pointers, front and rear, are used to keep track of the beginning and end of the queue.
3. Overflow and Underflow: Circular queues handle overflow and underflow conditions differently. Overflow occurs when the queue is full, and underflow occurs when trying to dequeue from an empty queue.

Advantages

1. Efficient Space Utilization: Circular queues make use of the buffer space more effectively by reusing empty slots that become available as elements are dequeued.
2. Fixed Size: Unlike dynamic arrays or linked lists, circular queues have a fixed size, which simplifies memory management.

Array Implementation of a Circular Queue and it’s Operation

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

#define MAX 5 // Size of the circular queue

// Circular Queue Structure
struct CircularQueue {
    int front, rear, size;
    int items[MAX];
};

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

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

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

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

// Function to remove an element from the queue (dequeue)
int dequeue(struct CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1; // Returning -1 to indicate an empty queue
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        // Queue is empty after dequeue
        q->front = q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX;
    }
    q->size--;
    return item;
}

// Function to get the front element of the queue
int peek(struct CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1; // Returning -1 to indicate an empty queue
    }
    return q->items[q->front];
}

// Function to print the queue
void printQueue(struct CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return;
    }
    printf("Queue: ");
    int i = q->front;
    do {
        printf("%d ", q->items[i]);
        i = (i + 1) % MAX;
    } while (i != (q->rear + 1) % MAX);
    printf("\n");
}

// Main function to demonstrate circular queue operations
int main() {
    struct CircularQueue queue;
    initializeQueue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    enqueue(&queue, 40);
    enqueue(&queue, 50);
    enqueue(&queue, 60); // This should show "Queue is full" message

    printQueue(&queue);

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

    printQueue(&queue);

    enqueue(&queue, 70);
    enqueue(&queue, 80);

    printQueue(&queue);

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

    return 0;
}

#define MAX 5 // Size of the circular queue

// Circular Queue Structure
struct CircularQueue {
    int front, rear, size;
    int items[MAX];
};

void initializeQueue(struct CircularQueue* q) {
    q->front = q->rear = -1;
    q->size = 0;
}

bool isEmpty(struct CircularQueue* q) {
    return q->size == 0;
}

bool isFull(struct CircularQueue* q) {
    return q->size == MAX;
}

void enqueue(struct CircularQueue* q, int item) {
    if (isFull(q)) {
        printf("Queue is full. Cannot enqueue %d.\n", item);
        return;
    }
    if (isEmpty(q)) {
        q->front = q->rear = 0;
    } else {
        q->rear = (q->rear + 1) % MAX;
    }
    q->items[q->rear] = item;
    q->size++;
    printf("Enqueued: %d\n", item);
}

int dequeue(struct CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1; // Returning -1 to indicate an empty queue
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        // Queue is empty after dequeue
        q->front = q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX;
    }
    q->size--;
    return item;
}

int peek(struct CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1; // Returning -1 to indicate an empty queue
    }
    return q->items[q->front];
}

void printQueue(struct CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return;
    }
    printf("Queue: ");
    int i = q->front;
    do {
        printf("%d ", q->items[i]);
        i = (i + 1) % MAX;
    } while (i != (q->rear + 1) % MAX);
    printf("\n");
}

int main() {
    struct CircularQueue queue;
    initializeQueue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    enqueue(&queue, 40);
    enqueue(&queue, 50);
    enqueue(&queue, 60); // This should show "Queue is full" message

    printQueue(&queue);

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

    printQueue(&queue);

    enqueue(&queue, 70);
    enqueue(&queue, 80);

    printQueue(&queue);

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

    return 0;
}

Linked list Array Implementation of a Circular Queue and it’s Operation

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

// Node structure for the linked list
struct Node {
    int data;
    struct Node* next;
};

// Circular Queue structure
struct CircularQueue {
    struct Node* front;
    struct Node* rear;
    int size;
};

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

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

// Function to add an element to the queue (enqueue)
void enqueue(struct CircularQueue* q, int item) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed.\n");
        return;
    }
    newNode->data = item;
    if (isEmpty(q)) {
        newNode->next = newNode; // Point to itself, circular link
        q->front = q->rear = newNode;
    } else {
        newNode->next = q->front; // New node points to the front
        q->rear->next = newNode; // Old rear node points to new node
        q->rear = newNode;       // Update rear to new node
    }
    q->size++;
    printf("Enqueued: %d\n", item);
}

// Function to remove an element from the queue (dequeue)
int dequeue(struct CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1; // Returning -1 to indicate an empty queue
    }
    struct Node* temp = q->front;
    int item = temp->data;
    if (q->front == q->rear) {
        // Only one node in the queue
        q->front = q->rear = NULL;
    } else {
        q->front = q->front->next; // Move front to the next node
        q->rear->next = q->front;  // Update rear to point to new front
    }
    free(temp); // Free the old front node
    q->size--;
    return item;
}

// Function to get the front element of the queue
int peek(struct CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1; // Returning -1 to indicate an empty queue
    }
    return q->front->data;
}

// Function to print the queue
void printQueue(struct CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return;
    }
    struct Node* current = q->front;
    printf("Queue: ");
    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != q->front); // Loop until we reach the front again
    printf("\n");
}

// Main function to demonstrate circular queue operations
int main() {
    struct CircularQueue queue;
    initializeQueue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    enqueue(&queue, 40);
    enqueue(&queue, 50);

    printQueue(&queue);

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

    printQueue(&queue);

    enqueue(&queue, 60);
    enqueue(&queue, 70);

    printQueue(&queue);

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

    return 0;
}

// Node structure for the linked list
struct Node {
    int data;
    struct Node* next;
};

// Circular Queue structure
struct CircularQueue {
    struct Node* front;
    struct Node* rear;
    int size;
};

void initializeQueue(struct CircularQueue* q) {
    q->front = q->rear = NULL;
    q->size = 0;
}

bool isEmpty(struct CircularQueue* q) {
    return q->size == 0;
}

void enqueue(struct CircularQueue* q, int item) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed.\n");
        return;
    }
    newNode->data = item;
    if (isEmpty(q)) {
        newNode->next = newNode; // Point to itself, circular link
        q->front = q->rear = newNode;
    } else {
        newNode->next = q->front; // New node points to the front
        q->rear->next = newNode; // Old rear node points to new node
        q->rear = newNode;       // Update rear to new node
    }
    q->size++;
    printf("Enqueued: %d\n", item);
}

int dequeue(struct CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1; // Returning -1 to indicate an empty queue
    }
    struct Node* temp = q->front;
    int item = temp->data;
    if (q->front == q->rear) {
        // Only one node in the queue
        q->front = q->rear = NULL;
    } else {
        q->front = q->front->next; // Move front to the next node
        q->rear->next = q->front;  // Update rear to point to new front
    }
    free(temp); // Free the old front node
    q->size--;
    return item;
}

int peek(struct CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1; // Returning -1 to indicate an empty queue
    }
    return q->front->data;
}

void printQueue(struct CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return;
    }
    struct Node* current = q->front;
    printf("Queue: ");
    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != q->front); // Loop until we reach the front again
    printf("\n");
}

int main() {
    struct CircularQueue queue;
    initializeQueue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    enqueue(&queue, 40);
    enqueue(&queue, 50);

    printQueue(&queue);

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

    printQueue(&queue);

    enqueue(&queue, 60);
    enqueue(&queue, 70);

    printQueue(&queue);

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

    return 0;
}

Application of Queues

1. Job Scheduling

• Operating Systems: In operating systems, queues manage processes in a ready queue. Processes waiting for CPU time are stored in a queue, ensuring that the CPU handles them in the order they arrive (FIFO: First In, First Out).
• Print Queue: In print spooling, print jobs are placed in a queue. The printer processes jobs in the order they were received, ensuring a fair and orderly printing process.

2. Task Scheduling

• Task Scheduling in Systems: Queues are used to manage tasks in systems where tasks are scheduled and executed in a specific order. For instance, task management in real-time systems or background job processing.

3. Breadth-First Search (BFS)

• Graph Algorithms: BFS uses a queue to explore nodes level by level. It’s employed in various algorithms, such as finding the shortest path in unweighted graphs and solving puzzles.

4. Data Buffering

• IO Buffers: Queues are used in buffering data between producers and consumers. For instance, keyboard buffering in input devices where keystrokes are stored in a queue before being processed by the system.
• Network Buffers: In network communications, packets are queued to handle variations in packet arrival rates, ensuring smooth data transmission.

5. Asynchronous Data Transfer

• Messaging Systems: Queues handle asynchronous communication between different parts of a system or between different systems. For example, in messaging systems like RabbitMQ or Apache Kafka, messages are queued for processing by consumers.
• Event Handling: In event-driven programming, events are queued and handled in the order they are received.

6. Order Processing Systems

• Customer Orders: E-commerce platforms use queues to manage and process customer orders. Orders are processed sequentially, ensuring that they are handled in the order they were placed.
• Call Centers: Incoming calls are queued to ensure that each call is answered in the order it arrives. This helps in managing the workload efficiently.

7. Simulation

• Queueing Theory: Queues are used in simulations to model real-world systems like customer service counters, ticket booking systems, and traffic flow. They help in analyzing and improving the performance of such systems.
• Event Simulations: In simulations like network packet routing or customer service, queues manage events and process them in the order they occur.

8. Memory Management

• Garbage Collection: Some garbage collection algorithms use queues to manage and track objects for cleanup. For instance, in reference counting systems, objects waiting to be deleted are placed in a queue.

9. Real-Time Systems

• Real-Time Scheduling: In real-time operating systems, queues are used to manage tasks that need to be executed in a timely manner. Tasks are scheduled based on priority and timing requirements.

10. Inter-process Communication

• Message Queues: In multi-threaded or multi-process systems, message queues are used for communication between different processes or threads. This ensures that messages are delivered and processed in an orderly manner.

11. Traffic Management

• Traffic Lights: In traffic management systems, queues manage the flow of vehicles at traffic signals, ensuring that vehicles pass through the intersection in an orderly manner.
• Simulation of Traffic Flow: Queues are used in simulations to model and analyze traffic flow, optimize signal timings, and reduce congestion.

Summary

Queues are essential in many areas of computing and real-world applications. Their ability to manage data in a FIFO manner makes them ideal for handling sequential processing tasks, managing resources, and improving efficiency in various systems. Whether in operating systems, network communications, simulations, or real-time processing, queues play a crucial role in maintaining order and managing tasks effectively.

Priority Queues

A priority queue is a data structure that allows elements to be processed based on their priority rather than just their order of arrival. It extends the concept of a regular queue by assigning a priority to each element, and the element with the highest priority is served before other elements with lower priorities.

Key Concepts

1. Priority: Each element in a priority queue has a priority value. The queue is organized such that elements with higher priority are dequeued before elements with lower priority.
2. Types of Priority Queues:
   • Max-Priority Queue: The element with the maximum priority is served first.
   • Min-Priority Queue: The element with the minimum priority is served first.

Operations

1. Insert (Enqueue): Add an element to the priority queue with a given priority.
2. Remove (Dequeue): Remove the element with the highest (or lowest) priority.
3. Peek: View the element with the highest (or lowest) priority without removing it.
4. Change Priority: Update the priority of an element in the queue.

Implementation

Priority queues can be implemented using several underlying data structures:

1. Binary Heap
2. Binary Search Tree
3. Fibonacci Heap
4. Pairing Heap

priority Queue using a single two Dimensional Array

Here’s a conceptual explanation of how a priority queue using a single two-dimensional array works, along with its representation:

Conceptual Overview

1. Two-Dimensional Array Representation
   • The two-dimensional array is used to represent multiple priority levels. Each row in the array corresponds to a different priority level, and each column in the row stores an element.
2. Priority Levels
   • Each row of the array represents a distinct priority level. For example, row 0 could represent the highest priority, while row kkk represents a lower priority.
3. Front and Rear Indexes
   • front[i]: Points to the index of the first element in the queue for priority level i.
   • rear[i]: Points to the index of the last element in the queue for priority level i.
4. Insertion (Enqueue)
   • When an element is added to the priority queue, it is placed in the row corresponding to its priority level. The rear index for that priority level is updated to point to the new last element.
5. Deletion (Dequeue)
   • To remove an element, the queue checks from the highest priority level (row 0) to the lowest. It removes the element at the front index of the highest priority level that is not empty. The front index is updated, and if the queue becomes empty, the front and rear indexes are reset.
6. Peek
   • To view the element with the highest priority, the queue looks at the front index of the highest priority level that is not empty.

Representation

Here’s a visual representation of the priority queue using a two-dimensional array:

Priority Level 0 (Highest Priority): [20, 50, ...]  // Elements with highest priority
Priority Level 1: [10, 40, ...]                    // Elements with medium priority
Priority Level 2 (Lowest Priority): [30, ...]      // Elements with lowest priority

Example Operations

1. Inserting Elements
   • Insert 10 with Priority 1:
     Priority Level 0: []
Priority Level 1: [10]
Priority Level 2: []
   • Insert 20 with Priority 0:
     Priority Level 0: [20]
Priority Level 1: [10]
Priority Level 2: []
2. Dequeue Operation
   • Remove an element:
     • Dequeue checks priority level 0 first, finds 20, removes it, and updates front for priority 0.
     • Remaining:
       Priority Level 0: []
Priority Level 1: [10]
Priority Level 2: []
3. Peek Operation
   • Peek looks at priority level 0 (highest priority), and returns the element at the front index. If empty, it moves to the next priority level.

Summary

In summary, a priority queue using a two-dimensional array organizes elements into rows based on priority levels. Each row operates as an independent queue, and elements are processed based on the priority level: higher-priority elements are dequeued before lower-priority elements. This approach simplifies priority management but may not be as efficient as other data structures like binary heaps.