Chuyên đề Tin 12 CTST Bài 1.1. Hàng đợi

Khi làm thủ tục tại các cơ quan hành chính nhà nước, em sẽ gặp các hệ thống xếp hàng tự động (Hình 1). Theo em, các hệ thống này hoạt động theo nguyên tắc “vào trước ra trước, được đặt tên là “hàng đợi” (queue).

Cho Hình 4, biểu diễn một hàng đợi, gồm có:

a) Phần tử đầu hàng đợi là m, phần tử cuối hàng đợi là x.

b) Sau khi lấy ra một phần tử, thì phần tử đầu hàng đợi là phần tử tiếp ngay sau nó. Ví dụ lấy ra phần tử m, thì phần tử đầu hàng đợi sẽ là +.

c) Sau khi thêm vào phần tử k vào thì phần tử cuối hàng đợi là phần tử k.

Các thông tin cần thiết để biểu diễn hàng đợi bằng mảng 1 chiều là:

Hàng đợi là một dãy các phần tử. Do đó, em có thể dùng mảng 1 chiều để biểu diễn hàng đợi. Phép thêm vào (enqueue) được thực hiện ở đầu rear và phép lấy ra (dequeue) được thực hiện ở đầu font. Phần đầu của hàng đợi được

Với hàng đợi ở Hình 5, hãy vẽ hình khi thực hiện liên tục các thao tác: thêm vào 0, lấy ra, lấy ra.

Hàng đợi ban đầu:

| 40 | 20 | 30 | 10 | 60 | 50 | 70 |

Biểu diễn bằng mảng một chiều:

| 40 | 20 | 30 | 10 | 60 | 50 | 70 |

   0     1    2     3     4    5     6

Thêm vào 0 (enqueue(0)):

| 40 | 20 | 30 | 10 | 60 | 50 | 70 | 0 |

Biểu diễn bằng mảng một chiều:

| 40 | 20 | 30 | 10 | 60 | 50 | 70 | 0 |

   0     1    2     3     4    5     6     7

Lấy ra (dequeue()):

Lấy ra phần tử đầu tiên (40).

| 20 | 30 | 10 | 60 | 50 | 70 | 0 |

Biểu diễn bằng mảng một chiều:

| 20 | 30 | 10 | 60 | 50 | 70 | 0 |

   0     1    2     3     4    5     6

Lấy ra (dequeue()):

Lấy ra phần tử tiếp theo (20).

| 30 | 10 | 60 | 50 | 70 | 0 |

Biểu diễn bằng mảng một chiều:

| 30 | 10 | 60 | 50 | 70 | 0 |

   0     1    2     3     4    5

Không cần sử dụng các chỉ số front, rear khi dùng kiểu list để biểu diễn hàng đợi trong Python vì:

- Việc sử dụng danh sách giúp đơn giản hóa việc quản lý hàng đợi vì không cần phải theo dõi và cập nhật các chỉ số front và rear. Python tự động quản lý các chỉ số này cho bạn khi bạn thêm hoặc lấy phần tử khỏi danh sách.

- Python cung cấp các phương thức append() để thêm phần tử vào cuối danh sách và pop(0) để lấy phần tử từ đầu danh sách. Những phương thức này trực tiếp thực hiện các thao tác tương ứng mà không cần chỉ số riêng biệt.

- Danh sách trong Python có tính linh hoạt cao và tự động điều chỉnh kích thước khi thêm hoặc bớt phần tử. Điều này loại bỏ sự cần thiết phải kiểm tra và điều chỉnh các chỉ số như front và rear để đảm bảo rằng hàng đợi không bị tràn hoặc rỗng.