NANDHOO.

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 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 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

OperationArray QueueCircular QueueLinked List QueuePriority Queue (Array)
EnqueueO(1)O(1)O(1)O(n)
DequeueO(1)O(1)O(1)O(1)
PeekO(1)O(1)O(1)O(1)
SpaceWastes spaceEfficientDynamicO(n)

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.

Recommended Bonus Resource
PreviousTake Quiz
Next Chapter