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 Nodewith 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 initializedatawithvalandnextwithnullptr.
-
-
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
frontandrearpointers 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
itemas 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 bothfrontandrearto point to the new node. - If the queue is not empty, we will link the current
rearnode'snextto the new node and then updaterearto 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
frontnode in a temporary variabletemp, then updatefrontto point to the next node in the queue. - If
frontbecomesnullptrafter updating (indicating the queue is now empty), we will also setreartonullptr. - Finally, we will delete the temporary
tempnode to free the memory.
isEmpty Operation
bool isEmpty() {
return front == nullptr;
}
We will define a method isEmpty():
- It will return
trueiffrontisnullptr, 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;
}
};
Top comments (0)