Queues are a fundamental data structure in computer science that follow the First-In-First-Out (FIFO) principle. In this blog post, we will explore the implementation of Queues using arrays in C++.
Table of Contents
Introduction to Queues
A Queue is an abstract data type that represents a collection of elements with two main operations - Enqueue, which adds an element to the end of the queue, and Dequeue, which removes an element from the front of the queue.
Array Implementation of Queues
One way to implement a Queue is by using an array. In this approach, we use a fixed-size array to store the elements of the queue.
#define MAX_SIZE 100
class Queue {
private:
int arr[MAX_SIZE];
int front, rear;
public:
Queue() {
front = -1;
rear = -1;
}
// Operations on Queue
};
In the above code snippet, we define a class Queue that has a fixed-size array arr to store the elements and two integer variables front and rear to keep track of the front and rear of the queue.
Operations on Array-based Queues
Enqueue
The Enqueue operation adds an element to the end of the queue. It checks if the queue is already full before adding the element.
void enqueue(int element) {
if (isFull()) {
// Handle queue overflow
return;
}
if (isEmpty()) {
front = 0;
rear = 0;
} else {
rear = (rear + 1) % MAX_SIZE;
}
arr[rear] = element;
}
Dequeue
The Dequeue operation removes an element from the front of the queue. It checks if the queue is empty before removing the element.
void dequeue() {
if (isEmpty()) {
// Handle queue underflow
return;
}
if (front == rear) {
front = -1;
rear = -1;
} else {
front = (front + 1) % MAX_SIZE;
}
}
Front
The Front operation returns the element at the front of the queue without removing it. It checks if the queue is empty before accessing the front element.
int front() {
if (isEmpty()) {
// Handle empty queue
return -1;
}
return arr[front];
}
IsEmpty
The IsEmpty operation checks if the queue is empty by comparing the front and rear indices.
bool isEmpty() {
return (front == -1 && rear == -1);
}
IsFull
The IsFull operation checks if the queue is full. It is full when the rear is one position behind the front.
bool isFull() {
return ((rear + 1) % MAX_SIZE == front);
}
Conclusion
In this blog post, we have seen the implementation of Queues using arrays in C++. Queues have various real-world applications, including CPU scheduling, printer queues, and more. Understanding how to implement queues using arrays is essential for mastering data structures and algorithms.
Hashtags: #queues #datastructures