Trong lý giải này mình đã giới thiệu các bạn cách cài đặt hàng ngóng Queue bằng danh sách liên kết. Đây là 1 trong nhì cách công dụng nhất để thiết lập hàng ngóng Queue.

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

Chúng ta sẽ thuộc nhau mày mò về bí quyết khởi tạo kết cấu dữ liệu mang đến Queue và tiến hành tạo các hàm cơ phiên bản trên hàng đợi. Tiếp nối sử dụng các hàm đã tạo nên viết một lịch trình nhập xuất dễ dàng và đơn giản trong C++.

1. Kết cấu dữ liệu của hàng hóng Queue

Hàng đợi là một kết cấu trừu tượng, vị vậy để gia công việc cùng với nó ta bắt buộc tạo cấu tạo dữ liệu cho nó. Trong gợi ý này mình sử dụng danh sách link để sản xuất Queue vì chưng vậy thứ nhất ta cần phải có cấu trúc của một Node trong list liên kết.

Tiếp cho là nhị hàm khởi tạo rỗng mang lại Node cùng hàm tạo bắt đầu một Node, đó là những hàm mà bọn họ đã học tập ở những bài về danh sách liên kết

/* khởi sinh sản rỗng mang đến Node vào danh sách links */void Init( Queue &q )q.head = q.tail = NULL;/* hàm chế tạo ra một Node new */Node *createNode( int x )Node *p = new Node;if(!p) exit(1);p->next = NULL;p->data = x;return p;
Cuối thuộc là sinh sản một cấu tạo của hàng chờ Queue bằng cách sử dụng Node để tạo, bao hàm hai con trỏ là head cùng tail nhằm quản lý thành phần đầu và bộ phận cuối.

2. Các hàm cơ bạn dạng trong hàng ngóng 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 hóng Queue: Push(), Top(), Pop().

Hàm Push

Hàm Push() là hàm để thêm các bộ phận vào đầu mặt hàng đợi, đây là một hàm rất đặc biệt quan trọng vì nếu không tồn tại dữ liệu vào hàng hóng thì ta không thể triển khai các thao tác khác.

Việc thứ nhất ta sẽ soát sổ xem sản phẩm đợi gồm rỗng tốt không, nếu như trong Queue không tồn tại thành phần nào thì phần tử được thêm vào đó là pHead với pTail. Trái lại nếu vào Queue đã tồn tại thành phần thì ta đến pNext của pTail trỏ cho 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 thành phần vào đầu vào hàng hóng Queue */void Push(Queue &q, Node *p ) //kiểm tra giả dụ 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 list đã tồn tại bộ phận thì mang lại pNext của pTail trỏ cho tới node phường //khi đó node p đó là pTailelseq.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 hóng Queue tuy thế không xóa nó khỏi Queue. Hay nói theo cách khác là nó chỉ hiển thị bộ phận đầu tiên vào Queue.

Ta thực hiện kiểm tra ví như hàng ngóng tồn tại phần tử thì return thành phần đó, trái lại nếu vào hàng đợi rỗng thì return 0 và ngừng hàm.

int Top(Queue q ) //kiểm tra nếu như hàng chờ tồn tại phần tử thì ta triển khai return bộ phận đầu tiênif(q.head)return q.head->data; //Nếu trong hàng chờ rỗng thì return 0 và ngừng hàmelse return 0;

Hàm Pop

Hàm Pop() là hàm xóa thành phần đầu tiên trong sản phẩm đợi, đấy là một hàm cũng khá quan trọng bởi vì trong một số trường hòa hợp ta cần được xóa phần tử khỏi Queue.

Việc đầu tiên ta sẽ đánh giá xem trong Queue gồm tồn tại phần tử hay không, nếu tất cả tồn tại phần tử thì thực hiện các bước sau:

Tạo bắt đầu một Node p. (là Node sửa chữa cho Node bắt buộc xóa).Trỏ bé trỏ Next đến phần tử tiếp theo để rất có thể xóa phần tử đầu.Gán data cho p và return nó.Thực hiện tại xóa p. Khỏi sản phẩm đợi.

/* hàm xóa bộ phận đầu trong hàng ngóng */int Pop(Queue &q ) //kiểm tra giả dụ hàng đợi tồn tại thì thực hiện các câu lệnhif(q.head) //tạo new một Node p. (là node thay thế sửa chữa cho node đề nghị xóa)Node *p = q.head; //trỏ con trỏ Next đến thành phần tiếp theo để có thể xóa bộ phận đầuq.head = q.head->next; //gán data cho p. Và return nóreturn p->data; //sau lúc 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 lấy ví dụ như này mình sẽ sử dụng những hàm đã tạo ở trên nhằm thêm một số phần tử và mặt hàng đợi, tiếp nối tạo một menu với các làm việc như:

Thêm thành phần vào Queue.Xuất các phần tử trong Queue.Lấy bộ phận đầu tiên vào Queue.Xóa thành phần đầu tiên vào Queue.

Các bạn có thể tham khảo code của chính mình dưới đây, trong những số ấy mình đã bao gồm chú thích rõ ràng.

Full code:

/**** chế tạo ra hàng đợi Queue bởi danh sách links đơn ****/#includeusing namespace std;/* tạo kết cấu của Node vào danh sách links */struct NodeNode *next;int data;;/* tạo cấu tạo của hàng ngóng Queue */struct QueueNode *head, *tail;;/* khởi sinh sản rỗng đến Node vào danh sách link */void Init( Queue &q )q.head = q.tail = NULL;/* hàm chế tác một Node bắt đầu */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 vào hàng chờ Queue */void Push(Queue &q, Node *p ) //kiểm tra giả dụ hàng chờ rỗng thì phần tử thêm vào đó 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ì mang lại pNext của pTail trỏ tới node p. //khi kia node p chính là pTailelseq.tail->next = p;q.tail = p;/* hàm lấy phần tử đầu trong hàng đợi, tuy thế không xóa nó */int Top(Queue q ) //kiểm tra ví như hàng hóng tồn tại thành phần thì ta thực hiện return bộ phận đầu tiênif(q.head)return q.head->data; //Nếu trong hàng hóng 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 ngóng tồn trên thì thực hiện các câu lệnhif(q.head) //tạo bắt đầu một Node phường (là node sửa chữa thay thế cho node nên xóa)Node *p = q.head; //trỏ bé trỏ Next đến phần tử tiếp theo để có thể xóa bộ phận đầuq.head = q.head->next; //gán data cho p. Và return nóreturn p->data; //sau lúc return thì triển khai xóa nó khỏi hàng đợidelete p;return 0;// tuong duong queue rong/* hàm nhập các bộ phận vào hàng ngóng */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 thành phần trong hàng hóng */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ẽ sử dụng thao tác 1 với 2 vào menu, các chúng ta cũng 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 đã tra cứu hiểu hoàn thành cách thiết lập hằng chờ Queue bằng list liên kết, cũng như tạo những hàm cơ phiên bản trong Queue. Các bạn hãy rèn luyện nó thật những để hoàn toàn có thể ghi lưu giữ nhớ thật thọ nhé. Ở bài tiếp theo mình đã hướng dẫn các bạn cách cài đặt Queue bởi mảng một chiều, hãy để ý theo dõi nhé !!

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

Để làm được bài bác này các bạn cần có kiến thức và kỹ năng về cấu tạo Queue…

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

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

Hàng ngóng Queue là gì? cấu trúc dữ liệu và những cách thiết lập Queue

Trong khuyên bảo này mình đang giới thiệu chúng ta một kết cấu lưu trữ…

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

họ sẽ với mọi người trong nhà tạo một kết cấu Stack với danh sách liên kết…

bài bác tập biến đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ tiến hành giải một bài toán đổi khác cơ…

thiết đặt Stack bằng mảng một chiều

họ sẽ lần lượt tiến hành tạo những hàm cơ phiên bản cho Stack như:…

cài đặt Stack bởi danh sách liên kết

họ sẽ triển khai lần lượt các thao tác trong Stack sử dụng danh…

phòng xếp Stack là gì? cấu tạo và cơ chế chuyển động ra sao?

Trong giải đáp này mình đang giới thiệu chúng ta một cấu tạo lưu trữ…

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

Trong chỉ dẫn này mình sẽ giới thiệu chúng ta một cấu tạo dữ liệu…

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

họ sẽ cùng nhau tiến hành xóa Node có một con, Node gồm 2…

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

bọn họ sẽ triển khai một vài bí quyết tìm ra quý hiếm MAX cùng MIN…

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

Trong chỉ dẫn này mình vẫn giới thiệu các bạn cách xuất những Node con…

tra cứu kiếm Node trên cây nhị phân search kiếm

Trong lí giải này mình đang giới thiệu các bạn cách kiếm tìm kiếm một Node…

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

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

kết cấu cây nhị phân là gì? vận động ra sao?

Trong bài này mình vẫn giới thiệu chúng ta một vào các cấu tạo dữ…

Gộp hai danh sách links đôi

chúng ta sẽ thuộc nhau tò mò về bí quyết nối hai danh sách liên kết…

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

chúng ta sẽ cùng nhau khám phá cách tra cứu kiếm một phần tử k trong…