Topic 5

Queue

FIFO — First In, First Out

A queue is like a line at a counter. First person gets served first.

Operations: enqueue() — add at rear, dequeue() — remove from front

Simple Queue problem: Spaces before front are wasted after dequeue.
Solution: Circular Queue — uses % size to wrap around.

Simple Queue

front↓
10
20
rear↓
30

Circular — wrapped

front↓
30
40
50
rear↓
60

Simple vs Circular Queue

AspectSimple QueueCircular Queue
isFull()rear == size - 1(rear+1) % size == front
isEmpty()front == -1 || front > rearfront == -1
Enqueuearr[++rear]rear = (rear+1) % size
Dequeuefront++front = (front+1) % size
Space reuse❌ Wasted✅ Wraps around
Last elementfront > rear = emptyfront = rear = -1
🧠
% is the magic! (rear+1) % size wraps 4 back to 0 when size is 5.
🧠
Both start at front = rear = -1. First enqueue sets front = 0.
#include <iostream>
using namespace std;

class Queue {
private:
    int front, rear, size;
    int* arr;

public:
    Queue(int s) {
        front = rear = -1;
        size = s;
        arr = new int[size];
    }

    bool isFull() {
        return rear == size - 1;
    }

    bool isEmpty() {
        return front == -1 || front > rear;
    }

    // Enqueue
    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue is Full!" << endl;
            return;
        }
        if (front == -1) front = 0;
        arr[++rear] = value;
        cout << value << " enqueued to queue" << endl;
    }

    // Dequeue
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is Empty!" << endl;
            return;
        }
        cout << arr[front] << " dequeued from queue" << endl;
        front++;
    }

    // Display
    void display() {
        if (isEmpty()) {
            cout << "Queue is Empty!" << endl;
            return;
        }
        cout << "Queue elements: ";
        for (int i = front; i <= rear; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }

    ~Queue() {
        delete[] arr;
    }
};

int main() {
    Queue q(5);
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.display();        // 10 20 30

    q.dequeue();
    q.display();        // 20 30

    return 0;
}