Understanding Queues in Data Structures

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that the element inserted first will be the one to be removed first, just like a real-world queue. Queues are commonly used in scenarios where we need to manage objects in an order, such as task scheduling, handling requests in a server, or implementing breadth-first search (BFS) in graph algorithms.

Queues are widely used in scenarios like scheduling processes in operating system, handling requests in web servers, and in breadth-first search algorithms.

Basic Operations on a Queue

A queue typically supports the following operations:

1. Enqueue: Add an element to the end of the queue.
2. Dequeue: Remove the element from the front of the queue.
3. Front/Peek: Get the front element of the queue.
4. Rear: Get the last element of the queue.
5. isEmpty: Check if the queue is empty.
6. isFull: Check if the queue is full (for a bounded queue).

Types of Queues

1. Simple Queue: Also known as a linear queue, where insertion is done at the rear and deletion is done at the front.
2. Circular Queue: A more efficient queue where the last position is connected back to the first position to make a circle. This helps in utilizing the space once elements are dequeued.
3. Priority Queue: Each element is assigned a priority, and elements are dequeued based on their priority rather than their position in the queue.
4. Deque (Double-Ended Queue): A queue where insertion and deletion can be performed at both the front and rear ends.

1️⃣ Array Implementation of Queue:

#include <iostream>
using namespace std;

#define SIZE 5

class Queue {
private:
    int items[SIZE];
    int front, rear;

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

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

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

    void enqueue(int element) {
        if (isFull()) {
            cout << "Queue is full!" << endl;
            return;
        }
        if (isEmpty()) {
            front = 0;
        }
        items[++rear] = element;
        cout << "Inserted " << element << endl;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        int element = items[front];
        if (front >= rear) { // Queue has only one element
            front = rear = -1;
        } else {
            front++;
        }
        cout << "Deleted " << element << endl;
        return element;
    }

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

int main() {
    Queue q;

    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);
    q.enqueue(5);
    q.enqueue(6); // Queue is full

    q.display();

    q.dequeue();
    q.display();

    return 0;
}

2️⃣ Linked List Implementation of Queue

#include <iostream>

// Node structure for the linked list
struct Node {
    int data;      // Data part of the node
    Node* next;    // Pointer to the next node

    // Constructor to initialize a node
    Node(int val) : data(val), next(nullptr) {}
};

// Queue class using a linked list
class Queue {
private:
    Node* front;   // Pointer to the front of the queue
    Node* rear;    // Pointer to the rear of the queue

public:
    // Constructor to initialize an empty queue
    Queue() : front(nullptr), rear(nullptr) {}

    // Function to add an element to the end of the queue
    void enqueue(int x) {
        Node* newNode = new Node(x);
        if (rear == nullptr) {
            // If queue is empty, both front and rear are the new node
            front = rear = newNode;
        } else {
            // Otherwise, add the new node at the end and update rear
            rear->next = newNode;
            rear = newNode;
        }
    }

    // Function to remove the element from the front of the queue
    int dequeue() {
        if (front == nullptr) {
            std::cerr << "Queue is empty, cannot dequeue!" << std::endl;
            return -1; // Indicate an error, or throw an exception
        }

        Node* temp = front;    // Temporary pointer to hold the front node
        int data = front->data; // Get the data of the front node
        front = front->next;    // Move front to the next node

        if (front == nullptr) {
            // If the queue is now empty, set rear to nullptr as well
            rear = nullptr;
        }

        delete temp; // Free the memory of the old front node
        return data; // Return the dequeued data
    }

    // Function to get the front element of the queue without removing it
    int peek() {
        if (front == nullptr) {
            std::cerr << "Queue is empty, cannot peek!" << std::endl;
            return -1; // Indicate an error, or throw an exception
        }
        return front->data;
    }

    // Function to check if the queue is empty
    bool isEmpty() {
        return front == nullptr;
    }

    // Destructor to clean up the memory allocated for the queue
    ~Queue() {
        while (front != nullptr) {
            Node* temp = front;
            front = front->next;
            delete temp;
        }
    }
};

// Example usage of the queue
int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    std::cout << "Front element is: " << q.peek() << std::endl; // Output: 10

    std::cout << "Dequeued: " << q.dequeue() << std::endl; // Output: 10
    std::cout << "Dequeued: " << q.dequeue() << std::endl; // Output: 20

    std::cout << "Front element is: " << q.peek() << std::endl; // Output: 30

    std::cout << "Is queue empty? " << (q.isEmpty() ? "Yes" : "No") << std::endl; // Output: No

    q.dequeue(); // Remove the last element
    std::cout << "Is queue empty? " << (q.isEmpty() ? "Yes" : "No") << std::endl; // Output: Yes

    return 0;
}

Queue in STL

In the C++ Standard Template Library (STL), several types of queues are available, each with unique characteristics and uses. These queues are designed to handle various scenarios in data structures and algorithms. Here are the main types of queues provided by STL:

1. std::queue: A standard FIFO (First In, First Out) queue.
2. std::priority_queue: A queue where elements are ordered by priority.
3. std::deque: A double-ended queue that allows insertion and deletion from both ends.

1️⃣ std:queue:

The C++ Standard Template Library (STL) provides a queue container that allows for easy implementation of a queue using a dynamic array. The queue in STL is a part of the <queue> header file and is designed to follow the First In, First Out (FIFO) principle.

#include <queue>

Queue Syntax:

queue<data_type> q;

Basic Operations of std::queue

The std::queue provides several member functions to perform standard queue operations:

1. push(): Adds an element to the back of the queue.
2. pop(): Removes the element from the front of the queue.
3. front(): Returns a reference to the front element of the queue.
4. back(): Returns a reference to the last element of the queue.
5. empty(): Checks if the queue is empty.
6. size(): Returns the number of elements in the queue.

Complete Example:

#include <iostream>
#include <queue>

int main() {
    // Create a queue of integers
    std::queue<int> q;

    // Enqueue elements
    q.push(10);
    q.push(20);
    q.push(30);

    // Display size of the queue
    std::cout << "Queue size: " << q.size() << std::endl;

    // Access the front and back elements
    std::cout << "Front element: " << q.front() << std::endl;
    std::cout << "Back element: " << q.back() << std::endl;

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

    // Check if queue is empty
    if (q.empty()) {
        std::cout << "Queue is empty." << std::endl;
    } else {
        std::cout << "Queue is not empty." << std::endl;
    }

    return 0;
}

Queue size: 3
Front element: 10
Back element: 30
Front element after pop: 20
Queue is not empty.

2️⃣ std::priority_queue:

std::priority_queue is a container adapter that provides a priority-based queue, where the largest element is always at the front. This queue does not follow the FIFO principle but instead orders elements by their priority.

By Default: It stores the data in decreasing order.

• Header File: <queue>
• Underlying Container: By default, std::priority_queue uses std::vector to store elements.

Basic Operations:

• push(x): Inserts an element x into the priority queue.
• pop(): Removes the element with the highest priority (the top element).
• top(): Returns a reference to the top element (the highest priority element).
• empty(): Checks if the priority queue is empty.
• size(): Returns the number of elements in the priority queue.

Example:

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    pq.push(5);
    pq.push(1);
    pq.push(10);
    pq.push(3);

    std::cout << "Top element: " << pq.top() << std::endl; // Should print 10

    pq.pop();
    std::cout << "Top element after pop: " << pq.top() << std::endl; // Should print 5

    return 0;
}

Top element: 10
Top element after pop: 5

Note: By default, std::priority_queue orders elements in descending order (max-heap). To create a min-heap, you can use a custom comparator or std::greater with std::priority_queue.

Min-Heap Example:

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

int main() {
    // Min-heap priority queue
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    minHeap.push(5);
    minHeap.push(1);
    minHeap.push(10);
    minHeap.push(3);

    std::cout << "Top element: " << minHeap.top() << std::endl; // Should print 1

    return 0;
}

Top element: 1

3️⃣ std::deque (Double-Ended Queue)

std::deque (double-ended queue) is a sequence container that allows fast insertion and deletion at both ends (front and back). Unlike std::queue and std::priority_queue, std::deque is not a container adapter but a full-fledged container class.

• Header File: <deque>
• Characteristics: Allows random access to elements, dynamic sizing, and provides constant-time insertions and deletions at both the front and the back.

Basic Operations:

• push_back(x): Inserts an element x at the back.
• push_front(x): Inserts an element x at the front.
• pop_back(): Removes the element at the back.
• pop_front(): Removes the element at the front.
• front(): Returns a reference to the first element.
• back(): Returns a reference to the last element.
• empty(): Checks if the deque is empty.
• size(): Returns the number of elements in the deque.
• operator[] or at(): Accesses elements by index.

Example:

#include <iostream>
#include <deque>

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

    d.push_back(2);
    d.push_front(1);
    d.push_back(3);
    d.push_front(0);

    std::cout << "Deque elements: ";
    for (int i : d) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    d.pop_back();
    d.pop_front();

    std::cout << "Deque elements after pop: ";
    for (int i : d) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

Deque elements: 0 1 2 3 
Deque elements after pop: 1 2