Đang chuẩn bị liên kết để tải về tài liệu:
CÂU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - HÀNG ĐỢI

Hàng đợi là một danh sách tuyến tính, trong đó: Việc bổ sung một phần tử vào hàng đợi được thực hiện ở một đầu gọi là cuối hàng Việc loại bỏ một phần tử ra khỏi hàng đợi được thực hiện ở đầu kia gọi là đầu hàng. Danh sách kiểu hàng đợi còn gọi là danh sách FIFO – First In First Out. | HÀNG ĐỢI QUEUE KHÁI NIỆM Hàng đợi là một danh sách tuyến tính, trong đó: Việc bổ sung một phần tử vào hàng đợi được thực hiện ở một đầu gọi là cuối hàng Việc loại bỏ một phần tử ra khỏi hàng đợi được thực hiện ở đầu kia gọi là đầu hàng. Danh sách kiểu hàng đợi còn gọi là danh sách FIFO – First In First Out. KHÁI NIỆM A B C D E F Đầu hàng Cuối hàng Loại bỏ Bổ sung Hình vẽ biểu diễn hàng đợi BIỂU DIỄN CẤU TRÚC DỮ LIỆU Giả sử các phần tử của HĐ có kiểu dữ liệu là Item, độ dài của HĐ là N HĐ được lưu trong BNMT bởi mảng 1 chiều (lưu trữ kế tiếp). Mỗi phần tử của mảng lưu một phần tử của hàng đợi Hàng đợi được biểu diễn là một cấu trúc có 3 thành phần: Thành phần thứ nhất là mảng E lưu các phần tử của HĐ Thành phần thứ hai là biến front lưu chỉ số của phần tử đầu hàng Thành phần thứ ba là biến rear lưu chỉ số của phần tử cuối hàng Cấu trúc dữ liệu như sau: BIỂU DIỄN CẤU TRÚC DỮ LIỆU A B C D E F 0 1 2 3 4 5 6 7 8 9 = Max-1 front = 2 rear = 7 E Mảng lưu trữ hàng đợi BIỂU DIỄN CẤU TRÚC DỮ LIỆU #define Max N //Định nghĩa kiểu Item struct Queue{ int front, rear; Item E[Max]; }; Queue Q; /* Q.rear = -1 -> hàng đợi rỗng, Q.rear = Max-1 -> Hàng đợi đầy */ CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI void Initialize (Queue &Q) { Q.front = 0; Q.rear = -1; } 1. Khởi tạo hàng đợi rỗng int Empty (Queue Q) { return (Q.rear == -1); } 2. Kiểm tra hàng đợi rỗng CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI 1 2 3 4 5 6 7 8 9 Max=10 front = 0 rear = -1 E Biểu diễn hàng đợi rỗng 0 CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI 3. Kiểm tra hàng đợi đầy int Full (Queue Q) { reurn (Q.rear == Max-1); } A B C D E F G H 1 2 3 4 5 6 7 8 9 10 = Max front = 2 rear = 9 E Biểu diễn hàng đợi đầy 0 CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI A B C D E F 1 2 3 4 5 6 7 8 9 10 = Max front = 2 rear = 7 E Mảng lưu trữ hàng đợi 4. Bổ sung một phần tử vào cuối hàng đợi G 0 X CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI A B C D E F 1 2 3 4 5 6 7 8 9 10 = Max front = 2 rear = 8 E Mảng lưu trữ hàng đợi 4. Bổ sung một phần tử vào cuối hàng đợi G 0 X CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI A B C D E F G 1 2 3 4 | HÀNG ĐỢI QUEUE KHÁI NIỆM Hàng đợi là một danh sách tuyến tính, trong đó: Việc bổ sung một phần tử vào hàng đợi được thực hiện ở một đầu gọi là cuối hàng Việc loại bỏ một phần tử ra khỏi hàng đợi được thực hiện ở đầu kia gọi là đầu hàng. Danh sách kiểu hàng đợi còn gọi là danh sách FIFO – First In First Out. KHÁI NIỆM A B C D E F Đầu hàng Cuối hàng Loại bỏ Bổ sung Hình vẽ biểu diễn hàng đợi BIỂU DIỄN CẤU TRÚC DỮ LIỆU Giả sử các phần tử của HĐ có kiểu dữ liệu là Item, độ dài của HĐ là N HĐ được lưu trong BNMT bởi mảng 1 chiều (lưu trữ kế tiếp). Mỗi phần tử của mảng lưu một phần tử của hàng đợi Hàng đợi được biểu diễn là một cấu trúc có 3 thành phần: Thành phần thứ nhất là mảng E lưu các phần tử của HĐ Thành phần thứ hai là biến front lưu chỉ số của phần tử đầu hàng Thành phần thứ ba là biến rear lưu chỉ số của phần tử cuối hàng Cấu trúc dữ liệu như sau: BIỂU DIỄN CẤU TRÚC DỮ LIỆU A B C D E F 0 1 2 3 4 5 6 7 8 9 = Max-1 front = 2 rear = 7 E Mảng lưu trữ hàng đợi BIỂU DIỄN CẤU TRÚC DỮ .