Queue

Queue

Description: 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. Think of it like a line of people waiting to buy tickets: the person who arrives first is the one who gets served first.

Basic Operations

1. Enqueue: Add an element to the end of the queue.
2. Dequeue: Remove an element from the front of the queue.
3. Front/Peek: Get the element at the front of the queue without removing it.
4. IsEmpty: Check if the queue is empty.
5. Size: Get the number of elements in the queue.

Time Complexity

• Enqueue: $O(1)$ — adding an element is done at the end.
• Dequeue: $O(1)$ — removing an element from the front is direct.
• Front/Peek: $O(1)$ — accessing the front element is direct.
• IsEmpty: $O(1)$ — checking if the queue is empty is straightforward.
• Size: $O(1)$ — tracking the size can be done in constant time.

Implementations

Queues can be implemented using various data structures, such as:

1. Array: A fixed-size array can be used, but it may lead to wasted space if elements are dequeued.
2. Linked List: A linked list implementation allows for dynamic sizing but requires more memory overhead for pointers.
3. Circular Queue: A circular array can be used to efficiently utilize space without the need to shift elements.

Example Code (Using Linked List)

Here's a C++ implementation of a queue using a linked list:

#include <iostream>
using namespace std;

// Node structure for linked list
struct Node {
    int data;
    Node* next;
};

// Queue class
class Queue {
private:
    Node* front;
    Node* rear;
    int size;

public:
    Queue() : front(nullptr), rear(nullptr), size(0) {}

    // Enqueue operation
    void enqueue(int value) {
        Node* newNode = new Node{value, nullptr};
        if (rear) {
            rear->next = newNode; // Link the new node at the end of the queue
        }
        rear = newNode; // Move the rear pointer to the new node
        if (!front) {
            front = rear; // If the queue was empty, front is also the new node
        }
        size++;
    }

    // Dequeue operation
    int dequeue() {
        if (isEmpty()) {
            throw runtime_error("Queue is empty");
        }
        int value = front->data; // Get the data from the front node
        Node* temp = front; // Temporary variable to delete the front node
        front = front->next; // Move front pointer to the next node
        delete temp; // Delete the old front node
        size--;
        if (isEmpty()) {
            rear = nullptr; // If the queue is empty, update rear as well
        }
        return value;
    }

    // Peek at the front element
    int peek() {
        if (isEmpty()) {
            throw runtime_error("Queue is empty");
        }
        return front->data; // Return the front element's data
    }

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

    // Get the size of the queue
    int getSize() {
        return size;
    }

    ~Queue() {
        while (!isEmpty()) {
            dequeue(); // Dequeue all elements to free memory
        }
    }
};

int main() {
    Queue q;

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

    cout << "Front element: " << q.peek() << endl; // Should print 10
    cout << "Dequeued: " << q.dequeue() << endl; // Should remove 10
    cout << "New front element: " << q.peek() << endl; // Should print 20
    cout << "Size of queue: " << q.getSize() << endl; // Should print 2

    return 0;
}

Explanation of the Code

1. Node Structure: Defines a node that holds data and a pointer to the next node.
2. Queue Class: Contains pointers to the front and rear of the queue and tracks the size.
   • enqueue: Adds a new node to the end of the queue and updates pointers.
   • dequeue: Removes the front node, updates the front pointer, and returns the removed data.
   • peek: Returns the data at the front without removing it.
   • isEmpty: Checks if the queue is empty.
   • getSize: Returns the current number of elements in the queue.
3. Destructor: Ensures all nodes are freed when the queue is no longer in use.
4. Main Function: Demonstrates queue operations, enqueuing and dequeuing elements.

Conclusion

Queues are fundamental data structures used in various applications, such as scheduling tasks, handling requests, and managing resources in computer systems. Their FIFO nature makes them suitable for scenarios where order matters. Understanding how to implement and use queues is essential for effective algorithm design and problem-solving in programming.