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_limitsusing namespace std;// Queue class definition for handling string dataclass 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 queuepublic: // 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 operationsint 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: 31. Enqueue (Insert) 2. Dequeue (Remove) 3. Display 4. ExitSelect operation: 1Enter a string to enqueue: helloEnqueued: hello1. Enqueue (Insert) 2. Dequeue (Remove) 3. Display 4. ExitSelect operation: 1Enter a string to enqueue: worldEnqueued: world1. Enqueue (Insert) 2. Dequeue (Remove) 3. Display 4. ExitSelect operation: 1Enter a string to enqueue: 1234Enqueued: 12341. Enqueue (Insert) 2. Dequeue (Remove) 3. Display 4. ExitSelect operation: 3Queue elements: hello world 1234The above program defines aStringQueue 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.
