Disclaimer
The solution of question or notes are written by either student or taken from some publications , so it is the responsibility of viewer to check whether answers are correct or incorrect.
fig: 1 queue in Linear Data structure
A queue is a fundamental data structure in computer science that follows the First-In-First-Out (FIFO) principle. It is an abstract data type with two primary operations: enqueue and dequeue.
Enqueue: It adds an element to the back of the queue. The new element becomes the last item in the queue.
Dequeue: It removes the element at the front of the queue, i.e., the oldest item that was enqueued.
The queue operates on a principle similar to waiting in line at a ticket counter or a queue of people. The first person to arrive is the first person to be served, and new arrivals join the back of the line.
A queue can be implemented using various data structures, such as arrays, linked lists, or other dynamic structures. The choice of implementation depends on factors like the expected size of the queue and the efficiency required for enqueue and dequeue operations.
#include <iostream>
template<typename T>
class Queue {
private:
struct Node {
T data;
Node* next;
Node(const T& item) : data(item), next(nullptr) {}
};
Node* front;
Node* rear;
public:
Queue() : front(nullptr), rear(nullptr) {}
~Queue() {
while (!isEmpty()) {
dequeue();
}
}
void enqueue(const T& item) {
Node* newNode = new Node(item);
if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
void dequeue() {
if (isEmpty()) {
std::cout << "Queue is empty. Unable to dequeue." << std::endl;
} else {
Node* temp = front;
front = front->next;
delete temp;
if (front == nullptr) {
rear = nullptr;
}
}
}
T getFront() const {
if (isEmpty()) {
std::cout << "Queue is empty. No front element." << std::endl;
exit(1);
}
return front->data;
}
bool isEmpty() const {
return front == nullptr;
}
};
int main() {
Queue<int> queue;
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
std::cout << "Front: " << queue.getFront() << std::endl;
queue.dequeue();
queue.dequeue();
std::cout << "Front: " << queue.getFront() << std::endl;
return 0;
}
In this example, the queue is implemented using a linked list. The Queue class has a nested Node struct that represents each element in the queue. The front and rear pointers keep track of the first and last nodes in the queue, respectively.
The enqueue function adds a new element to the end of the queue by creating a new node and updating the rear pointer.
The dequeue function removes the element at the front of the queue by updating the front pointer and deleting the old front node.
The getFront function returns the data of the front element without removing it.
The isEmpty function checks if the queue is empty.
In the main function, we create a Queue<int> object, enqueue three elements, and then dequeue two elements. Finally, we print the front element of the queue.
Comments