Chapter 7: Queues

Introduction

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle: the first element added is the first one removed. Think of a line at a ticket counter—people join at the back and leave from the front. This fundamental abstraction models many real-world systems and computing scenarios.

Why This Matters

Queues are everywhere in computing:

• Task scheduling: Operating systems manage processes
• Breadth-First Search: Graph and tree traversal
• Request handling: Web servers process requests in order
• Print spooler: Print jobs queued for execution
• Buffering: Data streams in networking
• Customer service: Call centers, support tickets

Understanding queues teaches:

• FIFO ordering and fairness
• Different implementation trade-offs
• Circular buffer optimization
• Priority-based ordering variations

How to Study This Chapter

1. Visualize operations - Draw queue state after enqueue/dequeue
2. Implement multiple types - Simple, circular, priority queues
3. Compare implementations - Array vs linked list trade-offs
4. Solve problems - Practice with BFS, scheduling scenarios
5. Understand applications - See where queues appear in systems

Queue Operations

Core Operations

1. enqueue(x) - Add element to rear - O(1)
2. dequeue() - Remove and return front element - O(1)
3. peek()/front() - View front element without removing - O(1)
4. isEmpty() - Check if queue is empty - O(1)
5. size() - Get number of elements - O(1)

Visualization

Enqueue operations:           Dequeue operations:

enqueue(10): [10]            dequeue(): [10, 20, 30]
enqueue(20): [10, 20]                   [20, 30]  (returns 10)
enqueue(30): [10, 20, 30]               [30]      (returns 20)
            FRONT→  →REAR               FRONT→

Simple Queue Implementation

C Implementation (Array-Based)

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

#define MAX_SIZE 100

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

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

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

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

void enqueue(Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue Overflow\n");
        return;
    }

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

    q->items[++(q->rear)] = value;
}

int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue Underflow\n");
        return -1;
    }

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

    if (q->front == q->rear) {
        // Last element
        q->front = q->rear = -1;
    } else {
        q->front++;
    }

    return value;
}

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

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

void display(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");
}

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

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

    display(&q);  // Queue: 10 20 30

    printf("Dequeued: %d\n", dequeue(&q));  // 10
    printf("Front: %d\n", peek(&q));        // 20

    display(&q);  // Queue: 20 30

    return 0;
}

C++ Implementation

#include <iostream>
#include <deque>
using namespace std;

class Queue {
private:
    deque<int> items;

public:
    void enqueue(int value) {
        items.push_back(value);
    }

    int dequeue() {
        if (isEmpty()) {
            throw runtime_error("Queue Underflow");
        }
        int value = items.front();
        items.pop_front();
        return value;
    }

    int peek() {
        if (isEmpty()) {
            throw runtime_error("Queue is empty");
        }
        return items.front();
    }

    bool isEmpty() {
        return items.empty();
    }

    int size() {
        return items.size();
    }

    void display() {
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return;
        }
        cout << "Queue: ";
        for (int item : items) {
            cout << item << " ";
        }
        cout << endl;
    }
};

int main() {
    Queue q;

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    q.display();  // Queue: 10 20 30

    cout << "Dequeued: " << q.dequeue() << endl;  // 10
    cout << "Front: " << q.peek() << endl;        // 20

    q.display();  // Queue: 20 30

    return 0;
}

Java Implementation

import java.util.LinkedList;

class Queue {
    private LinkedList<Integer> items;

    public Queue() {
        items = new LinkedList<>();
    }

    public void enqueue(int value) {
        items.addLast(value);
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue Underflow");
        }
        return items.removeFirst();
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return items.getFirst();
    }

    public boolean isEmpty() {
        return items.isEmpty();
    }

    public int size() {
        return items.size();
    }

    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        System.out.print("Queue: ");
        for (int item : items) {
            System.out.print(item + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Queue q = new Queue();

        q.enqueue(10);
        q.enqueue(20);
        q.enqueue(30);

        q.display();  // Queue: 10 20 30

        System.out.println("Dequeued: " + q.dequeue());  // 10
        System.out.println("Front: " + q.peek());        // 20

        q.display();  // Queue: 20 30
    }
}

Circular Queue

Problem with simple queue: After dequeuing, front moves forward, wasting space at the beginning.

Solution: Circular queue treats array as circular—when rear reaches end, wrap around to beginning.

Visualization

Initial (size=5):
[_ _ _ _ _]
 F,R

After enqueue(10,20,30):
[10 20 30 _ _]
 F        R

After dequeue() twice:
[_ _ 30 _ _]
     F  R

After enqueue(40,50,60):
[60 _ 30 40 50]
    R  F

Wraps around! Front at index 2, rear at index 0.

C Implementation

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

#define MAX_SIZE 5

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

void initQueue(CircularQueue* q) {
    q->front = 0;
    q->rear = -1;
    q->count = 0;
}

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

bool isFull(CircularQueue* q) {
    return q->count == MAX_SIZE;
}

void enqueue(CircularQueue* q, int value) {
    if (isFull(q)) {
        printf("Queue Overflow\n");
        return;
    }

    q->rear = (q->rear + 1) % MAX_SIZE;
    q->items[q->rear] = value;
    q->count++;
}

int dequeue(CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue Underflow\n");
        return -1;
    }

    int value = q->items[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    q->count--;

    return value;
}

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

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

    printf("Queue: ");
    int i = q->front;
    for (int c = 0; c < q->count; c++) {
        printf("%d ", q->items[i]);
        i = (i + 1) % MAX_SIZE;
    }
    printf("\n");
}

int main() {
    CircularQueue q;
    initQueue(&q);

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

    display(&q);  // Queue: 10 20 30 40 50

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

    display(&q);  // Queue: 30 40 50

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

    display(&q);  // Queue: 30 40 50 60 70

    return 0;
}

Linked List-Based Queue

C Implementation

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

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

typedef struct {
    Node* front;
    Node* rear;
    int count;
} Queue;

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

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

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

    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }

    q->count++;
}

int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue Underflow\n");
        return -1;
    }

    Node* temp = q->front;
    int value = temp->data;

    q->front = q->front->next;

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

    free(temp);
    q->count--;

    return value;
}

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

int size(Queue* q) {
    return q->count;
}

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

    printf("Queue: ");
    Node* current = q->front;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

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

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

    display(&q);

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

    display(&q);

    return 0;
}

Priority Queue

Elements dequeued based on priority, not insertion order.

Simple Array-Based Priority Queue

C Implementation:

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

#define MAX_SIZE 100

typedef struct {
    int value;
    int priority;
} Element;

typedef struct {
    Element items[MAX_SIZE];
    int size;
} PriorityQueue;

void initPQ(PriorityQueue* pq) {
    pq->size = 0;
}

bool isEmpty(PriorityQueue* pq) {
    return pq->size == 0;
}

bool isFull(PriorityQueue* pq) {
    return pq->size == MAX_SIZE;
}

void enqueue(PriorityQueue* pq, int value, int priority) {
    if (isFull(pq)) {
        printf("Priority Queue Overflow\n");
        return;
    }

    int i = pq->size - 1;

    // Shift elements with lower priority
    while (i >= 0 && pq->items[i].priority < priority) {
        pq->items[i + 1] = pq->items[i];
        i--;
    }

    pq->items[i + 1].value = value;
    pq->items[i + 1].priority = priority;
    pq->size++;
}

int dequeue(PriorityQueue* pq) {
    if (isEmpty(pq)) {
        printf("Priority Queue Underflow\n");
        return -1;
    }

    int value = pq->items[pq->size - 1].value;
    pq->size--;

    return value;
}

int peek(PriorityQueue* pq) {
    if (isEmpty(pq)) {
        printf("Priority Queue is empty\n");
        return -1;
    }
    return pq->items[pq->size - 1].value;
}

void display(PriorityQueue* pq) {
    if (isEmpty(pq)) {
        printf("Priority Queue is empty\n");
        return;
    }

    printf("Priority Queue (value:priority): ");
    for (int i = pq->size - 1; i >= 0; i--) {
        printf("(%d:%d) ", pq->items[i].value, pq->items[i].priority);
    }
    printf("\n");
}

int main() {
    PriorityQueue pq;
    initPQ(&pq);

    enqueue(&pq, 10, 2);
    enqueue(&pq, 20, 5);
    enqueue(&pq, 30, 1);
    enqueue(&pq, 40, 3);

    display(&pq);  // (20:5) (40:3) (10:2) (30:1)

    printf("Dequeued: %d\n", dequeue(&pq));  // 20 (highest priority)
    printf("Peek: %d\n", peek(&pq));         // 40

    display(&pq);

    return 0;
}

Queue Applications

1. Breadth-First Search (BFS)

Graph Traversal:

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

#define V 5

void BFS(int graph[V][V], int start) {
    bool visited[V] = {false};
    int queue[V];
    int front = 0, rear = 0;

    visited[start] = true;
    queue[rear++] = start;

    printf("BFS traversal: ");

    while (front < rear) {
        int node = queue[front++];
        printf("%d ", node);

        for (int i = 0; i < V; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                visited[i] = true;
                queue[rear++] = i;
            }
        }
    }

    printf("\n");
}

int main() {
    int graph[V][V] = {
        {0, 1, 1, 0, 0},
        {1, 0, 0, 1, 1},
        {1, 0, 0, 0, 1},
        {0, 1, 0, 0, 0},
        {0, 1, 1, 0, 0}
    };

    BFS(graph, 0);

    return 0;
}

2. CPU Scheduling (FCFS)

typedef struct {
    int processID;
    int burstTime;
} Process;

void FCFS_Scheduling(Process processes[], int n) {
    int waitTime[n];
    int turnAroundTime[n];

    waitTime[0] = 0;

    for (int i = 1; i < n; i++) {
        waitTime[i] = processes[i - 1].burstTime + waitTime[i - 1];
    }

    for (int i = 0; i < n; i++) {
        turnAroundTime[i] = processes[i].burstTime + waitTime[i];
        printf("P%d: Wait=%d, TAT=%d\n",
               processes[i].processID, waitTime[i], turnAroundTime[i]);
    }
}

3. Level Order Tree Traversal

typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

void levelOrder(TreeNode* root) {
    if (root == NULL) return;

    TreeNode* queue[100];
    int front = 0, rear = 0;

    queue[rear++] = root;

    while (front < rear) {
        TreeNode* node = queue[front++];
        printf("%d ", node->data);

        if (node->left) queue[rear++] = node->left;
        if (node->right) queue[rear++] = node->right;
    }
}

Deque (Double-Ended Queue)

Operations at both ends.

C Implementation:

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

void enqueueFront(Deque* dq, int value) {
    if (dq->count == MAX_SIZE) {
        printf("Deque Full\n");
        return;
    }

    dq->front = (dq->front - 1 + MAX_SIZE) % MAX_SIZE;
    dq->items[dq->front] = value;
    dq->count++;
}

void enqueueRear(Deque* dq, int value) {
    if (dq->count == MAX_SIZE) {
        printf("Deque Full\n");
        return;
    }

    dq->rear = (dq->rear + 1) % MAX_SIZE;
    dq->items[dq->rear] = value;
    dq->count++;
}

int dequeueFront(Deque* dq) {
    if (dq->count == 0) {
        printf("Deque Empty\n");
        return -1;
    }

    int value = dq->items[dq->front];
    dq->front = (dq->front + 1) % MAX_SIZE;
    dq->count--;

    return value;
}

int dequeueRear(Deque* dq) {
    if (dq->count == 0) {
        printf("Deque Empty\n");
        return -1;
    }

    int value = dq->items[dq->rear];
    dq->rear = (dq->rear - 1 + MAX_SIZE) % MAX_SIZE;
    dq->count--;

    return value;
}

Complexity Summary

Common Mistakes

1. Not handling wrap-around - Forgetting modulo in circular queue
2. Memory leaks - Not freeing nodes in linked list queue
3. Wrong empty condition - Incorrect check for empty queue
4. Front/rear confusion - Mixing up front and rear pointers
5. Not updating count - Forgetting to track size
6. Overflow handling - Not checking full condition
7. Priority queue insertion - Wrong position for new element

Debugging Tips

1. Visualize queue state - Draw front, rear, elements
2. Check boundary conditions - Empty, full, single element
3. Test wrap-around - In circular queue
4. Verify FIFO order - First in should be first out
5. Print queue state - After each operation
6. Test with small capacity - Easy to trace
7. Use assertions - Verify invariants

Mini Exercises

1. Implement queue using two stacks
2. Reverse first k elements of queue
3. Generate binary numbers from 1 to n using queue
4. Implement LRU cache using queue
5. Find first non-repeating character in stream
6. Sliding window maximum using deque
7. Interleave first half with second half
8. Reverse a queue using recursion
9. Sort a queue without extra space
10. Implement circular tour (petrol pump problem)

Review Questions

1. Why is circular queue more efficient than simple queue?
2. When should you use a linked list queue vs array queue?
3. How does BFS use a queue?
4. What's the difference between a queue and a deque?
5. How would you implement a priority queue efficiently?

Reference Checklist

By the end of this chapter, you should be able to:

• Implement queue using arrays and linked lists
• Understand FIFO principle
• Implement circular queue
• Build priority queue
• Apply queues to BFS
• Solve scheduling problems
• Implement deque
• Analyze time and space complexity

Next Steps

Now that you understand queues, Chapter 8 explores hashing—a technique that enables near-constant-time search, insert, and delete operations. You'll learn hash functions, collision resolution, and applications like hash tables and hash maps.

---

Key Takeaway: Queues implement FIFO ordering with O(1) operations. Circular queues optimize space usage. Priority queues order by importance. Queues are essential for BFS, scheduling, and buffering systems.