Cài đặt hàng đợi Queue bằng danh sách liên kết - Hàng đợi Queue
Trong hướng dẫn này mình sẽ giới thiệu các bạn cách cài đặt hàng đợi Queue bằng danh sách liên kết. Đây là một trong hai cách hiệu quả nhất để cài đặt hàng đợi Queue. Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu cho Queue và thực hiện tạo các hàm cơ bản trên hàng đợi. Sau đó ...
Trong hướng dẫn này mình sẽ giới thiệu các bạn cách cài đặt hàng đợi Queue bằng danh sách liên kết. Đây là một trong hai cách hiệu quả nhất để cài đặt hàng đợi Queue.
Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu cho Queue và thực hiện tạo các hàm cơ bản trên hàng đợi. Sau đó sử dụng các hàm đã tạo viết một chương trình nhập xuất đơn giản trong C++.
1. Cấu trúc dữ liệu của hàng đợi Queue
Hàng đợi là một cấu trúc trừu tượng, vì vậy để làm việc với nó ta cần tạo cấu trúc dữ liệu cho nó. Trong hướng dẫn này mình sử dụng danh sách liên kết để tạo Queue vì vậy đầu tiên ta cần có cấu trúc của một Node trong danh sách liên kết.
/* tạo cấu trúc của Node trong danh sách liên kết */
struct Node{
Node *next;
int data;
};Tiếp đến là hai hàm khởi tạo rỗng cho Node và hàm tạo mới một Node, đây là những hàm mà chúng ta đã học ở các bài về danh sách liên kết
/* khởi tạo rỗng cho Node trong danh sách liên kết */
void Init( Queue &q ){
q.head = q.tail = NULL;
}
/* hàm tạo một Node mới */
Node *createNode( int x ){
Node *p = new Node;
if(!p) exit(1);
p->next = NULL;
p->data = x;
return p;
}Cuối cùng là tạo một cấu trúc của hàng đợi Queue bằng cách sử dụng Node để tạo, bao gồm hai con trỏ là head và tail để quản lý phần tử đầu và phần tử cuối.
/* tạo cấu trúc của hàng đợi Queue */
struct Queue{
Node *head, *tail;
};2. Các hàm cơ bản trong hàng đợi Queue
Trong phần này mình sẽ thực hiện tạo một số hàm cơ bản cần thiết trong hàng đợi Queue: Push(), Top(), Pop().
Hàm Push
Hàm Push() là hàm để thêm các phần tử vào đầu hàng đợi, đây là một hàm rất quan trọng vì nếu không có dữ liệu trong hàng đợi thì ta không thể thực hiện các thao tác khác.
Việc đầu tiên ta sẽ kiểm tra xem hàng đợi có rỗng hay không, nếu trong Queue không tồn tại phần tử nào thì phần tử được thêm vào chính là pHead và pTail. Ngược lại nếu trong Queue đã tồn tại phần tử thì ta cho pNext của pTail trỏ tới node p.
/* hàm thêm phần tử vào đầu trong hàng đợi Queue */
void Push(Queue &q, Node *p ){
//kiểm tra nếu hàng đợi rỗng thì phần tử thêm vào chính là pHead và pTail
if(!q.head) q.head = q.tail = p;
//Nếu trong danh sách đã tồn tại phần tử thì cho pNext của pTail trỏ tới node p
//khi đó node p chính là pTail
else{
q.tail->next = p;
q.tail = p;
}
}Hàm Top
Hàm Top() là hàm để lấy phần tử đầu tiên trong hàng đợi Queue nhưng không xóa nó khỏi Queue. Hay nói cách khác là nó chỉ hiển thị phần tử đầu tiên trong Queue.
Ta thực hiện kiểm tra nếu hàng đợi tồn tại phần tử thì return phần tử đó, ngược lại nếu trong hàng đợi rỗng thì return 0 và kết thúc hàm.
int Top(Queue q ){
//kiểm tra nếu hàng đợi tồn tại phần tử thì ta thực hiện return phần tử đầu tiên
if(q.head){
return q.head->data;
}
//Nếu trong hàng đợi rỗng thì return 0 và kết thúc hàm
else return 0;
}Hàm Pop
Hàm Pop() là hàm xóa phần tử đầu tiên trong hàng đợi, đây là một hàm cũng khá quan trọng vì trong một số trường hợp ta cần phải xóa phần tử khỏi Queue.
Việc đầu tiên ta sẽ kiểm tra xem trong Queue có tồn tại phần tử hay không, nếu có tồn tại phần tử thì thực hiện các bước sau:
- Tạo mới một Node p (là Node thay thế cho Node cần xóa).
- Trỏ con trỏ Next đến phần tử tiếp theo để có thể xóa phần tử đầu.
- Gán data cho p và return nó.
- Thực hiện xóa p khỏi hàng đợi.
/* hàm xóa phần tử đầu trong hàng đợi */
int Pop(Queue &q ){
//kiểm tra nếu hàng đợi tồn tại thì thực hiện các câu lệnh
if(q.head){
//tạo mới một Node p (là node thay thế cho node cần xóa)
Node *p = q.head;
//trỏ con trỏ Next đến phần tử tiếp theo để có thể xóa phần tử đầu
q.head = q.head->next;
//gán data cho p và return nó
return p->data;
//sau khi return thì thực hiện xóa nó khỏi hàng đợi
delete p;
}
return 0;// tuong duong queue rong
}3. Ví dụ về hàng đợi Queue
Trong ví dụ này mình sẽ sử dụng các hàm đã tạo ở trên để thêm một số phần tử và hàng đợi, sau đó tạo một menu với các thao tác như:
- Thêm phần tử vào Queue.
- Xuất các phần tử trong Queue.
- Lấy phần tử đầu tiên trong Queue.
- Xóa phần tử đầu tiên trong Queue.
Các bạn có thể tham khảo code của mình dưới đây, trong đó mình đã có chú thích rõ ràng.
Full code:
/**** Tạo hàng đợi Queue bằng danh sách liên kết đơn ****/
#include<iostream>
using namespace std;
/* tạo cấu trúc của Node trong danh sách liên kết */
struct Node{
Node *next;
int data;
};
/* tạo cấu trúc của hàng đợi Queue */
struct Queue{
Node *head, *tail;
};
/* khởi tạo rỗng cho Node trong danh sách liên kết */
void Init( Queue &q ){
q.head = q.tail = NULL;
}
/* hàm tạo một Node mới */
Node *createNode( int x ){
Node *p = new Node;
if(!p) exit(1);
p->next = NULL;
p->data = x;
return p;
}
/* hàm thêm phần tử vào đầu trong hàng đợi Queue */
void Push(Queue &q, Node *p ){
//kiểm tra nếu hàng đợi rỗng thì phần tử thêm vào chính là pHead và pTail
if(!q.head) q.head = q.tail = p;
//Nếu trong danh sách đã tồn tại phần tử thì cho pNext của pTail trỏ tới node p
//khi đó node p chính là pTail
else{
q.tail->next = p;
q.tail = p;
}
}
/* hàm lấy phần tử đầu trong hàng đợi, nhưng không xóa nó */
int Top(Queue q ){
//kiểm tra nếu hàng đợi tồn tại phần tử thì ta thực hiện return phần tử đầu tiên
if(q.head){
return q.head->data;
}
//Nếu trong hàng đợi rỗng thì return 0 và kết thúc hàm
else return 0;
}
/* hàm xóa phần tử đầu trong hàng đợi */
int Pop(Queue &q ){
//kiểm tra nếu hàng đợi tồn tại thì thực hiện các câu lệnh
if(q.head){
//tạo mới một Node p (là node thay thế cho node cần xóa)
Node *p = q.head;
//trỏ con trỏ Next đến phần tử tiếp theo để có thể xóa phần tử đầu
q.head = q.head->next;
//gán data cho p và return nó
return p->data;
//sau khi return thì thực hiện xóa nó khỏi hàng đợi
delete p;
}
return 0;// tuong duong queue rong
}
/* hàm nhập các phần tử vào hàng đợi */
void nhap(Queue &q ){
int n, x;
cout<<"Nhập số phần tử bạn muốn thêm vào trong Queue: ";
cin>> n;
while(n--){
cout<<"
Nhập phần tử trong hàng đợi: "; cin>> x;
Node *p = createNode(x);
Push(q,p);
}
}
/* hàm xuất các phần tử trong hàng đợi */
void xuat(Queue q ){
Node *p = q.head;
while(p){
cout<<p->data << " ";
p = p->next;
}
cout<< endl;
}
/* hàm menu để hiển thị menu và gọi các hàm đã tạo */
void menu(Queue q){
int lc;
do{
cout << "
============== Menu ==============";
cout << "
1. Nhập phần tử cho hàng đợi";
cout << "
2. Xuất phần tử trong hàng đợi";
cout << "
3. Hiển thị phần tử đầu tiên của hàng đợi";
cout << "
4. Xóa phần tử đầu tiên của hàng đợi";
cout << "
0. Thoát";
cout << "
============== End ==============";
cout<<"
Nhập lựa chọn bạn muốn chọn: ";
cin>> lc;
switch(lc){
case 0: break;
case 1:
nhap(q);
break;
case 2:
cout<<"Các phần tử trong hàng đợi Queue là: ";
xuat(q);
break;
case 3:
cout<<"Phần tử đầu tiên của hàng đợi là: "<<Top(q);
break;
case 4:
Pop(q);
cout<<"Xóa thành công, vui lòng nhập 2 để kiểm tra lại!!";
break;
default: cout<<"
Nhập sai, vui lòng nhập lại!";
}
} while(lc);
}
/* hàm main để hiển thị menu*/
int main(){
Queue q;
Init(q);
int lc;
menu(q);
cout<<"
---------------------------------
";
cout<<"Chương trình này được đang tại Zaidap.com.net";
}Kết quả: Mình đã sử dụng thao tác 1 và 2 trong menu, các bạn có thể kiểm tra các thao tác khác nhé.
4. Kết luận
Như vậy là chúng ta đã tìm hiểu xong cách cài đặt hằng đợi Queue bằng danh sách liên kết, cũng như tạo các hàm cơ bản trong Queue. Các bạn hãy luyện tập nó thật nhiều để có thể ghi nhớ nhớ thật lâu nhé. Ở bài tiếp theo mình sẽ hướng dẫn các bạn cách cài đặt Queue bằng mảng một chiều, hãy chú ý theo dõi nhé !!
