Queue Operations in Data Structures

Queues are a linear data structure that operates on a First In First Out (FIFO) basis. It means the first element added to the queue is the first to be removed, just like in real-life scenarios where people line up for a service. In computer science, queues efficiently manage data in various scenarios, such as task scheduling, resource allocation, and buffering. The structure allows elements to be added to one end (the rear) and removed from the other end (the front).

What is a Queue?

A queue organizes elements in a linear sequence, where the element inserted first is the first to be removed, adhering to the FIFO principle. It is opposite to the stack's LIFO (Last In First Out) principle. The queue's primary operations involve adding elements to the rear and removing them from the front, making queues ideal for scenarios requiring ordered processing.

Queue as an Abstract Data Type (ADT)

As an ADT, a queue abstracts the data structure's implementation details, focusing on what operations are possible and how they behave. The essential operations for a queue ADT include:

• Initialize: Create an empty queue.
• isEmpty: Check if the queue is empty.
• isFull: Determine if the queue has reached its maximum capacity.
• Insert (Enqueue): Add an element to the rear of the queue, provided it's not full.
• Retrieve (Front/Peek): Access the first element without removing it, if the queue is not empty.
• Delete (Dequeue): Remove the first element from the queue, assuming it's not empty.

Implementing Queues Using Arrays

Using arrays to represent queues provides a straightforward implementation approach. The following C++ program demonstrates a basic queue operation using an array:

Example:

#include <iostream>
#include <string>
#include <limits> // Include this header for std::numeric_limits
using namespace std;

// Queue class definition for handling string data
class StringQueue {
    string* arr; // Array to store queue elements
    int capacity; // Maximum capacity of the queue
    int front; // Front index of the queue
    int rear; // Rear index of the queue
    int count; // Current size of the queue

public:
    // Constructor to initialize an empty queue with a given size
    StringQueue(int size) : capacity(size), front(0), rear(-1), count(0) {
        arr = new string[capacity];
    }

    // Function to add an element to the queue
    void enqueue(const string& element) {
        if (isFull()) {
            cout << "Queue overflow. Unable to insert new element.\n";
            return;
        }
        rear = (rear + 1) % capacity; // Circular increment
        arr[rear] = element;
        count++;
        cout << "Enqueued: " << element << endl;
    }

    // Function to remove the front element from the queue
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue underflow. No element to remove.\n";
            return;
        }
        cout << "Dequeued: " << arr[front] << endl;
        front = (front + 1) % capacity; // Circular increment
        count--;
    }

    // Function to check if the queue is empty
    bool isEmpty() const {
        return count == 0;
    }

    // Function to check if the queue is full
    bool isFull() const {
        return count == capacity;
    }

    // Function to display the elements of the queue
    void display() const {
        if (isEmpty()) {
            cout << "Queue is empty.\n";
            return;
        }
        cout << "Queue elements: ";
        for (int i = 0; i < count; i++) {
            cout << arr[(front + i) % capacity] << " ";
        }
        cout << endl;
    }

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

// Main function to demonstrate queue operations
int main() {
    int size, choice;
    string value;
    cout << "Enter the size of the queue: ";
    cin >> size;
    cin.ignore(numeric_limits<streamsize>::max(), '\n'); // Correctly includes <limits>

    StringQueue q(size); // Create a queue of the given size

    while (true) {
        cout << "\n1. Enqueue (Insert) 2. Dequeue (Remove) 3. Display 4. Exit\nSelect operation: ";
        cin >> choice;
        cin.ignore(numeric_limits<streamsize>::max(), '\n'); // Consume newline character

        switch (choice) {
            case 1: // Enqueue operation
                cout << "Enter a string to enqueue: ";
                getline(cin, value); // Use getline to read string with spaces
                q.enqueue(value);
                break;
            case 2: // Dequeue operation
                q.dequeue();
                break;
            case 3: // Display queue
                q.display();
                break;
            case 4: // Exit program
                cout << "Exiting program.\n";
                return 0;
            default:
                cout << "Invalid choice. Please enter a valid operation number.\n";
        }
    }

    return 0;
}

Output:

Enter the size of the queue: 3

1. Enqueue (Insert) 2. Dequeue (Remove) 3. Display 4. Exit
Select operation: 1
Enter a string to enqueue: hello
Enqueued: hello

1. Enqueue (Insert) 2. Dequeue (Remove) 3. Display 4. Exit
Select operation: 1
Enter a string to enqueue: world
Enqueued: world

1. Enqueue (Insert) 2. Dequeue (Remove) 3. Display 4. Exit
Select operation: 1
Enter a string to enqueue: 1234
Enqueued: 1234

1. Enqueue (Insert) 2. Dequeue (Remove) 3. Display 4. Exit
Select operation: 3
Queue elements: hello world 1234

The above program defines a StringQueue class to manage queue operations like insertion (enqueue), deletion (dequeue), and display, using a circular array for efficient space utilization.

Conclusion

Understanding and implementing queues are crucial for developers to manage data sequentially in various programming and computing scenarios. This tutorial covers the basics of queue operations and demonstrates a simple queue implementation using arrays in C++. Mastery of queues enhances one's ability to design efficient data management and processing algorithms in software development.