DSA Unit 2

What is a Queue?

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle.

The element inserted first is the one removed first. Think of it like people standing in line at a ticket counter.

Queue Terminology

• Front (Head): The index or pointer where deletion happens
• Rear (Tail): The index or pointer where insertion happens
• Enqueue (Insertion): Adding an element at the rear
• Dequeue (Deletion): Removing an element from the front
• Peek/Front: Get the element at the front without removing it
• isEmpty: Check if queue has no elements
• isFull (for array): Check if queue cannot insert more elements

Types of Queues

• Simple Queue: Basic FIFO
• Circular Queue: Fixes wasted space in array queue
• Double-Ended Queue (Deque): Insert/delete at both ends
• Priority Queue: Each element has priority

Queue Implementation Using Array

Here, we use a fixed-size array. After several enqueues and dequeues, even if space is available in the beginning of the array, it can't be reused (Solution: Circular Queue).

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5

struct Queue {
    int items[SIZE];
    int front, rear;
};

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

int isFull(struct Queue* q) {
    return q->rear == SIZE - 1;
}

int isEmpty(struct Queue* q) {
    return q->front == -1 || q->front > q->rear;
}

void enqueue(struct Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue is Full\n");
        return;
    }
    if (q->front == -1) q->front = 0;
    q->items[++q->rear] = value;
    printf("%d enqueued\n", value);
}

int dequeue(struct Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is Empty\n");
        return -1;
    }
    int val = q->items[q->front++];
    if (q->front > q->rear) {
        q->front = q->rear = -1;
    }
    return val;
}

int peek(struct Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is Empty\n");
        return -1;
    }
    return q->items[q->front];
}

void display(struct Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is Empty\n");
        return;
    }
    printf("Queue: ");
    for (int i = q->front; i <= q->rear; i++) {
        printf("%d ", q->items[i]);
    }
    printf("\n");
}

Queue Implementation Using Linked List

Here, we dynamically allocate nodes. No fixed size like array.

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

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

struct Queue {
    struct Node *front, *rear;
};

void initQueue(struct Queue* q) {
    q->front = q->rear = NULL;
}

int isEmpty(struct Queue* q) {
    return q->front == NULL;
}

void enqueue(struct Queue* q, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    printf("%d enqueued\n", value);
}

int dequeue(struct Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is Empty\n");
        return -1;
    }
    struct Node* temp = q->front;
    int val = temp->data;
    q->front = q->front->next;

    if (q->front == NULL) q->rear = NULL;

    free(temp);
    return val;
}

int peek(struct Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is Empty\n");
        return -1;
    }
    return q->front->data;
}

void display(struct Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is Empty\n");
        return;
    }
    struct Node* temp = q->front;
    printf("Queue: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

Circular Queue

In a Simple Queue (array), once rear reaches the end, no more insertions, even if space is freed at front. Circular Queue connects last position back to the first using modulo arithmetic. Used in CPU scheduling and memory buffers.

Array Implementation

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

#define SIZE 5

struct queue {
    int items[SIZE];
    int front, rear;
};

void init(struct queue* q) {
    q->front = -1;
    q->rear = -1;
}

int isEmpty(struct queue* q) {
    return q->front == -1;
}

int isFull(struct queue* q) {
    return (q->rear + 1) % SIZE == q->front;
}

int qinsert(struct queue* q, int x) {
    if (isFull(q)) {
        printf("Queue Overflow..\n");
        return -1;
    }
    q->rear = (q->rear + 1) % SIZE;
    q->items[q->rear] = x;
    if (q->front == -1)
        q->front = 0;
    printf("Enqueued %d\n", x);
    return 1;
}

int removeq(struct queue* q) {
    if (isEmpty(q)) {
        printf("Queue Empty..\n");
        return -1;
    }
    int x = q->items[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;
    } else {
        q->front = (q->front + 1) % SIZE;
    }
    return x;
}

void display(struct queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty..\n");
        return;
    }
    printf("Queue elements: ");
    int i = q->front;
    while (1) {
        printf("%d ", q->items[i]);
        if (i == q->rear) break;
        i = (i + 1) % SIZE;
    }
    printf("\n");
}

Linked List Implementation

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

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

struct cqu{
    struct Node *front, *rear;
};

void init(struct cqu* q){
    q->front = NULL;
    q->rear = NULL;
}

int isEmpty(struct cqu* q){
    return q->front == NULL;
}

void enqueue(struct cqu* q, int value){
    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
    newnode->data = value;
    if(isEmpty(q)){
        q->front = q->rear = newnode;
        newnode->next = newnode;
    } else {
        newnode->next = q->front;
        q->rear->next = newnode;
        q->rear = newnode;
    }
    printf("Enqueued %d\n", value);
}

int dequeue(struct cqu* q){
    if(isEmpty(q)){
        printf("Queue is empty\n");
        return -1;
    }
    int x = q->front->data;
    if(q->front == q->rear){
        free(q->front);
        q->front = q->rear = NULL;
    } else {
        struct Node* temp = q->front;
        q->front = q->front->next;
        q->rear->next = q->front;
        free(temp);
    }
    return x;
}

void display(struct cqu* q){
    if(isEmpty(q)){
        printf("Queue is empty\n");
        return;
    }
    printf("Queue elements: ");
    struct Node* temp = q->front;
    do{
        printf("%d ", temp->data);
        temp = temp->next;
    } while(temp != q->front);
    printf("\n");
}

Double Ended Queue (Deque)

Deque allows insertions and deletions at both front and rear. Used in palindrome checking and sliding window problems.

Circular Deque Using Array

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5

struct Deque {
    int items[SIZE];
    int front, rear;
};

void initDeque(struct Deque* dq) {
    dq->front = dq->rear = -1;
}

int isFull(struct Deque* dq) {
    return (dq->rear + 1) % SIZE == dq->front;
}

int isEmpty(struct Deque* dq) {
    return dq->front == -1;
}

void insertFront(struct Deque* dq, int value) {
    if (isFull(dq)) {
        printf("Deque Full\n");
        return;
    }
    if (dq->front == -1) {
        dq->front = dq->rear = 0;
    } else if (dq->front == 0) {
        dq->front = SIZE - 1;
    } else {
        dq->front--;
    }
    dq->items[dq->front] = value;
    printf("%d inserted at front\n", value);
}

void insertRear(struct Deque* dq, int value) {
    if (isFull(dq)) {
        printf("Deque Full\n");
        return;
    }
    if (dq->front == -1) {
        dq->front = dq->rear = 0;
    } else if (dq->rear == SIZE - 1) {
        dq->rear = 0;
    } else {
        dq->rear++;
    }
    dq->items[dq->rear] = value;
    printf("%d inserted at rear\n", value);
}

int deleteFront(struct Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque Empty\n");
        return -1;
    }
    int val = dq->items[dq->front];
    if (dq->front == dq->rear) {
        dq->front = dq->rear = -1;
    } else if (dq->front == SIZE - 1) {
        dq->front = 0;
    } else {
        dq->front++;
    }
    return val;
}

int deleteRear(struct Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque Empty\n");
        return -1;
    }
    int val = dq->items[dq->rear];
    if (dq->front == dq->rear) {
        dq->front = dq->rear = -1;
    } else if (dq->rear == 0) {
        dq->rear = SIZE - 1;
    } else {
        dq->rear--;
    }
    return val;
}

Deque Using Linked List

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

struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

struct Node *front = NULL, *rear = NULL;

void insertFront(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = front;

    if (front == NULL) rear = newNode;
    else front->prev = newNode;
    front = newNode;

    printf("%d inserted at front\n", value);
}

void insertRear(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    newNode->prev = rear;

    if (rear == NULL) front = newNode;
    else rear->next = newNode;
    rear = newNode;

    printf("%d inserted at rear\n", value);
}

int deleteFront() {
    if (front == NULL) {
        printf("Deque Empty\n");
        return -1;
    }
    int val = front->data;
    struct Node* temp = front;
    front = front->next;
    if (front) front->prev = NULL;
    else rear = NULL;
    free(temp);
    return val;
}

int deleteRear() {
    if (rear == NULL) {
        printf("Deque Empty\n");
        return -1;
    }
    int val = rear->data;
    struct Node* temp = rear;
    rear = rear->prev;
    if (rear) rear->next = NULL;
    else front = NULL;
    free(temp);
    return val;
}

Priority Queue

Each element has a priority. Deletion always removes the highest/lowest priority element, not FIFO order. Used in OS scheduling, Dijkstra's shortest path, and Huffman coding.

Ordered Insert - Descending Priority Queue

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10

struct PQueue {
    int data;
    int pty;
};

struct PQueue pq[SIZE];
int count = 0;

void init() {
    count = 0;
}

int isFull() {
    return count == SIZE;
}

int isEmpty() {
    return count == 0;
}

void enq(int x, int p) {
    if (isFull()) {
        printf("Priority Queue Full..\n");
        return;
    }
    struct PQueue key;
    key.data = x;
    key.pty  = p;

    int j = count - 1;
    while (j >= 0 && pq[j].pty < key.pty) {
        pq[j + 1] = pq[j];
        j--;
    }

    pq[j + 1] = key;
    count++;
    printf("%d inserted with priority %d\n", x, p);
}

struct PQueue deq() {
    struct PQueue item;
    if (isEmpty()) {
        printf("Priority Queue Empty..\n");
        item.data = 0;
        item.pty  = -1;
        return item;
    }
    item = pq[0];
    for (int i = 1; i < count; i++) {
        pq[i - 1] = pq[i];
    }
    count--;
    return item;
}

void display() {
    if (isEmpty()) {
        printf("Priority Queue Empty..\n");
        return;
    }
    printf("Priority Queue (data:priority): ");
    for (int i = 0; i < count; i++) {
        printf("[%d:%d] ", pq[i].data, pq[i].pty);
    }
    printf("\n");
}

Josephus Problem

The Josephus problem is a theoretical problem where people stand in a circle and every nth person is eliminated until only one survives.

Using Circular Linked List

struct Node* insert(struct Node* head, char name[]) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    strcpy(newNode->name, name);

    if (head == NULL) {
        newNode->next = newNode;
        head = newNode;
        return head;
    }

    struct Node* temp = head;
    while (temp->next != head)
        temp = temp->next;

    temp->next = newNode;
    newNode->next = head;

    return head;
}

void josephus(struct Node** head, int n) {
    struct Node* p = *head;
    struct Node* q = NULL;

    while (p->next != p) {
        for (int i = 0; i < n - 1; i++) {
            q = p;
            p = p->next;
        }

        printf("%s has been killed.\n", p->name);
        q->next = p->next;
        free(p);
        p = q->next;
    }

    printf("%s survives!\n", p->name);
    *head = p;
}

Using Circular Queue

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 50

struct Queue {
    char items[SIZE][50];
    int front, rear;
};

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

int isFull(struct Queue* q) {
    return (q->rear + 1) % SIZE == q->front;
}

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

void enq(struct Queue* q, char name[]) {
    if (isFull(q)) {
        printf("Queue Full\n");
        return;
    }
    if (q->front == -1) q->front = 0;

    q->rear = (q->rear + 1) % SIZE;
    strcpy(q->items[q->rear], name);
}

void deq(struct Queue* q, char name[]) {
    if (isEmpty(q)) {
        printf("Queue Empty\n");
        return;
    }
    strcpy(name, q->items[q->front]);
    if (q->front == q->rear) {
        q->front = q->rear = -1;
    } else {
        q->front = (q->front + 1) % SIZE;
    }
}

int size(struct Queue* q) {
    if (isEmpty(q)) return 0;
    if (q->rear >= q->front) return q->rear - q->front + 1;
    return SIZE - q->front + q->rear + 1;
}

void josephus(struct Queue* q, int n) {
    char temp[50];

    while (size(q) > 1) {
        for (int i = 0; i < n - 1; i++) {
            deq(q, temp);
            enq(q, temp);
        }
        deq(q, temp);
        printf("%s has been killed.\n", temp);
    }

    deq(q, temp);
    printf("%s survives!\n", temp);
}

Binary Trees - Iterative Traversals

Inorder Traversal (Left-Root-Right)

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Stack {
    struct Node** array;
    int top;
    int capacity;
};

struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

struct Stack* createStack(int capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (struct Node**)malloc(capacity * sizeof(struct Node*));
    return stack;
}

int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

void push(struct Stack* stack, struct Node* node) {
    if(stack->top == stack->capacity - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack->array[++stack->top] = node;
}

struct Node* pop(struct Stack* stack) {
    if(isEmpty(stack)) {
        return NULL;
    }
    return stack->array[stack->top--];
}

void iterativeInorder(struct Node* root) {
    struct Stack* stack = createStack(100);
    struct Node* current = root;

    while(!isEmpty(stack) || current != NULL) {
        while(current != NULL) {
            push(stack, current);
            current = current->left;
        }

        current = pop(stack);
        printf("%d ", current->data);

        current = current->right;
    }
}

Preorder Traversal (Root-Left-Right)

void iterativePreorder(struct Node* root) {
    if (root == NULL) return;

    struct Stack* stack = createStack(100);
    push(stack, root);

    while (!isEmpty(stack)) {
        struct Node* current = pop(stack);
        printf("%d ", current->data);

        if (current->right) push(stack, current->right);
        if (current->left) push(stack, current->left);
    }
}

Postorder Traversal (Left-Right-Root)

void iterativePostorder(struct Node* root) {
    if (root == NULL) return;

    struct Stack* stack1 = createStack(100);
    struct Stack* stack2 = createStack(100);

    push(stack1, root);

    while (!isEmpty(stack1)) {
        struct Node* current = pop(stack1);
        push(stack2, current);

        if (current->left) push(stack1, current->left);
        if (current->right) push(stack1, current->right);
    }

    while (!isEmpty(stack2)) {
        struct Node* node = pop(stack2);
        printf("%d ", node->data);
    }
}

Queue Comparison