TAILIEUCHUNG - Hàng đợi, sử dụng mảng

Các đối tượng trong hàng đợi được sắp thứ tự theo thời gian chúng được chèn vào hàng Đối tượng được lấy ra khỏi hàng đợi là đối tượng được chèn vào trước nhất. | Hàng đợi Cấu trúc dữ liệu hoạt động theo cơ chế first-in first-out (FIFO) Hai thao tác cơ bản: Chèn vào hàng đợi: enqueue Lấy ra khỏi hàng đợi: dequeue Các đối tượng trong hàng đợi được sắp thứ tự theo thời gian chúng được chèn vào hàng Đối tượng được lấy ra khỏi hàng đợi là đối tượng được chèn vào trước nhất Hàng đợi A B C D . M N head of queue tail of queue enqueue dequeue Hàng đợi, sử dụng mảng Khai báo cấu trúc hàng đợi Typerdef struct Queue { int *arrQueue; int max; int numItems; int front; int rear; } Hàng đợi, sử dụng mảng Thao tác khởi tạo hàng đợi rỗng int InitQueue(Queue &q, int maxItems) { = new int(maxItems); if( == Null) return 0; // không cấp phát được bộ nhớ = maxItems; = 0; // chưa có phần tử nào trong queue = = -1; return 1; // khởi tạo thành công } Hàng đợi, sử dụng mảng Thao tác kiểm tra hàng đợi rỗng int IsEmpty(const Queue q) { if( == 0) return 1; // Queue rỗng return 0; // Queue không rỗng } Hàng đợi, sử dụng mảng Thao tác kiểm tra hàng đợi đầy int IsFull(const Queue q) { if(q. numItems == ) return 1; // Queue đầy return 0; // Queue không đầy } Problem Nếu mảng có kích thước là n, ta có: Phải thực hiện 11 lần chèn vào, 9 lần lấy ra: 0 0 1 1 1 2 8 9 9 9 enqueue( 0 ) enqueue( 1 ) dequeue() enqueue( 2 ) enqueue( 9 ) dequeue(8) enqueue( 10 ) Trừu tượng mảng 9 Trừu tượng mảng 10 9 Giải pháp Trở lại đầu dãy: Yêu cầu: front chỉ số đầu hàng đợi rear chỉ số cuối hàng đợi numItems biến đếm array_size chiều dài mảng 10 9 enqueue( 10 ) Hàng đợi, sử dụng mảng Thao tác EnQueue: thêm 1 phần tử vào cuối hàng đợi int EnQueue(Queue &q, int newItem) { if (IsFull(q)) return 0; // Queue đầy, không thêm vào được ; if( == ) // tràn giá = 0; // quay trở về đầu mảng [] = newItem; // thêm phần tử vào cuối Queue if( == 0) = 0; ; return 1; // thêm thành công } Hàng đợi, sử dụng mảng Thao tác DeQueue: lấy ra 1 phần tử ở đầu hàng đợi

• Kỹ thuật lập trình
• Cơ chế first in first out
• Chèn vào hàng đợi
• Lấy ra khỏi hàng đợi
• Thao tác kiểm tra hàng đợi rỗng
• trật tự breadth first