Mastering Queues: Day 8 DSA Challenge

Welcome to Day 9 of the 100 Days DSA Challenge! Today, we will dive into the concept of queues, a fundamental data structure used in various applications. We will explore different types of queues and their implementations using C language. Let's get started!

1. Implement a Queue Using Arrays

Problem: Implement a queue using arrays with basic operations: enqueue, dequeue, and display.

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

#define MAX 100

int queue[MAX];
int front = -1;
int rear = -1;

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

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

void display() {
    if (front == -1 || front > rear) {
        printf("Queue is empty\n");
    } else {
        for (int i = front; i <= rear; i++) {
            printf("%d ", queue[i]);
        }
        printf("\n");
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    printf("Dequeued element: %d\n", dequeue());
    display();
    return 0;
}

2. Implement a Circular Queue

Problem: Write a program to implement a circular queue.

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

#define MAX 100

int cqueue[MAX];
int front = -1;
int rear = -1;

void enqueue(int value) {
    if ((front == 0 && rear == MAX - 1) || (rear == (front - 1) % (MAX - 1))) {
        printf("Circular Queue overflow\n");
    } else {
        if (front == -1) {
            front = rear = 0;
        } else if (rear == MAX - 1 && front != 0) {
            rear = 0;
        } else {
            rear++;
        }
        cqueue[rear] = value;
    }
}

int dequeue() {
    if (front == -1) {
        printf("Circular Queue underflow\n");
        return -1;
    }

    int data = cqueue[front];
    if (front == rear) {
        front = rear = -1;
    } else if (front == MAX - 1) {
        front = 0;
    } else {
        front++;
    }
    return data;
}

void display() {
    if (front == -1) {
        printf("Circular Queue is empty\n");
    } else {
        if (rear >= front) {
            for (int i = front; i <= rear; i++) {
                printf("%d ", cqueue[i]);
            }
        } else {
            for (int i = front; i < MAX; i++) {
                printf("%d ", cqueue[i]);
            }
            for (int i = 0; i <= rear; i++) {
                printf("%d ", cqueue[i]);
            }
        }
        printf("\n");
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    printf("Dequeued element: %d\n", dequeue());
    display();
    return 0;
}

3. First Non-Repeating Character in a Stream of Characters

Problem: Solve the "first non-repeating character in a stream of characters" problem using a queue.

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

#define MAX 256

char queue[MAX];
int front = 0;
int rear = -1;
int charCount[MAX] = {0};

void enqueue(char c) {
    queue[++rear] = c;
}

char dequeue() {
    if (front > rear) {
        return '\0';
    } else {
        return queue[front++];
    }
}

char firstNonRepeating(char str[]) {
    for (int i = 0; i < strlen(str); i++) {
        enqueue(str[i]);
        charCount[str[i]]++;

        while (front <= rear && charCount[queue[front]] > 1) {
            dequeue();
        }
    }

    if (front <= rear) {
        return queue[front];
    } else {
        return '\0';
    }
}

int main() {
    char str[] = "aabcbd";
    char result = firstNonRepeating(str);
    if (result != '\0') {
        printf("First non-repeating character: %c\n", result);
    } else {
        printf("All characters are repeating.\n");
    }
    return 0;
}

4. Implement a Priority Queue Using a Heap

Problem: Implement a priority queue using a heap.

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

#define MAX 100

int heap[MAX];
int heapSize = 0;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapifyUp(int index) {
    int parentIndex = (index - 1) / 2;
    if (parentIndex >= 0 && heap[parentIndex] < heap[index]) {
        swap(&heap[parentIndex], &heap[index]);
        heapifyUp(parentIndex);
    }
}

void heapifyDown(int index) {
    int leftChild = 2 * index + 1;
    int rightChild = 2 * index + 2;
    int largest = index;

    if (leftChild < heapSize && heap[leftChild] > heap[largest]) {
        largest = leftChild;
    }
    if (rightChild < heapSize && heap[rightChild] > heap[largest]) {
        largest = rightChild;
    }
    if (largest != index) {
        swap(&heap[index], &heap[largest]);
        heapifyDown(largest);
    }
}

void enqueue(int value) {
    heap[heapSize] = value;
    heapifyUp(heapSize);
    heapSize++;
}

int dequeue() {
    if (heapSize == 0) {
        printf("Priority Queue underflow\n");
        return -1;
    }

    int root = heap[0];
    heap[0] = heap[--heapSize];
    heapifyDown(0);
    return root;
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    printf("Dequeued element: %d\n", dequeue());
    enqueue(5);
    enqueue(25);
    printf("Dequeued element: %d\n", dequeue());
    return 0;
}

5. Sliding Window Maximum

Problem: Solve the "sliding window maximum" problem using a deque.

#include <stdio.h>

#define MAX 100

int deque[MAX];
int front = -1;
int rear = -1;

void push_back(int value) {
    if (rear == MAX - 1) {
        printf("Deque overflow\n");
    } else {
        if (front == -1) front = 0;
        deque[++rear] = value;
    }
}

void pop_front() {
    if (front == -1 || front > rear) {
        printf("Deque underflow\n");
    } else {
        front++;
    }
}

void pop_back() {
    if (front == -1 || front > rear) {
        printf("Deque underflow\n");
    } else {
        rear--;
    }
}

int get_front() {
    if (front != -1) {
        return deque[front];
    }
    return -1;
}

void slidingWindowMaximum(int arr[], int n, int k) {
    for (int i = 0; i < k; i++) {
        while (rear >= front && arr[i] >= arr[deque[rear]]) {
            pop_back();
        }
        push_back(i);
    }

    for (int i = k; i < n; i++) {
        printf("%d ", arr[get_front()]);

        while (front <= rear && deque[front] <= i - k) {
            pop_front();
        }
        while (rear >= front && arr[i] >= arr[deque[rear]]) {
            pop_back();
        }
        push_back(i);
    }
    printf("%d\n", arr[get_front()]);
}

int main() {
    int arr[] = {1, 3, -1, -3, 5, 3, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    slidingWindowMaximum(arr, n, k);
    return 0;
}

Conclusion

That wraps up Day 9 of our DSA challenge! We explored various problems related to queues and implemented solutions in C language. Queues are a versatile data structure that can be used in many different scenarios, making them an essential tool in our data structures toolkit. Keep practicing, and you'll become more proficient with queues and other data structures.

Stay tuned for more exciting problems and solutions as we continue to improve our skills in data structures and algorithms.

Day 9 of the 100 Days DSA Challenge: Queues

Table of contents