Queues
Queues are a fundamental data structure in computer science that follow a specific order for insertion and deletion of elements, adhering to 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, akin to a line of people waiting for service where the person at the front is served first. Queues are widely used in various applications such as scheduling tasks, handling requests in web servers, and breadth-first search algorithms in graphs.
Basic Concepts of Queues
- Enqueue: This operation adds an element to the end of the queue. If the queue is full, an overflow condition is encountered.
- Dequeue: This operation removes an element from the front of the queue. If the queue is empty, an underflow condition is encountered.
- Front/Peek: This operation returns the front element of the queue without removing it. It allows us to inspect the element that will be dequeued next.
- IsEmpty: This operation checks whether the queue is empty. It returns true if there are no elements in the queue and false otherwise.
Characteristics of Queues
FIFO Structure:
Queues operate on a First-In-First-Out basis, meaning the first element added is the first to be removed. This ensures that elements are processed in the order they were added, which is crucial for tasks that require sequential processing.Linear Data Structure:
Queues are a linear data structure, where elements are arranged in a sequential manner. Each element in the queue is connected to its predecessor and successor, forming a linear sequence of elements.Dynamic Size:
The size of a queue can change dynamically with the addition and removal of elements. This flexibility allows queues to adapt to varying workloads, making them suitable for scenarios with fluctuating demands.Multiple Types:
There are several variations of queues tailored for specific needs, such as circular queues, double-ended queues (deques), and priority queues. Each type of queue offers unique features and advantages, expanding the range of applications where queues can be effectively utilized.
Understanding these characteristics and basic operations of queues provides a solid foundation for exploring more advanced implementations and applications of this essential data structure.
Implementing Queues
Implementing queues involves creating a data structure that supports the fundamental operations of enqueue (insertion) and dequeue (removal) while maintaining the FIFO order. There are various ways to implement queues, each with its own advantages and trade-offs. The two most common implementations are using arrays and linked lists. Understanding these implementations is crucial for applying queues effectively in different scenarios and optimizing performance.
Array-Based Implementation
In an array-based implementation, a fixed-size array is used to store the queue elements. This approach is straightforward but can lead to inefficiencies such as wasted space or the need for dynamic resizing.
- Static Array: A static array has a fixed size. Enqueue operations are straightforward until the array is full, leading to an overflow condition. Dequeue operations can cause elements to shift, which may be inefficient.
- Circular Array: A circular array improves efficiency by treating the array as a loop, so the end of the array wraps around to the beginning. This eliminates the need to shift elements after dequeue operations and makes better use of available space.
Linked List-Based Implementation
A linked list-based implementation uses nodes to store queue elements, with each node pointing to the next element in the sequence. This approach offers dynamic sizing and eliminates the need for shifting elements.
- Singly Linked List: In a singly linked list, each node contains data and a reference to the next node. The queue maintains pointers to the front and rear nodes for efficient enqueue and dequeue operations.
- Doubly Linked List: A doubly linked list, where each node has references to both the next and previous nodes, can be used to implement a double-ended queue (deque) efficiently. This allows for insertion and deletion at both ends of the queue.
By understanding and implementing these different types of queues, you can tailor the data structure to fit specific use cases, optimizing performance and functionality for various applications.
Queue Implementation Using Arrays in C++
Queue implementation using arrays in C++ is a straightforward and efficient way to manage elements in a First-In-First-Out (FIFO) manner. By using arrays, we can leverage their fast access times and simple structure to create a queue that supports basic operations like enqueue, dequeue, and peek.
Creation of the Queue
To create a queue using arrays in C++, we define a class that contains the basic attributes and methods required to manage the queue. Below is the initial part of the class definition, including the basic attributes and the constructor.
#include <iostream>
using namespace std;
class Queue {
private:
int front;
int rear;
int size;
int *arr;
public:
Queue(int s) {
front = -1;
rear = -1;
size = s;
arr = new int[size];
}
~Queue() {
delete[] arr;
}
};
Attributes Explanation
front: This integer variable keeps track of the front position of the queue. It indicates the position from where elements will be dequeued. Initially set to -1, indicating the queue is empty.
rear: This integer variable tracks the rear position of the queue. It indicates the position where new elements will be enqueued. Initially set to -1, indicating the queue is empty.
size: This integer variable defines the maximum size of the queue. It is set through the constructor when a queue object is created.
arr: This is a pointer to an array that will store the queue elements. The array is dynamically allocated based on the specified size.
Constructor Explanation
The constructor Queue(int s) initializes the queue with a specified size:
- front = -1: Initializes the front index to -1, indicating that the queue is currently empty.
- rear = -1: Initializes the rear index to -1, indicating that the queue is currently empty.
- size = s: Sets the size of the queue.
- arr = new int[size]: Allocates memory for the queue's array based on the given size.
This setup provides the basic framework for the queue, allowing us to build upon it with the necessary operations such as enqueue, dequeue, and peek. The constructor ensures that the queue is properly initialized with the specified size and is ready for use.
Operations on Queue (Array Implementation)
Queue operations in array implementation involve adding elements to the rear (enqueue) and removing elements from the front (dequeue). Additionally, we can check if the queue is empty and if it's full.
Enqueue Operation
The enqueue operation adds an element to the rear of the queue. In array implementation, this involves incrementing the rear pointer and assigning the element to the corresponding index in the array.
void enqueue(int value) {
if (rear == size - 1) {
cout << "Queue is full. Cannot enqueue." << endl;
return;
}
else {
rear++;
arr[rear] = value;
}
}
Time Complexity: O(1)
Dequeue Operation
The dequeue operation removes an element from the front of the queue. In array implementation, this involves incrementing the front pointer to remove the element at the front position.
void dequeue() {
if (front == rear) {
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
else {
front++;
}
}
Time Complexity: O(1)
Problem with the Dequeue Operation
The above dequeue implementation is simple and efficient, with a time complexity of O(1). However, it has a significant drawback: as the front pointer keeps incrementing with each dequeue operation, it moves towards the end of the array. Eventually, the front pointer reaches the end of the array, and no further enqueues can be performed, even if there is available space at the beginning of the array. This leads to inefficient use of the array space.
Solution: Shifting Elements
To solve this issue, we can shift the elements of the array to the left whenever a dequeue operation is performed. This way, the front pointer always points to the first valid element in the queue, and the rear pointer correctly reflects the position of the last valid element. Shifting elements ensures that we can reuse the space at the beginning of the array and maintain the efficient functionality of the queue.
Updated Dequeue Operation
Here is the updated dequeue function that includes shifting elements to the left:
void dequeue() {
if (front == rear) {
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
else {
cout << "Removing " << arr[front + 1] << endl;
for (int i = front + 1; i < rear; i++) {
arr[i] = arr[i + 1];
}
rear--;
}
}
Time Complexity: O(n)
The time complexity of the updated dequeue operation is O(n), where n is the number of elements in the queue. This is because, in the worst case, we may need to shift all elements to the left.
IsEmpty Operation
The isEmpty operation checks if the queue is empty by comparing the front and rear pointers.
bool isEmpty() {
return front == rear;
}
Time Complexity: O(1)
IsFull Operation
The isFull operation checks if the queue is full by comparing the rear pointer with the size of the array.
bool isFull() {
return rear == size - 1;
}
Time Complexity: O(1)
These operations provide the basic functionality to manage a queue using array implementation. Each operation has constant time complexity, ensuring efficient performance for typical queue operations.
Full Code Implementation of Queues Using Arrays
Implementing queues using arrays in C++ involves creating a class that encapsulates the necessary attributes and methods to manage the queue efficiently. The class will include operations such as enqueue, dequeue, isEmpty, and isFull.
Below is the complete implementation of the Queue class in C++, including all the required operations.
#include <iostream>
using namespace std;
class Queue {
private:
int front;
int rear;
int size;
int *arr;
public:
Queue(int s) {
size = s;
front = -1;
rear = -1;
arr = new int[size];
}
~Queue() {
delete[] arr;
}
void enqueue(int value) {
if (isFull()) {
cout << "Queue is full. Cannot enqueue." << endl;
return;
}
else {
rear++;
arr[rear] = value;
}
}
void dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
else {
cout << "Removing " << arr[front + 1] << endl;
for (int i = front + 1; i < rear; i++) {
arr[i] = arr[i + 1];
}
rear--;
}
}
bool isEmpty() {
return front == rear;
}
bool isFull() {
return rear == size - 1;
}
void display() {
if (isEmpty()) {
cout << "Queue is empty." << endl;
return;
}
cout << "Queue elements: ";
for (int i = front + 1; i <= rear; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
int main() {
Queue q(5); // Create a queue of size 5
q.enqueue(1); // Enqueue elements
q.enqueue(2);
q.enqueue(3);
q.enqueue(4);
q.enqueue(5);
q.display(); // Display queue elements
q.dequeue(); // Dequeue an element
q.display(); // Display queue elements after dequeue
return 0;
}
This complete code demonstrates the implementation of a queue using arrays in C++. It includes all the necessary operations such as enqueue, dequeue, isEmpty, and isFull. The main function demonstrates how to create a queue object, enqueue and dequeue elements, and display the queue contents.
Queue Implementation Using Linked List in C++
Queue implementation using a linked list in C++ offers flexibility and dynamic sizing, making it suitable for scenarios where the size of the queue may change dynamically. Linked list-based implementation eliminates the need for a fixed-size array and allows for efficient insertion and deletion of elements at both ends of the queue.
Creation of the Queue
To create a queue using a linked list in C++, we define a class that encapsulates the necessary attributes and methods required to manage the queue. Below is the initial part of the class definition, including the basic attributes and the constructor.
#include <iostream>
using namespace std;
class Queue {
private:
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
Node* front;
Node* rear;
public:
Queue() : front(nullptr), rear(nullptr) {}
~Queue() {
// Destructor code to deallocate memory
}
};
Attributes Explanation
front: This pointer points to the front node of the queue, indicating the position from where elements will be dequeued. Initially set to nullptr, indicating the queue is empty.
rear: This pointer points to the rear node of the queue, indicating the position where new elements will be enqueued. Initially set to nullptr, indicating the queue is empty.
Constructor Explanation
The constructor initializes the queue:
Queue(): Initializes the front and rear pointers to nullptr.
- front: Points to the front node of the queue. Initially set to nullptr to indicate an empty queue.
- rear: Points to the rear node of the queue. Initially set to nullptr to indicate an empty queue.
This setup provides the basic framework for the queue, allowing us to build upon it with the necessary operations such as enqueue, dequeue, and isEmpty. The constructor ensures that the queue is properly initialized with empty pointers and is ready for use.
Operations on Queues (Linked List Implementation)
Queue operations in linked list implementation involve adding elements to the rear (enqueue) and removing elements from the front (dequeue). Additionally, we can check if the queue is empty.
Enqueue Operation
The enqueue operation adds an element to the rear of the queue. In linked list implementation, this involves creating a new node and updating the rear pointer to point to this new node.
void enqueue(int value) {
Node* newNode = new Node(value);
if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
Time Complexity: O(1)
Dequeue Operation
The dequeue operation removes an element from the front of the queue. In linked list implementation, this involves updating the front pointer to point to the next node.
void dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
Node* temp = front;
front = front->next;
delete temp;
}
Time Complexity: O(1)
IsEmpty Operation
The isEmpty operation checks if the queue is empty by checking if the front pointer is nullptr.
bool isEmpty() {
return front == nullptr;
}
Time Complexity: O(1)
These operations provide the basic functionality to manage a queue using linked list implementation. Each operation has constant time complexity, ensuring efficient performance for typical queue operations.
Full Code Implementation of Queues Using Linked List
Queue implementation using a linked list in C++ provides flexibility and dynamic sizing, making it suitable for scenarios where the size of the queue may change dynamically. This implementation eliminates the need for a fixed-size array and allows for efficient insertion and deletion of elements.
Below is the complete implementation of the Queue class using linked lists in C++, including all the required operations.
#include <iostream>
using namespace std;
class Queue {
private:
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
Node* front;
Node* rear;
public:
Queue() : front(nullptr), rear(nullptr) {}
~Queue() {
while (!isEmpty()) {
dequeue();
}
}
void enqueue(int value) {
Node* newNode = new Node(value);
if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
void dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
Node* temp = front;
front = front->next;
delete temp;
}
bool isEmpty() {
return front == nullptr;
}
void display() {
if (isEmpty()) {
cout << "Queue is empty." << endl;
return;
}
cout << "Queue elements: ";
Node* current = front;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
};
int main() {
Queue q;
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.display();
q.dequeue();
q.display();
return 0;
}
This complete code demonstrates the implementation of a queue using linked lists in C++. It includes all the necessary operations such as enqueue, dequeue, isEmpty, and display. The main function demonstrates how to create a queue object, enqueue and dequeue elements, and display the queue contents.
Circular Queue Using Arrays
A circular queue is a data structure that extends the functionality of a regular queue by allowing efficient use of space and avoiding the need to shift elements when dequeuing. It achieves this by treating the underlying array as circular, so when the rear pointer reaches the end of the array, it wraps around to the beginning. This circular behavior enables efficient memory utilization and constant-time enqueue and dequeue operations.
Differences with Simple Queue in Array Implementation:
- In a simple queue, when the rear pointer reaches the end of the array, further enqueue operations are not possible even if there are empty spaces at the beginning of the array. However, in a circular queue, the rear pointer wraps around to the beginning to utilize any available empty spaces.
- Similarly, in a simple queue, when the front pointer reaches the end of the array, further dequeue operations are not possible even if there are elements at the beginning of the array. In contrast, in a circular queue, the front pointer wraps around to the beginning to access elements.
Full Code Implementation of Circular Queues Using Arrays
Implementing a circular queue using arrays in C++ allows for efficient memory utilization and constant-time enqueue and dequeue operations. Below is the complete implementation of the Queue class for a circular queue using arrays.
#include <iostream>
using namespace std;
class CircularQueue {
private:
int *arr;
int front;
int rear;
int capacity;
public:
CircularQueue(int size) {
capacity = size;
arr = new int[capacity];
front = -1;
rear = -1;
}
~CircularQueue() {
delete[] arr;
}
void enqueue(int value) {
if (isFull()) {
cout << "Queue is full. Cannot enqueue." << endl;
return;
}
if (isEmpty())
front = 0;
rear = (rear + 1) % capacity;
arr[rear] = value;
}
void dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
if (front == rear)
front = rear = -1;
else
front = (front + 1) % capacity;
}
bool isEmpty() {
return front == -1;
}
bool isFull() {
return (rear + 1) % capacity == front;
}
void display() {
if (isEmpty()) {
cout << "Queue is empty." << endl;
return;
}
cout << "Queue elements: ";
int i = front;
while (i != rear) {
cout << arr[i] << " ";
i = (i + 1) % capacity;
}
cout << arr[rear] << endl;
}
};
int main() {
CircularQueue cq(5); // Create a circular queue of size 5
cq.enqueue(1); // Enqueue elements
cq.enqueue(2);
cq.enqueue(3);
cq.enqueue(4);
cq.enqueue(5);
cq.display(); // Display queue elements
cq.dequeue(); // Dequeue an element
cq.display(); // Display queue elements after dequeue
return 0;
}
This complete code demonstrates the implementation of a circular queue using arrays in C++. It includes all the necessary operations such as enqueue, dequeue, isEmpty, and isFull. The main function demonstrates how to create a circular queue object, enqueue and dequeue elements, and display the queue contents.
Queue Implementation Using Doubly Linked List
A queue implemented using a doubly linked list offers efficient insertion and deletion operations at both ends of the queue. Each node in the linked list contains pointers to both the next and previous nodes, allowing for easy traversal and manipulation.
Full Code Implementation of Queue Using Doubly Linked List
Implementing a queue using a doubly linked list in C++ provides flexibility and efficient operations. Below is the complete implementation of the Queue class for a doubly linked list-based queue.
#include <iostream>
using namespace std;
class Queue {
private:
struct Node {
int data;
Node* next;
Node* prev;
Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};
Node* front;
Node* rear;
public:
Queue() : front(nullptr), rear(nullptr) {}
~Queue() {
while (!isEmpty()) {
dequeue();
}
}
void enqueue(int value) {
Node* newNode = new Node(value);
if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode;
newNode->prev = rear;
rear = newNode;
}
}
void dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
Node* temp = front;
if (front == rear) {
front = rear = nullptr;
} else {
front = front->next;
front->prev = nullptr;
}
delete temp;
}
bool isEmpty() {
return front == nullptr;
}
void display() {
if (isEmpty()) {
cout << "Queue is empty." << endl;
return;
}
cout << "Queue elements: ";
Node* current = front;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
};
int main() {
Queue q;
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.display();
q.dequeue();
q.display();
return 0;
}
This complete code demonstrates the implementation of a queue using a doubly linked list in C++. It includes all the necessary operations such as enqueue, dequeue, isEmpty, and display. The main function demonstrates how to create a queue object, enqueue and dequeue elements, and display the queue contents.
Deque (Doubly Ended Queue)
A Deque, short for "Double-ended Queue," is an abstract data type that allows insertion and deletion of elements from both ends (front and rear). It combines the properties of both stacks and queues, providing more flexibility for adding and removing elements.
Key Features of Deque:
- Insertion/Deletion at Both Ends: Elements can be added or removed from both the front and the rear of the deque.
- Dynamic Size: The size of the deque can grow or shrink dynamically as elements are added or removed.
- Bidirectional Traversal: Allows traversal from both ends, making it useful for certain algorithms.
Full Code Implementation of Deque Using Doubly Linked List
Below is the implementation of a Deque using a doubly linked list in C++:
#include <iostream>
using namespace std;
class Deque {
private:
struct Node {
int data;
Node* next;
Node* prev;
Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};
Node* front;
Node* rear;
public:
Deque() : front(nullptr), rear(nullptr) {}
~Deque() {
while (!isEmpty()) {
removeFront();
}
}
// Insert at the front
void insertFront(int value) {
Node* newNode = new Node(value);
if (isEmpty()) {
front = rear = newNode;
} else {
newNode->next = front;
front->prev = newNode;
front = newNode;
}
}
// Insert at the rear
void insertRear(int value) {
Node* newNode = new Node(value);
if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode;
newNode->prev = rear;
rear = newNode;
}
}
// Remove from the front
void removeFront() {
if (isEmpty()) {
cout << "Deque is empty. Cannot remove from front." << endl;
return;
}
Node* temp = front;
if (front == rear) {
front = rear = nullptr;
} else {
front = front->next;
front->prev = nullptr;
}
delete temp;
}
// Remove from the rear
void removeRear() {
if (isEmpty()) {
cout << "Deque is empty. Cannot remove from rear." << endl;
return;
}
Node* temp = rear;
if (front == rear) {
front = rear = nullptr;
} else {
rear = rear->prev;
rear->next = nullptr;
}
delete temp;
}
// Check if the deque is empty
bool isEmpty() {
return front == nullptr;
}
// Display the deque from front to rear
void display() {
if (isEmpty()) {
cout << "Deque is empty." << endl;
return;
}
Node* temp = front;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
int main() {
Deque dq;
dq.insertFront(10);
dq.insertRear(20);
dq.insertFront(5);
dq.insertRear(25);
cout << "Deque after insertions: ";
dq.display();
dq.removeFront();
cout << "Deque after removing from front: ";
dq.display();
dq.removeRear();
cout << "Deque after removing from rear: ";
dq.display();
return 0;
}
This implementation ensures that the Deque provides efficient operations for insertion and removal from both ends, leveraging the properties of a doubly linked list.
Priority Queue Using Linked List
A priority queue using a linked list is an implementation where each element is associated with a priority and elements are dequeued in order of their priority. In a linked list implementation, elements are inserted in such a way that the list remains sorted based on priority.
Key Features of Priority Queue with Linked List:
- Ordered Insertion: Elements are inserted in the correct position to maintain the order based on priority.
- Dynamic Size: The size of the priority queue can grow or shrink dynamically as elements are added or removed.
- Efficient Deletion: Deleting the highest-priority element (at the front) is efficient.
Full Code Implementation of Priority Queue Using Linked List
Below is the implementation of a priority queue using a singly linked list in C++:
#include <iostream>
using namespace std;
class PriorityQueue {
private:
struct Node {
int data;
int priority;
Node* next;
Node(int val, int pri) : data(val), priority(pri), next(nullptr) {}
};
Node* front;
public:
PriorityQueue() : front(nullptr) {}
~PriorityQueue() {
while (!isEmpty()) {
dequeue();
}
}
// Insert with priority
void enqueue(int value, int priority) {
Node* newNode = new Node(value, priority);
if (isEmpty() || front->priority > priority) {
newNode->next = front;
front = newNode;
} else {
Node* temp = front;
while (temp->next != nullptr && temp->next->priority <= priority) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
}
// Remove the highest priority element
int dequeue() {
if (isEmpty()) {
cout << "Priority Queue is empty. Cannot dequeue." << endl;
return -1; // or throw an exception
}
Node* temp = front;
int value = temp->data;
front = front->next;
delete temp;
return value;
}
// Peek at the highest priority element
int peek() {
if (isEmpty()) {
cout << "Priority Queue is empty." << endl;
return -1;
}
return front->data;
}
// Check if the priority queue is empty
bool isEmpty() {
return front == nullptr;
}
// Display the priority queue
void display() {
if (isEmpty()) {
cout << "Priority Queue is empty." << endl;
return;
}
Node* temp = front;
while (temp != nullptr) {
cout << "(" << temp->data << ", " << temp->priority << ") ";
temp = temp->next;
}
cout << endl;
}
};
int main() {
PriorityQueue pq;
pq.enqueue(10, 2);
pq.enqueue(20, 1);
pq.enqueue(30, 3);
pq.enqueue(15, 1);
cout << "Priority Queue: ";
pq.display();
cout << "Dequeued element: " << pq.dequeue() << endl;
cout << "Priority Queue after dequeue: ";
pq.display();
cout << "Peek element: " << pq.peek() << endl;
return 0;
}
This implementation ensures that the priority queue maintains the correct order of elements based on their priority, providing efficient insertion and removal operations. The use of a linked list allows the priority queue to dynamically grow and shrink as elements are added or removed.
Top comments (0)