Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 13: Hàng đợi - Queues

"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 13: Hàng đợi - Queues" tìm hiểu về khái niệm về hàng đợi, xây dựng và sử dụng Queue, ví dụ về hàng đợi. Để nắm chi tiết nội dung kiến thức, mời các bạn cùng tham khảo bài giảng.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 13: Hàng đợi - Queues Cấu trúc dữ liệu và giải thuật Bài 13. Hàng đợi - Queues Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com1 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical UniversityBài 13. Hàng đợi - QueuesNội dung: 13.1. Khái niệm về hàng đợi. 13.2. Xây dựng và sử dụng Queue. 13.3. Ví dụ về hàng đợi.Tham khảo:1. Data structures and Algorithms Stacks.htm, Kyle Loudon Mastering Algorithms,2. Chapter 6 Stacks and Queues, Elliz Horowitz – Fundamentals of Data Structures.3. Chapter 3 Stacks and Queues, Deshpande Kakle – C and Data Structures.4. Bài giảng TS Nguyễn Nam Hồng.2 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13.1. Khái niệm về hàng đợi (1/8)3 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13.1. Khái niệm về hàng đợi (2/8) Trong ứng dụng máy tính, định nghĩa CTDL hàng đợi là danh sách, trong đó việc thêm một phần tử được thực hiện ở đầu một danh sách (cuối hàng đợi) và việc lấy ra một phần tử được thực hiện ở cuối danh sách (đầu hàng). Hàng đợi còn được gọi là danh sách FIFO (First In First Out). Ví dụ về hàng đợi4 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13.1. Khái niệm về hàng đợi (3/8) Đối với hàng đợi, số lượng ứng dụng có nhiều hơn cả ngăn xếp. Ví dụ như máy tính thực hiện nhiệm vụ, có nhiều hàng đợi được sử dụng:  hàng đợi máy in,  việc truy xuất đĩa,  sử dụng CPU.  chuyển đổi từ Infix sang Prefix. Phần tử đầu hàng đợi được phục vụ trước, phần tử này thường gọi là front hay head. Phần tử mới thêm vào được gọi là rear hay tail.5 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13.1. Khái niệm về hàng đợi (4/8)Định nghĩa:Một hàng đợi các phần tử kiểu T là một chuỗi nối tiếp các phần tử của T và kèm theo một số tác vụ sau: 1. Tạo mới một đối tượng hàng rỗng. 2. Thêm một phần tử mới vào hàng, giả sử hàng đợi chưa đầy (phần tử dữ liệu mới luôn được thêm vào cuối hàng). 3. Loại một phần tử ra khỏi hàng, giả sử hàng chưa rỗng (phần tử bị loại là phần tử tại đầu hàng, thường là phần tử vừa được xử lý xong). 4. Xem phần tử tại đầu hàng (phần tử sắp được xử lý).6 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13.1. Khái niệm về hàng đợi (5/8) Hoạt động của hàng đợi7 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13.1. Khái niệm về hàng đợi (3/8)Xây dựng Queue: Thành phần dữ liệu cho Queue:  MaxEntry: Kích thước của Queue.  QueueEntry: Kiểu dữ liệu dành cho mỗi phần tử trong Queue. Một số phương thức cơ bản của Queue:  QueueClassL();  int isEmpty();  int isFull();  int Dequeue(QueueEntry *value);  int Enqueue(QueueEntry value);  int Peek(QueueEntry *value);  void makeEmpty();8 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13.1. Khái niệm về hàng đợi (4/8)Khai báo lớp Queue (dạng tuyến tính):template // Lớp mẫu cho kiểu dữ liệu của Queueclass QueueClassL{ // Định nghĩa tên lớppublic: QueueClassL(); // Hàm tạo của lớp, khởi tạo thông tin cho Queue int isEmpty(); // Queue rỗng → 1, ngược lại → 0 int isFull(); // Queue đầy → 1, ngược lại → 0 int Dequeue(QueueEntry *value); // Lấy 1 phần tử Queue int Enqueue(QueueEntry value); // Thêm 1 phần tử vào Queue int Peek(QueueEntry *value); // Xem giá trị tại đầu của Queue void makeEmpty(); // Làm rỗng Queueprivate: int front, rear; // front: đầu Queue, rear: cuối Queue QueueEntry entry[MaxEntry]; // Mảng lưu thông tin của Queue};9 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13.1. Khái niệm về hàng đợi (5/8)Một số phương thức của Queue:template templateQueueClassL int QueueClassL ::QueueClassL(void) ::isEmpty(){ { front=rear=-1; if(front==rear)} return 1; else return 0; }10 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13.1. Khái niệm về hàng đợi (6/8)Một số phương thức của Queue: templatetemplate int QueueClassL ::Dequeue(QueueEntry *value)int QueueClassL::isFull() {{ if(!isEmpty()) if(rear==MaxEntry-1) { return 1; front++; else return 0; *value = entry[front];} return 1; } else ...