Thực hành cái đặt danh sách kiểu hàng đợi
Ta dùng một mảng để chứa các phần tử của hàng, khởi đầu phần tử đầu tiên của hàng được đưa vào vị trí thứ 1 của mảng, phần tử thứ 2 vào vị trí thứ 2 của mảng... Giả sử hàng có n phần tử, ta có front=1 và rear=n. Khi xoá một phần tử front tăng ...
Ta dùng một mảng để chứa các phần tử của hàng, khởi đầu phần tử đầu tiên của hàng được đưa vào vị trí thứ 1 của mảng, phần tử thứ 2 vào vị trí thứ 2 của mảng... Giả sử hàng có n phần tử, ta có front=1 và rear=n. Khi xoá một phần tử front tăng lên 1, khi thêm một phần tử rear tăng lên 1. Như vậy hàng có khuynh hướng đi xuống, đến một lúc nào đó ta không thể thêm vào hàng được nữa dù mảng còn nhiều chỗ trống (các vị trí trước front) trường hợp này ta gọi là hàng bị tràn (xem hình 2).Trong trường hợp toàn bộ mảng đã chứa các phần tử của hàng ta gọi là hàng bị đầy.
Cách khắc phục hàng bị tràn
- Dời toàn bộ hàng lên front-1 vị trí, Cách này gọi là di chuyển tịnh tiến. Trong trường hợp này ta luôn có front <= rear.
- Xem mảng như là một vòng tròn nghĩa là khi hàng bị tràn nhưng chưa đầy ta thêm phần tử mới vào vị trí 1 của mảng, thêm một phần tử mới nữa thì thêm vào vị trí 2 (nếu có thể)...Rõ ràng cách làm này front có thể lớn hơn rear. Cách khắc phục này gọi là dùng mảng xoay vòng (xem hình dưới).
Hình : hàng bị tràn khi có một phần nữa thêm vào
Cài đặt hàng với phương pháp di chuyển tịnh tiến khi hàng bị tràn.
Ðể quản lí một hàng ta chỉ cần quản lí đầu hàng và cuối hàng. Có thể dùng 2 biến số nguyên chỉ vị trí đầu hàng và cuối hàng
Bài 1: Tạo hàng rỗng
Hướng dẫn : Lúc này front và rear không trỏ đến vị trí hợp lệ nào trong mảng vậy ta có thể cho front và rear đều bằng 0
Bài 2 : Kiểm tra hàng rỗng
Hướng dẫn : Trong quá trình làm việc ta có thể thêm và xoá các phần tử trong hàng. Rõ ràng, nếu ta có đưa vào hàng một phần tử nào đó thì front>0. Khi xoá một phần tử ta tăng front lên 1. Hàng rỗng nếu front>rear. Hơn nữa khi mới khởi tạo hàng, tức là front = 0, thì hàng cũng rỗng. Tuy nhiên để phép kiểm tra hàng rỗng đơn giản, ta sẽ làm một phép kiểm tra khi xoá một phần tử của hàng, nếu phần tử bị xoá là phần tử duy nhất trong hàng thì ta đặt lại front = 0. Vậy hàng rỗng khi và chỉ khi front = 0.
Bài 3: Kiểm tra hàng đầy
Hướng dẫn : Hàng đầy nếu số phần tử hiện có trong hàng bằng độ dài của mảng.
Bài 4: Xoá một phần tử của hàng
Hướng dẫn : Xoá phần tử đầu hàng ta chỉ cần cho front tăng lên 1. Nếu front > rear thì hàng thực chất đã rỗng, nên ta khởi tạo lại hàng rỗng (tức là đặt lại giá trị front = rear =0)
Bài 5: Thêm một phần tử vào hàng
Hướng dẫn : Khi thêm một phần tử vào hàng ta xét các trường hợp
- Nếu hàng đầy thì không thêm được nữa.
- Nếu hàng chưa đầy ta phải xét xem hàng có bị tràn không. Nếu hàng bị tràn ta di chuyển tịnh tiến rồi mới nối thêm phần tử mới vào đuôi hàng, rear tăng lên 1. Ðặc biệt nếu thêm vào hàng rỗng thì ta cho front=1 để front trỏ đúng phần tử đầu tiên của hàng.
Cài đặt hàng với phương pháp mảng xoay vòng
Hình : Cài đặt hàng bằng mảng xoay vòng
Với phương pháp này, khi hàng bị tràn, tức là rear=maxlength, nhưng chưa đầy, tức là front >1, thì ta thêm phần tử mới vào vị trí 1 của mảng và cứ tiếp tục như vậy vì từ 1 đến front-1 là các vị trí trống. Vì ta sử dụng mảng một cách xoay vòng như vậy nên phướng pháp này gọi là phương pháp dùng mảng xoay vòng.
Các phần khai báo cấu trúc dữ liệu, tạo hàng rỗng, kiểm tra hàng rỗng giống như phương pháp di chuyển tịnh tiến.
Bài 1: Tạo hàng rỗng
Hướng dẫn : Lúc này front và rear không trỏ đến vị trí hợp lệ nào trong mảng vậy ta có thể cho front và rear đều bằng 0
Bài 2 : Kiểm tra hàng rỗng
Hướng dẫn : Trong quá trình làm việc ta có thể thêm và xoá các phần tử trong hàng. Rõ ràng, nếu ta có đưa vào hàng một phần tử nào đó thì front>0. Khi xoá một phần tử ta tăng front lên 1. Hàng rỗng nếu front>rear. Hơn nữa khi mới khởi tạo hàng, tức là front = 0, thì hàng cũng rỗng. Tuy nhiên để phép kiểm tra hàng rỗng đơn giản, ta sẽ làm một phép kiểm tra khi xoá một phần tử của hàng, nếu phần tử bị xoá là phần tử duy nhất trong hàng thì ta đặt lại front=0. Vậy hàng rỗng khi và chỉ khi front =0.
Bài 3: Kiểm tra hàng đầy
Hướng dẫn : Hàng đầy nếu toàn bộ các ô trong mảng đang chứa các phần tử của hàng. Với phương pháp này thì front có thể lớn hơn rear, do đó hàm được viết như sau:
Bài 4: Xoá một phần tử của hàng
Hướng dẫn : Xoá phần tử đầu hàng ta chỉ cần cho front tăng lên 1. Nếu front > rear thì hàng thực chất đã rỗng, nên ta khởi tạo lại hàng rỗng (tức là đặt lại giá trị front = rear =0)
Bài 5: Thêm một phần tử vào hàng
Hướng dẫn : Khi thêm một phần tử vào hàng ta xét các trường hợp
- Nếu hàng đầy thì không thêm được nữa.
- Nếu hàng chưa đầy ta phải xét xem hàng có bị tràn không. Nếu hàng bị tràn ta di chuyển tịnh tiến rồi mới nối thêm phần tử mới vào đuôi hàng, rear tăng lên 1. Ðặc biệt nếu thêm vào hàng rỗng thì ta cho front=1 để front trỏ đúng phần tử đầu tiên của hàng.
Cách tự nhiên nhất là dùng hai con trỏ front và rear để trỏ tới phần tử đầu hàng và cuối hàng. Hàng được cài đặt như là một danh sách liên kết có Header là một ô thực sự, xem hình II.13.
Bài 1: Tạo hàng rỗng
Hướng dẫn : Front và rear cùng trỏ đến HEADER của hàng.
Bài 2 : Kiểm tra hàng rỗng
Hướng dẫn : Hàng rỗng nếu front và rear chỉ cùng một ô, ô đó chính là HEADER
Bài 3: Kiểm tra hàng đầy
Hướng dẫn : Hàng đầy nếu toàn bộ các ô trong mảng đang chứa các phần tử của hàng. Với phương pháp này thì front có thể lớn hơn rear, do đó hàm được viết như sau:
Bài 4: Xoá một phần tử của hàng
Hướng dẫn : Thực chất là xoá phần tử nằm ở đầu hàng. Ta chỉ cần cho front trỏ tới vị trí kế tiếp nó trong danh sách.
Bài 5: Thêm một phần tử vào hàng
Hướng dẫn : Thêm một phần tử vào hàng ta thêm vào sau rear ( rear^.next ), rồi cho rear trỏ đến phần tử mới này, xem hình. Trường next của ô mới này trỏ tới NIL.
