Queues

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Elements are added at the rear (enqueue) and removed from the front (dequeue). Think of it like a line of people waiting - the first person in line is the first to be served.

Queues are essential in computer science for task scheduling, breadth-first search, handling requests in web servers, and many other applications where fairness and order matter.

Queue Operations

The main operations on a queue are:

enqueue(): Add an element to the rear
dequeue(): Remove an element from the front
front(): View the front element without removing it
empty(): Check if the queue is empty
size(): Get the number of elements

Queue Implementation using Array

#include <iostream>
using namespace std;

class Queue {
private:
    int* arr;
    int capacity;
    int frontIndex;
    int rearIndex;
    int count;

public:
    Queue(int size) {
        arr = new int[size];
        capacity = size;
        frontIndex = 0;
        rearIndex = -1;
        count = 0;
    }
    
    ~Queue() {
        delete[] arr;
    }
    
    // Add element to rear
    void enqueue(int value) {
        if (count >= capacity) {
            cout << "Queue Overflow! Cannot enqueue " << value << endl;
            return;
        }
        rearIndex = (rearIndex + 1) % capacity;
        arr[rearIndex] = value;
        count++;
        cout << "Enqueued: " << value << endl;
    }
    
    // Remove element from front
    int dequeue() {
        if (count <= 0) {
            cout << "Queue Underflow! Cannot dequeue from empty queue" << endl;
            return -1;
        }
        int value = arr[frontIndex];
        frontIndex = (frontIndex + 1) % capacity;
        count--;
        return value;
    }
    
    // Get front element
    int front() {
        if (count <= 0) {
            cout << "Queue is empty" << endl;
            return -1;
        }
        return arr[frontIndex];
    }
    
    // Check if queue is empty
    bool empty() {
        return count == 0;
    }
    
    // Get size of queue
    int size() {
        return count;
    }
    
    // Display queue contents
    void display() {
        if (empty()) {
            cout << "Queue is empty" << endl;
            return;
        }
        
        cout << "Queue contents (front to rear): ";
        for (int i = 0; i < count; i++) {
            int index = (frontIndex + i) % capacity;
            cout << arr[index] << " ";
        }
        cout << endl;
    }
};

int main() {
    Queue queue(5);
    
    // Enqueue elements
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);
    
    queue.display();
    cout << "Front element: " << queue.front() << endl;
    cout << "Queue size: " << queue.size() << endl;
    
    // Dequeue elements
    cout << "Dequeued: " << queue.dequeue() << endl;
    cout << "Dequeued: " << queue.dequeue() << endl;
    
    queue.display();
    
    // Add more elements
    queue.enqueue(40);
    queue.enqueue(50);
    queue.display();
    
    return 0;
}

STL Queue

C++ Standard Template Library provides a queue container adapter:

Using STL Queue

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

int main() {
    queue<int> q;
    
    // Enqueue elements
    q.push(10);
    q.push(20);
    q.push(30);
    q.push(40);
    
    cout << "Queue size: " << q.size() << endl;
    cout << "Front element: " << q.front() << endl;
    cout << "Back element: " << q.back() << endl;
    
    // Display and dequeue all elements
    cout << "Queue contents: ";
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
    
    // Queue of strings
    queue<string> stringQueue;
    stringQueue.push("First");
    stringQueue.push("Second");
    stringQueue.push("Third");
    
    cout << "String queue: ";
    while (!stringQueue.empty()) {
        cout << stringQueue.front() << " ";
        stringQueue.pop();
    }
    cout << endl;
    
    return 0;
}

Priority Queue

A priority queue is a special type of queue where elements are served based on their priority rather than their order of arrival:

STL Priority Queue

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // Max heap (default) - largest element has highest priority
    priority_queue<int> maxHeap;
    
    maxHeap.push(30);
    maxHeap.push(10);
    maxHeap.push(50);
    maxHeap.push(20);
    
    cout << "Priority Queue (Max Heap): ";
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    cout << endl;
    
    // Min heap - smallest element has highest priority
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    minHeap.push(30);
    minHeap.push(10);
    minHeap.push(50);
    minHeap.push(20);
    
    cout << "Priority Queue (Min Heap): ";
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl;
    
    // Priority queue with custom priority
    struct Task {
        string name;
        int priority;
        
        Task(string n, int p) : name(n), priority(p) {}
        
        bool operator<(const Task& other) const {
            return priority < other.priority; // Higher priority value = higher priority
        }
    };
    
    priority_queue<Task> taskQueue;
    taskQueue.push(Task("Low Priority Task", 1));
    taskQueue.push(Task("High Priority Task", 5));
    taskQueue.push(Task("Medium Priority Task", 3));
    
    cout << "Task Priority Queue:" << endl;
    while (!taskQueue.empty()) {
        Task task = taskQueue.top();
        cout << task.name << " (Priority: " << task.priority << ")" << endl;
        taskQueue.pop();
    }
    
    return 0;
}

Circular Queue

A circular queue efficiently uses memory by treating the array as circular, connecting the end back to the beginning:

Circular Queue Implementation

#include <iostream>
using namespace std;

class CircularQueue {
private:
    int* arr;
    int capacity;
    int front;
    int rear;
    int count;

public:
    CircularQueue(int size) {
        arr = new int[size];
        capacity = size;
        front = 0;
        rear = -1;
        count = 0;
    }
    
    ~CircularQueue() {
        delete[] arr;
    }
    
    bool enqueue(int value) {
        if (isFull()) {
            cout << "Queue is full! Cannot enqueue " << value << endl;
            return false;
        }
        
        rear = (rear + 1) % capacity;
        arr[rear] = value;
        count++;
        return true;
    }
    
    int dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty! Cannot dequeue" << endl;
            return -1;
        }
        
        int value = arr[front];
        front = (front + 1) % capacity;
        count--;
        return value;
    }
    
    int getFront() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        return arr[front];
    }
    
    bool isEmpty() {
        return count == 0;
    }
    
    bool isFull() {
        return count == capacity;
    }
    
    int size() {
        return count;
    }
    
    void display() {
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return;
        }
        
        cout << "Queue: ";
        for (int i = 0; i < count; i++) {
            int index = (front + i) % capacity;
            cout << arr[index] << " ";
        }
        cout << endl;
    }
};

int main() {
    CircularQueue cq(5);
    
    // Fill the queue
    for (int i = 1; i <= 5; i++) {
        cq.enqueue(i * 10);
    }
    cq.display();
    
    // Try to add one more (should fail)
    cq.enqueue(60);
    
    // Remove some elements
    cout << "Dequeued: " << cq.dequeue() << endl;
    cout << "Dequeued: " << cq.dequeue() << endl;
    cq.display();
    
    // Add new elements (reusing space)
    cq.enqueue(60);
    cq.enqueue(70);
    cq.display();
    
    return 0;
}