Queues

Introduction

A queue is a linear data structure that follows the First In First Out (FIFO) principle, meaning the first element added to the queue is the first one to be removed. Queues can be implemented using arrays, linked lists, or circular buffers.

Basic Operations

The main operations associated with a queue are:

• Enqueue: Adding an element to the rear of the queue.
• Dequeue: Removing the front element from the queue.
• Front: Accessing the front element of the queue without removing it.
• Rear: Accessing the rear element of the queue without removing it.
• IsEmpty: Checking if the queue is empty.

C++ Example

Here's an example of a simple queue implementation in C++ using a linked list:

#include <iostream>

class Node {
public:
    int data;
    Node* next;
};

class Queue {
public:
    Queue() : front(nullptr), rear(nullptr) {}

    void enqueue(int data) {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->next = nullptr;

        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
    }

    void dequeue() {
        if (!isEmpty()) {
            Node* temp = front;
            front = front->next;
            if (front == nullptr) {
                rear = nullptr;
            }
            delete temp;
        }
    }

    int getFront() {
        if (!isEmpty()) {
            return front->data;
        }
        return -1;
    }

    int getRear() {
        if (!isEmpty()) {
            return rear->data;
        }
        return -1;
    }

    bool isEmpty() {
        return front == nullptr;
    }

private:
    Node* front;
    Node* rear;
};

int main() {
    Queue queue;

    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);

    std::cout << "Front element is: " << queue.getFront() << std::endl;
    std::cout << "Rear element is: " << queue.getRear() << std::endl;

    queue.dequeue();
    std::cout << "Front element after dequeue is: " << queue.getFront() << std::endl;

    return 0;
}

In this example, the Node class represents a single node in the queue, and the Queue class implements the queue operations using a linked list. The enqueue() function adds a new node to the rear of the queue, the dequeue() function removes the front node from the queue, the getFront() function retrieves the front element, the getRear() function retrieves the rear element, and the isEmpty() function checks if the queue is empty.

Applications

Queues are used in various applications such as:

• Scheduling processes in operating systems.
• Managing resources, like printers, in a network.
• Implementing certain search algorithms like Breadth-First Search (BFS).
• Handling requests in a server, like a web server or database server.

See Also

• Stacks
• Linked Lists
• Arrays