PROBLEM SOLVING - QUEUES IN C INTRODUCTION

Queue Basics in C

Queue Definition

A queue in C is a linear data structure that follows the First-In-First-Out (FIFO) principle. Key characteristics:

FIFO Principle - First element added is the first to be removed
Two ends - Front for removal, rear for insertion
Dynamic size - Can grow and shrink as needed

// Basic structure:
#define SIZE 100
int queue[SIZE];
int front = -1, rear = -1;

Queue Applications

Queues are fundamental in computer science with various applications:

CPU scheduling
Breadth-First Search (BFS)
Printer job scheduling
Call center systems
Network packet handling
Simulation of real-world queues
Asynchronous data transfer

Queue Operations

Basic queue operations and their implementations:

// Enqueue operation
void enqueue(int value) {
    if(rear == SIZE-1) {
        printf("Queue Overflow");
    } else {
        if(front == -1) front = 0;
        rear++;
        queue[rear] = value;
    }
}

// Dequeue operation
int dequeue() {
    if(front == -1 || front > rear) {
        printf("Queue Underflow");
        return -1;
    } else {
        int value = queue[front];
        front++;
        return value;
    }
}

Types of Queues

Different variations of queues with specific use cases:

Linear Queue - Simple FIFO structure
Circular Queue - Efficient memory utilization
Priority Queue - Elements with priority
Double-ended Queue (Deque) - Insert/remove from both ends
Blocking Queue - Thread-safe operations

PROBLEM SOLVING - QUEUE TRICKS

Queue Manipulation Approaches

#	Technique	Use Case	Approach	Complexity	Examples
1	Two-Queue	Implement stack using queues or level-order traversal	Use two queues to alternate between operations	O(n)	Implement stack with queues BFS traversal Zigzag traversal
2	Circular Queue	Efficient memory utilization in fixed-size queues	Use modulo arithmetic for circular indexing	O(1)	CPU scheduling Memory management Traffic systems
3	Priority Queue	Process elements based on priority	Implement using heap or ordered array	O(log n)	Dijkstra's algorithm Huffman coding Task scheduling
4	BFS	Level-order traversal or shortest path	Use queue to track current level nodes	O(V+E)	Tree traversal Graph traversal Shortest path in unweighted graph
5	Deque	Sliding window problems or palindrome checks	Insert/remove from both ends as needed	O(1)	Sliding window maximum Palindrome checker Undo/Redo operations

Common Queue Operations

Queue Implementation

#define SIZE 100
int queue[SIZE];
int front = -1, rear = -1;

void enqueue(int value) {
    if(rear == SIZE-1) {
        printf("Queue Overflow");
    } else {
        if(front == -1) front = 0;
        rear++;
        queue[rear] = value;
    }
}

int dequeue() {
    if(front == -1 || front > rear) {
        printf("Queue Underflow");
        return -1;
    } else {
        return queue[front++];
    }
}

Time Complexity: O(1) for both operations

Circular Queue

#define SIZE 100
int queue[SIZE];
int front = -1, rear = -1;

void enqueue(int value) {
    if((rear + 1) % SIZE == front) {
        printf("Queue Full");
    } else {
        if(front == -1) front = 0;
        rear = (rear + 1) % SIZE;
        queue[rear] = value;
    }
}

int dequeue() {
    if(front == -1) {
        printf("Queue Empty");
        return -1;
    } else {
        int val = queue[front];
        if(front == rear) front = rear = -1;
        else front = (front + 1) % SIZE;
        return val;
    }
}

Efficient memory utilization

Queue Using Stacks

// Using two stacks
void enqueue(int x) {
    // Push to stack1
    push(stack1, x);
}

int dequeue() {
    if(isEmpty(stack2)) {
        while(!isEmpty(stack1)) {
            push(stack2, pop(stack1));
        }
    }
    return pop(stack2);
}

Amortized O(1) time

BFS Implementation

void BFS(int start) {
    int visited[MAX] = {0};
    enqueue(start);
    visited[start] = 1;
    
    while(!isEmpty()) {
        int current = dequeue();
        printf("%d ", current);
        
        for(int i = 0; i < MAX; i++) {
            if(graph[current][i] && !visited[i]) {
                enqueue(i);
                visited[i] = 1;
            }
        }
    }
}

Time Complexity: O(V+E)

Priority Queue

void enqueue(int value, int priority) {
    Node* new = createNode(value, priority);
    
    if(*head == NULL || priority < (*head)->priority) {
        new->next = *head;
        *head = new;
    } else {
        Node* temp = *head;
        while(temp->next != NULL && 
              temp->next->priority <= priority) {
            temp = temp->next;
        }
        new->next = temp->next;
        temp->next = new;
    }
}

int dequeue() {
    if(*head == NULL) return -1;
    Node* temp = *head;
    int val = temp->data;
    *head = (*head)->next;
    free(temp);
    return val;
}

O(n) insertion, O(1) removal

Advanced Queue Techniques

#	Technique	Description	Use Case
1	Double-ended Queue	Queue that allows insertion and removal from both ends	Sliding window problems, undo operations
2	Blocking Queue	Thread-safe queue that blocks when empty or full	Producer-consumer problems
3	Priority Queue with Heap	Efficient priority queue implementation using binary heap	Dijkstra's algorithm, Huffman coding
4	Multilevel Queue	Multiple queues with different priorities for scheduling	Operating system scheduling
5	Message Queue	Inter-process communication through message passing	Distributed systems
6	Circular Buffer	Fixed-size circular queue for streaming data	Audio processing, network buffers

Related Queue Resources

Basic Programs

Interview Questions

MCQs

Queue Tricks