Queues

Data Structures and Algorithms (DSA) in C++: Queues

Queues are linear data structures that follow the First In, First Out (FIFO) principle, meaning that the element inserted first is the one that is removed first. They are commonly used to implement scheduling algorithms, breadth-first search (BFS) in graphs, and more. Here's an in-depth look into queues in C++:

Overview of Queues

• FIFO Principle: The element added to the queue first is the one that is removed first.
• Operations: Queues typically support operations such as enqueue (add an element to the end of the queue) and dequeue (remove an element from the front of the queue).
• Applications: Used in scenarios where elements are processed in the order they arrive or are added.

Implementing a Queue in C++

Using Standard Library (std::queue)

C++ provides a built-in queue container in the <queue> header, which implements all necessary functionalities efficiently.

Example:

        #include 
          #include 
          
          int main() {
              std::queue q;
          
              // Enqueue elements
              q.push(10);
              q.push(20);
              q.push(30);
          
              // Dequeue elements and print them
              while (!q.empty()) {
                  std::cout << q.front() << " ";
                  q.pop();
              }
              std::cout << std::endl;
          
              return 0;
          }
      

Implementing Queue from Scratch

If you want to understand how queues work internally, here’s a basic implementation using a linked list:

        #include 

          // Node structure for queue
          struct Node {
              int data;
              Node* next;
          
              Node(int val) : data(val), next(nullptr) {}
          };
          
          // Queue class
          class Queue {
          private:
              Node* front;
              Node* rear;
          
          public:
              Queue() : front(nullptr), rear(nullptr) {}
          
              // Check if queue is empty
              bool isEmpty() {
                  return front == nullptr;
              }
          
              // Enqueue operation: Add element to the rear of the queue
              void enqueue(int val) {
                  Node* newNode = new Node(val);
                  if (isEmpty()) {
                      front = rear = newNode;
                  } else {
                      rear->next = newNode;
                      rear = newNode;
                  }
              }
          
              // Dequeue operation: Remove element from the front of the queue
              void dequeue() {
                  if (isEmpty()) {
                      std::cout << "Queue is empty" << std::endl;
                      return;
                  }
          
                  Node* temp = front;
                  front = front->next;
                  delete temp;
          
                  if (front == nullptr) {
                      rear = nullptr;
                  }
              }
          
              // Display the queue elements
              void display() {
                  if (isEmpty()) {
                      std::cout << "Queue is empty" << std::endl;
                      return;
                  }
          
                  Node* curr = front;
                  while (curr != nullptr) {
                      std::cout << curr->data << " ";
                      curr = curr->next;
                  }
                  std::cout << std::endl;
              }
          
              // Destructor to free memory
              ~Queue() {
                  Node* curr = front;
                  while (curr != nullptr) {
                      Node* temp = curr;
                      curr = curr->next;
                      delete temp;
                  }
                  front = rear = nullptr;
              }
          };
          
          int main() {
              Queue q;
          
              q.enqueue(10);
              q.enqueue(20);
              q.enqueue(30);
          
              std::cout << "Queue elements: ";
              q.display(); // Output: Queue elements: 10 20 30
          
              q.dequeue();
              std::cout << "Queue elements after dequeue: ";
              q.display(); // Output: Queue elements after dequeue: 20 30
          
              return 0;
          }
      

Applications of Queues

• Operating Systems: Task scheduling (e.g., process scheduling).
• Networking: Data packet scheduling.
• Graph Algorithms: Breadth-First Search (BFS) uses queues to explore nodes level by level.
• Simulation: Simulating scenarios where events occur in the order they arrive.