Queue
Creation of Queue (Array Implementation)
class Queue {
private:
int* arr;
int front;
int rear;
int capacity;
public:
// Constructor to initialize queue
Queue(int size) {
arr = new int[size];
capacity = size;
front = -1;
rear = -1;
}
};
First, we will create a class named
Queue
.-
It will contain four properties:
-
int* arr
: Points to the array that will store queue elements. -
int front
: Stores the index of the front element in the queue. -
int rear
: Stores the index of the rear element in the queue. -
int capacity
: Stores the maximum number of elements the queue can hold.
-
-
We will declare a constructor
Queue(int size)
:- It will take
size
as input. - We will dynamically allocate memory for the queue array with the given size and assign it to
arr
. - We will set the
capacity
to the given size. - We will set
front
andrear
to-1
, indicating an empty queue.
- It will take
Enqueue Operation
void enqueue(int value) {
if (isFull()) {
cout << "Queue is full. Cannot enqueue." << endl;
return;
}
rear++;
arr[rear] = value;
if (front == -1) {
front = 0;
}
}
We will define a method enqueue(int value)
:
- It will take an integer
value
as input, which is the value to be added to the queue. - We will check if the queue is full (using
isFull()
); if so, it will print "Queue is full. Cannot enqueue." and return. - Otherwise, it will increment the
rear
index and assign thevalue
to the queue at the updatedrear
index. - If the queue was empty (i.e.,
front
was-1
), it will setfront
to0
.
Dequeue Operation
void dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
front++;
if (front > rear) {
front = rear = -1; // Reset when the queue becomes empty
}
}
We will define a method dequeue()
:
- It will remove an element from the front of the queue.
- We will check if the queue is empty (using
isEmpty()
); if so, it will print "Queue is empty. Cannot dequeue." and return. - Otherwise, it will increment the
front
index. - If the
front
index exceeds therear
index after dequeuing, indicating the queue is now empty, it will reset bothfront
andrear
to-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.
Dequeue Operation (Improved)
void dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
// Remove the element from the front of the queue
for (int i = 0; i < rear; i++) {
arr[i] = arr[i + 1];
}
rear--;
// If the queue is empty after dequeuing, reset pointers
if (rear == -1) {
front = -1;
}
}
We will define a method dequeue()
:
- It will remove an element from the front of the queue.
- We will check if the queue is empty (using
isEmpty()
); if so, it will print "Queue is empty. Cannot dequeue." and return. - Otherwise, we will shift all elements in the array one position to the left to fill the gap left by the dequeued element.
- We will decrement the
rear
index. - If the queue becomes empty after dequeuing (i.e.,
rear
is-1
), it will resetfront
to-1
to indicate the queue is empty.
isFull Operation
bool isFull() {
return rear == capacity - 1;
}
We will define a method isFull()
:
- It will return a boolean value indicating whether the queue is full.
- It will return
true
ifrear
is equal tocapacity - 1
, indicating that the queue has reached its maximum capacity. - Otherwise, it will return
false
.
isEmpty Operation
bool isEmpty() {
return front == -1;
}
We will define a method isEmpty()
:
- It will return a boolean value indicating whether the queue is empty.
- It will return
true
iffront
is-1
, indicating that the queue is empty. - Otherwise, it will return
false
.
Full Code Implementation
#include <iostream>
using namespace std;
class Queue {
private:
int* arr;
int front;
int rear;
int capacity;
public:
// Constructor to initialize queue
Queue(int size) {
arr = new int[size];
capacity = size;
front = -1;
rear = -1;
}
// Destructor to free allocated memory
~Queue() {
delete[] arr;
}
// Enqueue operation
void enqueue(int value) {
if (isFull()) {
cout << "Queue is full. Cannot enqueue." << endl;
return;
}
rear++;
arr[rear] = value;
if (front == -1) {
front = 0;
}
}
// Dequeue operation (Improved)
void dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
// Remove the element from the front of the queue
for (int i = 0; i < rear; i++) {
arr[i] = arr[i + 1];
}
rear--;
// If the queue is empty after dequeuing, reset pointers
if (rear == -1) {
front = -1;
}
}
// Peek operation
int peek() {
if (isEmpty()) {
cout << "Queue is empty." << endl;
return -1;
}
return arr[front];
}
// Check if queue is empty
bool isEmpty() {
return front == -1;
}
// Check if queue is full
bool isFull() {
return rear == capacity - 1;
}
};
Circular Queue
Creation of Circular Queue (Array Implementation)
class CircularQueue {
private:
int* arr;
int front;
int rear;
int capacity;
int size;
public:
// Constructor to initialize queue
CircularQueue(int size) {
arr = new int[size];
capacity = size;
front = 0;
rear = -1;
this->size = 0;
}
};
First, we will create a class named
CircularQueue
.-
It will contain five properties:
-
int* arr
: Points to the array that will store queue elements. -
int front
: Stores the index of the front element in the queue. -
int rear
: Stores the index of the rear element in the queue. -
int capacity
: Stores the maximum number of elements the queue can hold. -
int size
: Keeps track of the current number of elements in the queue.
-
-
We will declare a constructor
CircularQueue(int size)
:- It will take
size
as input. - We will dynamically allocate memory for the queue array with the given size and assign it to
arr
. - We will set the
capacity
to the given size. - We will initialize
front
to0
,rear
to-1
, andsize
to0
, indicating an empty queue.
- It will take
Enqueue Operation
void enqueue(int item) {
if (isFull()) {
cout << "Queue is full. Cannot enqueue.\n";
return;
}
rear = (rear + 1) % capacity;
arr[rear] = item;
size++;
}
We will define a method enqueue(int item)
:
- It will take an integer
item
as input, which is the value to be added to the queue. - We will check if the queue is full (using
isFull()
); if so, it will print "Queue is full. Cannot enqueue." and return. - Otherwise, we will increment the
rear
index in a circular manner using modulo operation(rear + 1) % capacity
and assign theitem
to the queue at the updatedrear
index. - We will then increment the
size
.
Dequeue Operation
int dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue.\n";
return -1;
}
int item = arr[front];
front = (front + 1) % capacity;
size--;
return item;
}
We will define a method dequeue()
:
- It will remove an element from the front of the queue.
- We will check if the queue is empty (using
isEmpty()
); if so, it will print "Queue is empty. Cannot dequeue." and return-1
. - Otherwise, we will retrieve the element from the
front
index, increment thefront
index in a circular manner using modulo operation(front + 1) % capacity
, and decrement thesize
. - We will return the removed item.
isFull Operation
bool isFull() {
return size == capacity;
}
We will define a method isFull()
:
- It will return a boolean value indicating whether the queue is full.
- It will return
true
ifsize
is equal tocapacity
, indicating that the queue has reached its maximum capacity. - Otherwise, it will return
false
.
isEmpty Operation
bool isEmpty() {
return size == 0;
}
We will define a method isEmpty()
:
- It will return a boolean value indicating whether the queue is empty.
- It will return
true
ifsize
is0
, indicating that the queue is empty. - Otherwise, it will return
false
.
Full Code Implementation
#include <iostream>
using namespace std;
class CircularQueue {
private:
int* arr;
int front;
int rear;
int capacity;
int size;
public:
// Constructor to initialize queue
CircularQueue(int size) {
arr = new int[size];
capacity = size;
front = 0;
rear = -1;
this->size = 0;
}
// Destructor to free allocated memory
~CircularQueue() {
delete[] arr;
}
// Enqueue operation
void enqueue(int item) {
if (isFull()) {
cout << "Queue is full. Cannot enqueue.\n";
return;
}
rear = (rear + 1) % capacity;
arr[rear] = item;
size++;
}
// Dequeue operation
int dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue.\n";
return -1;
}
int item = arr[front];
front = (front + 1) % capacity;
size--;
return item;
}
// Check if queue is full
bool isFull() {
return size == capacity;
}
// Check if queue is empty
bool isEmpty() {
return size == 0;
}
};