tailieunhanh - Cấu trúc dữ liệu và giải thuật part 4

Tham khảo tài liệu 'cấu trúc dữ liệu và giải thuật part 4', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | sau và F trỏ tới lối trước. Nếu ta qui ước dùng địa chỉ tương đối thì khi queue rỗng R F 0 khi bổ sung một phần tử vào queue R sẽ tàng lên 1 còn khi loại bỏ phần tử ra khỏi queue F sẽ tàng lên 1. Sau khi bổ sung thêm phần tử G Sau khi loại bỏ phần tử A Hình Tuy nhiên với cách tổ chức này có thể xuất hiện tình huống là các phần tử của queue sẽ di chuyển khắp không gian nhớ khi thực hiện bổ sung và loại bỏ chẳng hạn cứ liên tiếp thực hiện một phép bổ sung rồi lại một phép loại bỏ đối với queue có dạng như ở hình . Do đó người ta phải khắc phục bằng cách coi không gian nhớ dành cho queue như được tổ chức theo kiểu vòng tròn nghĩa là với vectơ lưu trữ Q thì Q 1 J dược coi như đứng sau Q nỊ như ớ hình . Hình Và tương ứng với cách tổ chức này giải thuật bổ sung và loại bỏ phần tử đô i với queue sẽ như sau 96 Procedure CQINSERT Q F R X ở đây queue được lưu trữ bởi vectơ Q có n phần tù có cấu trúc kiểu vòng tròn. F và R là 2 con trỏ trỏ tới lối trước và lối sau của queue. Giải thuật này thực hiện bổ sung một phần tử mới X vào queue Ị 1. Trường hợp queue đã đầy Ị if F - 1 and R n or F R 1 then begin write TRÀN return end 2. Chỉnh íý con trỏ if F 0 then F R 1 else if R - n then R 1 else R R 1 3. Bổ sung X QỈR X 4. return Procedure CQDELETE Q F R Y Giải thuật này thực hiện việc loại phần tử đang ở lối trước ra khỏi queue thông tin ứng với phần tử bị loại sẽ được bảo lưu ở Y 1. Trường hợp queue rỗng if F 0 then begin write CẠN return end 2. Bảo lưu thông tin của phần tử bị loại Ị Y Ọ F 3. Chỉnh lý con trỏ if F R then F R 0 else if F n then F 1 else F F 1 4. return 97 Chú ý Queue thường dùng đe thực hiện các tuyến chờ waiting line trong các xử lý động đạc biệt trong các hệ mỏ phỏng Simulation Chẳng hạn hệ xử lý việc đật chỗ trước của khách cho một chuyên bay là hệ mô phỏng việc xếp hàng mua ve. Thông tin về khách hàng sẽ được lưu trữ trong queue để xử lý người đăng ký trước sẽ được giải quyết trước nếu như sô chồ bị hạn chế . Trong các phần sau ta sẽ có dịp làm .