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.

Bạn đang xem: Cài đặt queue bằng danh sách liên kết

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.

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.

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.

Xem thêm: Bảng Màu Son Maybelline Color Show Matte, Bảng Màu Son Maybelline Color Show

/* 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à pTailif(!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à pTailelse{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ênif(q.head){return q.head->data;} //Nếu trong hàng đợi rỗng thì return 0 và kết thúc hàmelse 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ệnhif(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ử đầuq.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 đợidelete 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 ****/#includeusing 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à pTailif(!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à pTailelse{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ênif(q.head){return q.head->data;} //Nếu trong hàng đợi rỗng thì return 0 và kết thúc hàmelse 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ệnhif(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ử đầuq.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 đợidelete 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> n;while(n--){cout> 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){coutdata next;}cout> lc; switch(lc){ case 0: break; case 1: nhap(q); break; case 2: cout
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é !!

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Tìm kiếm phần tử k trong danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu cách tìm kiếm một phần tử k trong…