Creation of Queue (Linked List Implementation)
class Queue {
private:
struct Node {
int data;
Node* next;
Node(int val) {
data = val;
next = nullptr;
}
};
Node* front;
Node* rear;
public:
// Constructor to initialize queue
Queue() {
front = nullptr;
rear = nullptr;
}
};
First, we will create a class named
Queue
.-
It will contain a
struct Node
with the following properties:-
int data
: Stores the value of the node. -
Node* next
: Points to the next node in the queue. -
Node(int val)
: Constructor to initializedata
withval
andnext
withnullptr
.
-
-
It will contain two properties:
-
Node* front
: Points to the front node of the queue. -
Node* rear
: Points to the rear node of the queue.
-
-
We will declare a constructor
Queue()
:- It will initialize both
front
andrear
pointers tonullptr
, indicating an empty queue.
- It will initialize both
Enqueue Operation
void enqueue(int item) {
Node* newNode = new Node(item);
if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
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 create a new node with the given
item
. - If the queue is empty (checked using
isEmpty()
), we will set bothfront
andrear
to point to the new node. - If the queue is not empty, we will link the current
rear
node'snext
to the new node and then updaterear
to point to the new node.
Dequeue Operation
void dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
Node* temp = front;
front = front->next;
if (front == nullptr) {
rear = nullptr;
}
delete temp;
}
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 store the
front
node in a temporary variabletemp
, then updatefront
to point to the next node in the queue. - If
front
becomesnullptr
after updating (indicating the queue is now empty), we will also setrear
tonullptr
. - Finally, we will delete the temporary
temp
node to free the memory.
isEmpty Operation
bool isEmpty() {
return front == nullptr;
}
We will define a method isEmpty()
:
- It will return
true
iffront
isnullptr
, indicating that the queue is empty. - Otherwise, it will return
false
.
Full Code Implementation
#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:
// Constructor to initialize queue
Queue() {
front = nullptr;
rear = nullptr;
}
// Destructor to free allocated memory
~Queue() {
while (!isEmpty()) {
dequeue();
}
}
// Enqueue operation
void enqueue(int item) {
Node* newNode = new Node(item);
if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
// Dequeue operation
void dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl;
return;
}
Node* temp = front;
front = front->next;
if (front == nullptr) {
rear = nullptr;
}
delete temp;
}
// Check if queue is empty
bool isEmpty() {
return front == nullptr;
}
};