Queue data structure

A queue is a fundamental data structure that operates on the principle of “First In, First Out” (FIFO), where the first element added to the queue is the first one to be removed. This structure resembles a real-world queue like people waiting in line; the person who joins first is the first one to be served.

In C++, the Standard Template Library (STL) provides an efficient implementation of queues using the std::queue container adapter. This introduction covers the fundamental concepts of queues, their types, and how to implement them in C++.

Key Concepts of Queues

Basic Operations

Queues typically support the following operations:

1. Enqueue (Push): Add an element to the end of the queue.
2. Dequeue (Pop): Remove and return the element at the front.
3. Peek (Front/Back): View the element at the front or back without removing it.
4. Size: Returns the number of elements in the queue.
5. IsEmpty: Checks if the queue is empty.

Types of Queues

1. Simple Queue: A basic FIFO queue.
2. Circular Queue: A queue where the last position is connected to the first, forming a circle.
3. Priority Queue: Elements are arranged based on priority rather than arrival order.
4. Double-Ended Queue (Deque): Allows insertion and deletion from both ends.

Implementing Queues in C++

Using std::queue

The C++ STL provides a straightforward way to implement simple queues using the std::queue class template, which requires a container, typically std::deque or std::list.

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    // Enqueue elements
    q.push(1);
    q.push(2);
    q.push(3);

    // Check the front element
    std::cout << "Front element: " << q.front() << std::endl;

    // Dequeue elements
    q.pop();
    std::cout << "After pop, front element: " << q.front() << std::endl;

    return 0;
}

Using std::deque

The STL also provides the std::deque container, which supports fast insertions and deletions at both ends. It can be used directly to implement a double-ended queue.

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq;

    // Add to both ends
    dq.push_back(1);
    dq.push_back(2);
    dq.push_front(0);

    // Check both ends
    std::cout << "Front element: " << dq.front() << std::endl;
    std::cout << "Back element: " << dq.back() << std::endl;

    // Remove from both ends
    dq.pop_front();
    dq.pop_back();

    std::cout << "After popping, front element: " << dq.front() << std::endl;

    return 0;
}

Using std::priority_queue

Priority queues organize elements based on a specified comparison function. The default is a max-heap, but a min-heap can also be used.

#include <iostream>
#include <queue>
#include <vector>

int main() {
    // Priority queue with default comparator (max-heap)
    std::priority_queue<int> max_heap;

    max_heap.push(10);
    max_heap.push(20);
    max_heap.push(15);

    // Access top element
    std::cout << "Max-heap top element: " << max_heap.top() << std::endl;

    // Remove top element
    max_heap.pop();
    std::cout << "After pop, top element: " << max_heap.top() << std::endl;

    // Min-heap using custom comparator
    auto comp = [](int a, int b) { return a > b; };
    std::priority_queue<int, std::vector<int>, decltype(comp)> min_heap(comp);

    min_heap.push(10);
    min_heap.push(20);
    min_heap.push(15);

    std::cout << "Min-heap top element: " << min_heap.top() << std::endl;

    return 0;
}

Implementing Custom Queues

Custom queues can be implemented using linked lists or arrays to achieve specific behavior.

Array-Based Queue

An array-based implementation allows random access to elements but requires careful management of indexes.

#include <iostream>
#define MAX 1000

class ArrayQueue {
    int arr[MAX];
    int front, rear;

public:
    ArrayQueue() : front(-1), rear(-1) {}

    void enqueue(int x) {
        if (rear == MAX - 1) {
            std::cout << "Queue Overflow\n";
            return;
        }
        if (front == -1)
            front = 0;
        arr[++rear] = x;
    }

    void dequeue() {
        if (front == -1 || front > rear) {
            std::cout << "Queue Underflow\n";
            return;
        }
        front++;
    }

    int peek() {
        if (front == -1 || front > rear) {
            std::cout << "Queue is Empty\n";
            return -1;
        }
        return arr[front];
    }
};

int main() {
    ArrayQueue q;
    q.enqueue(10);
    q.enqueue(20);

    std::cout << "Front element: " << q.peek() << std::endl;
    q.dequeue();
    std::cout << "After dequeue, front element: " << q.peek() << std::endl;

    return 0;
}

Linked List-Based Queue

A linked list implementation avoids overflow and provides dynamic sizing.

#include <iostream>

class Node {
public:
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedListQueue {
    Node *front, *rear;

public:
    LinkedListQueue() : front(nullptr), rear(nullptr) {}

    void enqueue(int x) {
        Node* newNode = new Node(x);
        if (rear == nullptr) {
            front = rear = newNode;
            return;
        }
        rear->next = newNode;
        rear = newNode;
    }

    void dequeue() {
        if (front == nullptr) {
            std::cout << "Queue Underflow\n";
            return;
        }
        Node* temp = front;
        front = front->next;
        if (front == nullptr)
            rear = nullptr;
        delete temp;
    }

    int peek() {
        if (front == nullptr) {
            std::cout << "Queue is Empty\n";
            return -1;
        }
        return front->data;
    }
};

int main() {
    LinkedListQueue q;
    q.enqueue(10);
    q.enqueue(20);

    std::cout << "Front element: " << q.peek() << std::endl;
    q.dequeue();
    std::cout << "After dequeue, front element: " << q.peek() << std::endl;

    return 0;
}