Queues

Queues in C++

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed, just like people waiting in a line (the first person in the line is the first to be served). Queues are commonly used in scenarios like process scheduling, handling requests in servers, and managing resources.

Basic Operations of a Queue

A queue supports the following fundamental operations:

1. Enqueue: Adds an element to the rear of the queue.
2. Dequeue: Removes an element from the front of the queue.
3. Front: Returns the element at the front of the queue without removing it.
4. IsEmpty: Checks whether the queue is empty.
5. Size: Returns the number of elements currently in the queue.

Types of Queues

1. Simple Queue: A basic FIFO structure where elements are added at the rear and removed from the front.
2. Circular Queue: A more advanced version of the queue where the last position is connected back to the first position, forming a circle, allowing more efficient use of space.
3. Priority Queue: In a priority queue, elements are removed based on their priority rather than their arrival order.
4. Double-Ended Queue (Deque): A deque allows insertion and deletion from both ends (front and rear) of the queue.

Implementation of Queues in C++

Queues can be implemented using arrays, linked lists, or using the Standard Template Library (STL) queue class.

1. Manual Implementation of a Queue Using Array

In a simple array-based queue, you need to maintain two indices: front (indicating where to remove elements) and rear (indicating where to add elements).

Array-based Queue Implementation:

#include <iostream>
using namespace std;

class Queue {
private:
    int *arr;
    int front, rear, capacity;
    
public:
    // Constructor to initialize the queue
    Queue(int size) {
        arr = new int[size];
        capacity = size;
        front = 0;
        rear = -1;
    }

    // Enqueue operation
    void enqueue(int x) {
        if (rear == capacity - 1) {
            cout << "Queue Overflow\n";
            return;
        }
        arr[++rear] = x;
        cout << x << " enqueued to queue\n";
    }

    // Dequeue operation
    int dequeue() {
        if (front > rear) {
            cout << "Queue Underflow\n";
            return -1;
        }
        int data = arr[front++];
        return data;
    }

    // Front operation
    int frontElement() {
        if (front > rear) {
            cout << "Queue is empty\n";
            return -1;
        }
        return arr[front];
    }

    // Check if the queue is empty
    bool isEmpty() {
        return front > rear;
    }

    // Destructor to deallocate memory
    ~Queue() {
        delete[] arr;
    }
};

int main() {
    Queue q(5); // Create a queue of size 5

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    cout << "Front element: " << q.frontElement() << endl;  // Should print 10

    cout << "Dequeued element: " << q.dequeue() << endl;  // Should print 10

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

    return 0;
}

2. Queue Using Linked List

Alternatively, a queue can be implemented using a linked list where each node represents an element. The front pointer will point to the front element, and the rear pointer will point to the last element.

Linked List-based Queue Implementation:

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

class Queue {
private:
    Node* front;
    Node* rear;

public:
    // Constructor to initialize the queue
    Queue() {
        front = rear = nullptr;
    }

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

    // Dequeue operation
    int dequeue() {
        if (front == nullptr) {
            cout << "Queue Underflow\n";
            return -1;
        }
        Node* temp = front;
        int data = front->data;
        front = front->next;
        
        // If the queue becomes empty, make rear null as well
        if (front == nullptr) {
            rear = nullptr;
        }
        delete temp;
        return data;
    }

    // Front operation
    int frontElement() {
        if (front == nullptr) {
            cout << "Queue is empty\n";
            return -1;
        }
        return front->data;
    }

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

    // Destructor to free memory
    ~Queue() {
        while (front != nullptr) {
            dequeue();
        }
    }
};

int main() {
    Queue q;

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    cout << "Front element: " << q.frontElement() << endl;  // Should print 10

    cout << "Dequeued element: " << q.dequeue() << endl;  // Should print 10

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

    return 0;
}

3. Using C++ Standard Library (STL)

C++ provides a built-in queue container in the Standard Template Library (STL) that makes working with queues much easier. It follows the FIFO order and provides efficient access to the front and rear elements.

Using STL Queue:

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

int main() {
    queue<int> q;

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

    cout << "Front element: " << q.front() << endl;  // Should print 10

    q.pop();  // Dequeue operation
    cout << "Dequeued element: " << q.front() << endl;  // Should print 20

    cout << "Is queue empty? " << (q.empty() ? "Yes" : "No") << endl;  // Should print No

    return 0;
}

The STL queue provides:

• push(x): Adds element x to the rear of the queue.
• pop(): Removes the element from the front.
• front(): Returns the front element without removing it.
• back(): Returns the rear element.
• empty(): Checks if the queue is empty.
• size(): Returns the number of elements in the queue.

Applications of Queues

1. Process Scheduling: Queues are used in operating systems for task scheduling. For example, in a CPU scheduling algorithm, processes are managed in a queue where the process that enters first gets executed first.

2. Breadth-First Search (BFS): Queues are used in graph traversal algorithms like BFS to explore nodes level by level, ensuring that nodes are visited in the order they are discovered.

3. Print Queue: In printers, print jobs are managed using a queue. The job that enters the queue first is printed first.

4. Event Handling: In event-driven systems, queues are used to store and handle incoming events in the order they are received.

5. Data Buffering: Queues are used in networking and multimedia systems for buffering data packets and streaming data to ensure smooth delivery and processing.

Time Complexity of Queue Operations

For both array-based and linked list-based queues:

• Enqueue: O(1) (constant time for adding an element).
• Dequeue: O(1) (constant time for removing an element).
• Front: O(1) (constant time for accessing the front element).
• IsEmpty: O(1) (constant time for checking if the queue is empty).
• Size: O(1) (if implemented with a counter).

Advantages and Disadvantages

• Advantages:

  • Simple to implement.
  • Efficient access to both ends (front and rear).
  • Suitable for applications that require FIFO behavior.

• Disadvantages:

  • In an array-based implementation, the size is fixed, so memory can be wasted if the queue isn’t fully used, or overflow can occur if the queue becomes too full.
  • Linked list implementations can incur overhead due to pointer management.

Conclusion

Queues are an essential data structure in computer science that follow the FIFO principle. They are widely used in various applications, including process scheduling, BFS, and event handling. C++ provides several ways to implement queues, from manual implementations using arrays and linked lists to using the powerful STL queue class. Understanding how queues work and their practical applications will help you solve