Hàng đợi là một cấu trúc dữ liệu trừu tượng chứa một tập hợp các phần tử. Hàng đợi thực hiện cơ chế FIFO tức là phần tử được chèn vào trước cũng sẽ bị xóa trước. Nói cách khác, phần tử ít được thêm gần đây nhất sẽ bị xóa đầu tiên trong hàng đợi.
Một chương trình thực hiện hàng đợi bằng cách sử dụng danh sách liên kết được đưa ra như sau -
Ví dụ
#include <iostream>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node* front = NULL;
struct node* rear = NULL;
struct node* temp;
void Insert() {
int val;
cout<<"Insert the element in queue : "<<endl;
cin>>val;
if (rear == NULL) {
rear = (struct node *)malloc(sizeof(struct node));
rear->next = NULL;
rear->data = val;
front = rear;
} else {
temp=(struct node *)malloc(sizeof(struct node));
rear->next = temp;
temp->data = val;
temp->next = NULL;
rear = temp;
}
}
void Delete() {
temp = front;
if (front == NULL) {
cout<<"Underflow"<<endl;
return;
}
else
if (temp->next != NULL) {
temp = temp->next;
cout<<"Element deleted from queue is : "<<front->data<<endl;
free(front);
front = temp;
} else {
cout<<"Element deleted from queue is : "<<front->data<<endl;
free(front);
front = NULL;
rear = NULL;
}
}
void Display() {
temp = front;
if ((front == NULL) && (rear == NULL)) {
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are: ";
while (temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
}
int main() {
int ch;
cout<<"1) Insert element to queue"<<endl;
cout<<"2) Delete element from queue"<<endl;
cout<<"3) Display all the elements of queue"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter your choice : "<<endl;
cin>>ch;
switch (ch) {
case 1: Insert();
break;
case 2: Delete();
break;
case 3: Display();
break;
case 4: cout<<"Exit"<<endl;
break;
default: cout<<"Invalid choice"<<endl;
}
} while(ch!=4);
return 0;
} Đầu ra
Kết quả của chương trình trên như sau
1) Insert element to queue 2) Delete element from queue 3) Display all the elements of queue 4) Exit Enter your choice : 1 Insert the element in queue : 4 Enter your choice : 1 Insert the element in queue : 3 Enter your choice : 1 Insert the element in queue : 5 Enter your choice : 2 Element deleted from queue is : 4 Enter your choice : 3 Queue elements are : 3 5 Enter your choice : 7 Invalid choice Enter your choice : 4 Exit
Trong chương trình trên, hàm Insert () chèn một phần tử vào hàng đợi. Nếu phía sau là NULL, thì hàng đợi trống và một phần tử duy nhất được chèn vào. Nếu không, một nút được chèn vào sau phần tử được yêu cầu và sau đó nút đó được đặt thành phía sau. Điều này được hiển thị bên dưới -
void Insert() {
int val;
cout<<"Insert the element in queue : "<<endl;
cin>>val;
if (rear == NULL) {
rear = (struct node *)malloc(sizeof(struct node));
rear->next = NULL;
rear->data = val;
front = rear;
} else {
temp=(struct node *)malloc(sizeof(struct node));
rear->next = temp;
temp->data = val;
temp->next = NULL;
rear = temp;
}
} Trong hàm Delete (), nếu không có phần tử nào trong hàng đợi thì đó là điều kiện dòng dưới. Nếu chỉ có một phần tử trong hàng đợi bị xóa và phía trước và phía sau được đặt thành NULL. Nếu không, phần tử phía trước sẽ bị xóa và phía trước trỏ đến phần tử tiếp theo. Điều này được hiển thị bên dưới -
void Delete() {
temp = front;
if (front == NULL) {
cout<<"Underflow"<<endl;
return;
} else
if (temp->next != NULL) {
temp = temp->next;
cout<<"Element deleted from queue is : "<<front->data<<endl;
free(front);
front = temp;
} else {
cout<<"Element deleted from queue is : "<<front->data<<endl;
free(front);
front = NULL;
rear = NULL;
}
} Trong hàm display (), nếu phía trước và phía sau là NULL thì hàng đợi trống. Nếu không, tất cả các phần tử hàng đợi được hiển thị bằng vòng lặp while với sự trợ giúp của biến tạm thời. Điều này được hiển thị bên dưới -
void Display() {
temp = front;
if ((front == NULL) && (rear == NULL)) {
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are: ";
while (temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
} Hàm main () cung cấp sự lựa chọn cho người dùng nếu họ muốn chèn, xóa hoặc hiển thị hàng đợi. Theo phản hồi của người dùng, chức năng thích hợp được gọi là sử dụng công tắc. Nếu người dùng nhập một phản hồi không hợp lệ, thì phản hồi đó sẽ được in. Đoạn mã cho điều này được cung cấp bên dưới -
int main() {
int ch;
cout<<"1) Insert element to queue"<<endl;
cout<<"2) Delete element from queue"<<endl;
cout<<"3) Display all the elements of queue"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter your choice : "<<endl;
cin>>ch;
switch (ch) {
case 1: Insert();
break;
case 2: Delete();
break;
case 3: Display();
break;
case 4: cout<<"Exit"<<endl;
break;
default: cout<<"Invalid choice"<<endl;
}
} while(ch!=4);
return 0;
}