Queues | Data Structures | Cplusplus Tutorial

Introduction

A queue is a linear data structure that follows the First In First Out (FIFO) principle. This means that the element added first will be removed first. Queues are used in various applications like scheduling, buffering, and many other scenarios where order needs to be preserved.

Basic Queue Operations

There are several fundamental operations associated with a queue:

Enqueue: Add an element to the end of the queue.
Dequeue: Remove an element from the front of the queue.
Front: Get the front element of the queue.
Rear: Get the last element of the queue.
IsEmpty: Check if the queue is empty.
Size: Get the number of elements in the queue.

Queue Implementation in C++

Below is an example of a simple queue implementation in C++ using the Standard Template Library (STL).

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> q;

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

    // Print front element
    cout << "Front element: " << q.front() << endl;

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

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

    // Print queue size
    cout << "Queue size: " << q.size() << endl;

    return 0;
}

Output:

Front element: 10
Front element after pop: 20
Queue is not empty
Queue size: 2

Applications of Queues

Queues are used in various applications, including:

CPU Scheduling: Managing processes in an operating system.
Disk Scheduling: Managing requests to access disk sectors.
Data Buffers: Temporary storage for data being transferred between two places.
Waiting Lines: Managing tasks in real-time systems.

Types of Queues

There are several variations of queues, each serving different purposes:

Simple Queue: Basic FIFO structure.
Circular Queue: Last position is connected back to the first position to make a circle.
Priority Queue: Elements are processed based on priority rather than arrival order.
Double-Ended Queue (Deque): Elements can be added or removed from both ends.

Circular Queue Implementation

A circular queue is a more efficient implementation where the end of the queue wraps around to the front. Below is an example of a circular queue in C++:

#include <iostream>

#define SIZE 5

using namespace std;

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

public:
    CircularQueue() {
        front = -1;
        rear = -1;
    }

    // Check if the queue is full
    bool isFull() {
        if ((front == 0 && rear == SIZE - 1) || (front == rear + 1)) {
            return true;
        }
        return false;
    }

    // Check if the queue is empty
    bool isEmpty() {
        if (front == -1) return true;
        return false;
    }

    // Add an element
    void enqueue(int element) {
        if (isFull()) {
            cout << "Queue is full" << endl;
        } else {
            if (front == -1) front = 0;
            rear = (rear + 1) % SIZE;
            items[rear] = element;
            cout << "Inserted " << element << endl;
        }
    }

    // Remove an element
    int dequeue() {
        int element;
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return (-1);
        } else {
            element = items[front];
            if (front == rear) {
                front = -1;
                rear = -1;
            } else {
                front = (front + 1) % SIZE;
            }
            return (element);
        }
    }

    // Display the queue
    void display() {
        int i;
        if (isEmpty()) {
            cout << "Empty Queue" << endl;
        } else {
            cout << "Front -> " << front << endl;
            cout << "Items -> ";
            for (i = front; i != rear; i = (i + 1) % SIZE)
                cout << items[i] << " ";
            cout << items[i];
            cout << endl << "Rear -> " << rear << endl;
        }
    }
};

int main() {
    CircularQueue q;

    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);
    q.enqueue(5);

    q.display();

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

    q.enqueue(6);
    q.display();

    return 0;
}