Bài giảng Ngăn xếp (Stack) – Hàng đợi (Queue) - Nguyễn Trí Tuấn

1Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 1 p Trình bày khái niệm Stack và Queue p Minh họa các ứng dụng p Các phương pháp xây dựng Stack và Queue dựa trên những cấu trúc dữ liệu đã biết Ngăn xếp (Stack) – Hàng đợi (Queue) Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 2 Nội dung trình bày p Stack p Ví dụ p Định nghĩa p Các thao tác cơ bản p Xây dựng Stack p Queue p Ví dụ p Định nghĩa p Các thao tác cơ bản p Xây dựng Queue 2Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 3 Ngăn xếp (Stack) Các Ví dụ về Stack Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 4 Ngăn xếp (Stack) Các Ví dụ về Stack 3Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 5 Ngăn xếp (Stack) Định nghĩa p Stack là 1 cấu trúc: p gồm nhiều phần tử có thứ tự p hoạt động theo cơ chế “Vào sau – Ra trước” (LIFO – Last In, First Out) Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 6 Ngăn xếp (Stack) Định nghĩa p Các thao tác cơ bản trên Stack: p InitStack: khởi tạo Stack rỗng p IsEmpty: kiểm tra Stack rỗng ? p IsFull: kiểm tra Stack đầy ? p Push: thêm 1 phần tử vào đỉnh Stack, có thể làm Stack đầy p Pop: lấy ra 1 phần tử từ đỉnh Stack, có thể làm Stack rỗng p Stack Top: kiểm tra phần tử đầu Stack 4Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 7 Ngăn xếp (Stack) Minh họa các thao tác Thao tác Push Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 8 Ngăn xếp (Stack) Minh họa các thao tác Thao tác Pop 5Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 9 Ngăn xếp (Stack) Minh họa các thao tác Thao tác Stack Top, Stack không thay đổi Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 10 Ngăn xếp (Stack) Xây dựng Stack p Có 2 cách để xây dựng Stack: p Sử dụng mảng 1 chiều p Sử dụng danh sách liên kết đơn 6Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 11 Ngăn xếp (Stack) Xây dựng Stack, sử dụng mảng 5 2 StkArray StkMax StkTop [0] [1] [2] [3] [4] Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 12 Ngăn xếp (Stack) Xây dựng Stack, sử dụng mảng // Giả sử Stack chứa các phần tử kiểu nguyên // (int) - Khai báo cấu trúc Stack typedef struct STACK { int *StkArray; // mảng chứa các phần tử int StkMax; // số phần tử tối đa int StkTop; // vị trí đỉnh Stack } 7Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 13 Ngăn xếp (Stack) Xây dựng Stack, sử dụng mảng p Thao tác “Khởi tạo Stack rỗng” int InitStack(STACK &s, int MaxItems) { s.StkArray = new int[MaxItems]; if (s.StkArray==NULL) return 0; // Không cấp phát được bộ nhớ s.StkMax = MaxItems; s.StkTop = -1; // chưa có phần tử nào trong Stack return 1; // khởi tạo thành công } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 14 Ngăn xếp (Stack) Xây dựng Stack, sử dụng mảng p Thao tác “Kiểm tra Stack rỗng” int IsEmpty(const STACK &s) { if (s.StkTop==-1) return 1; // Stack rỗng return 0; // Stack không rỗng } 8Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 15 Ngăn xếp (Stack) Xây dựng Stack, sử dụng mảng p Thao tác “Kiểm tra Stack đầy” int IsFull(const STACK &s) { if (s.StkTop==s.StkMax-1) return 1; // Stack đầy return 0; // Stack chưa đầy } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 16 Ngăn xếp (Stack) Xây dựng Stack, sử dụng mảng p Thao tác “Push”: thêm 1 phần tử vào đỉnh Stack int Push(STACK &s, int newitem) { if (IsFull(s)) return 0; // Stack đầy, không thêm vào được s.StkTop++; s.StkArray[s.StkTop] = newitem; return 1; // Thêm thành công } 9Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 17 Ngăn xếp (Stack) Xây dựng Stack, sử dụng mảng p Thao tác “Pop”: lấy ra 1 phần tử từ đỉnh Stack int Pop(STACK &s, int &outitem) { if (IsEmpty(s)) return 0; // Stack rỗng, không lấy ra được outitem = s.StkArray[s.StkTop]; s.StkTop--; return 1; // Lấy ra thành công } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 18 Ngăn xếp (Stack) Xây dựng Stack, sử dụng mảng p Thao tác “StackTop”: kiểm tra 1 phần tử ở đỉnh Stack, không làm thay đổi Stack int StackTop(const STACK &s, int &outitem) { if (IsEmpty(s)) return 0; // Stack rỗng, không lấy ra được outitem = s.StkArray[s.StkTop]; return 1; // Lấy ra thành công } 10 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 19 Ngăn xếp (Stack) – Ví dụ ứng dụng p Kiểm tra sự tương ứng của dấu ngoặc đơn trong 1 biểu thức p Đảo ngược 1 chuỗi ký tự Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 20 Ngăn xếp (Stack) Xây dựng Stack, sử dụng Danh sách liên kết 11 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 21 Ngăn xếp (Stack) Xây dựng Stack, sử dụng Danh sách liên kết Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 22 Ngăn xếp (Stack) Xây dựng Stack, sử dụng Danh sách liên kết // Khai báo cấu trúc 1 phần tử trong Stack typedef struct tagSTACK_NODE { int Data; tagSTACK_NODE *pNext; } STACK_NODE; // Khai báo cấu trúc Stack typedef struct STACK { int StkCount; STACK_NODE *StkTop; } 12 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 23 Ngăn xếp (Stack) Xây dựng Stack, sử dụng Danh sách liên kết p VD. thực hiện 1 số thao tác trên Stack STACK s; InitStack(s); Push(s, “green”); Push(s, “blue”); Pop(s, x); // x = ? Pop(s, y); // y = ? 13 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 25 Ngăn xếp (Stack) Xây dựng Stack, sử dụng Danh sách liên kết p Thao tác khởi tạo Stack rỗng: void InitStack(STACK &s) { s.StkTop = NULL; s.StkCount = 0; } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 26 Ngăn xếp (Stack) Xây dựng Stack, sử dụng Danh sách liên kết p Thao tác “Kiểm tra Stack rỗng”: int IsEmpty(const STACK &s) { if (s.StkTop==NULL) return 1; // Stack rỗng return 0; // Stack không rỗng } 14 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 27 Ngăn xếp (Stack) Xây dựng Stack, sử dụng Danh sách liên kết p Thao tác “Kiểm tra Stack đầy”: int IsFull(const STACK &s) { // thử tạo mới 1 phần tử STACK_NODE *temp = new STACK_NODE; // nếu không tạo được à Stack đầy if (temp==NULL) return 1; delete temp; return 0; // Stack không đầy } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 28 Ngăn xếp (Stack) Xây dựng Stack, sử dụng Danh sách liên kết p Thao tác “Push”: thêm 1 phần tử vào đỉnh Stack # thêm 1 phần tử vào đầu danh sách liên kết int Push(STACK &s, int newitem) { if (IsFull(s)) return 0; // Stack đầy, không thêm vào được STACK_NODE *pNew = new STACK_NODE; pNew->Data = newitem; pNew->pNext = s.StkTop; s.StkTop = pNew; s.StkCount++; return 1; // Thêm thành công } 15 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 29 Ngăn xếp (Stack) Xây dựng Stack, sử dụng Danh sách liên kết Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 30 Ngăn xếp (Stack) Xây dựng Stack, sử dụng Danh sách liên kết p Thao tác “Pop”: lấy ra 1 phần tử từ đỉnh Stack # Xóa 1 phần tử ở đầu danh sách int Pop(STACK &s, int &outitem) { if (IsEmpty(s)) return 0; // Stack rỗng, không lấy ra được STACK_NODE *temp = s.StkTop; outitem = temp->Data; s.StkTop = temp->pNext; delete temp; s.StkCount--; return 1; // Lấy ra thành công } 16 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 31 Ngăn xếp (Stack) Xây dựng Stack, sử dụng Danh sách liên kết Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 32 Ngăn xếp (Stack) Xây dựng Stack, sử dụng Danh sách liên kết p Thao tác “StackTop”: kiểm tra 1 phần tử ở đỉnh Stack, không làm thay đổi Stack int StackTop(const STACK &s, int &outitem) { if (IsEmpty(s)) return 0; // Stack rỗng, không lấy ra được outitem = s.StkTop->Data; return 1; // Lấy ra thành công } 17 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 33 Một ứng dụng của Stack p Lưu vết trong các giải thuật “back-tracking” p Bài toán “N quân Hậu” p Giả sử ta có 8 con hậu và 1 bàn cờ p Làm sao để đặt các quân hậu lên bàn cờ mà các quân hậu không “ăn” nhau ? Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 34 Một ứng dụng của Stack Bài toán “N quân Hậu” Hai quân hậu không được đặt trên cùng 1 dòng... 18 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 35 Một ứng dụng của Stack Bài toán “N quân Hậu” Hai quân hậu không được đặt trên cùng 1 cột... Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 36 Một ứng dụng của Stack Bài toán “N quân Hậu” Hai quân hậu không được đặt trên cùng 1 đường chéo 19 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 37 Một ứng dụng của Stack Bài toán “N quân Hậu” Số quân hậu, kích thước của bàn cờ có thể thay đổi N quân hậu N dò ng N cột Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 38 Một ứng dụng của Stack Bài toán “N quân Hậu” Chương trình sẽ dùng 1 Stack để lưu lại những vị trí đã đặt quân hậu 20 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 39 Một ứng dụng của Stack Bài toán “N quân Hậu” Khi ta quyết định đặt quân hậu vào ô nào, ta sẽ lưu tọa độ ô đó vào Stack Dòng 1, Cột 1 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 40 Một ứng dụng của Stack Bài toán “N quân Hậu” Ta cũng dùng 1 biến (int) để ghi nhận có bao nhiêu quân hậu đã được đặt lên bàn cờ Dòng 1, Cột 1 1 21 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 41 Một ứng dụng của Stack Bài toán “N quân Hậu” Khi đặt quân hậu vào 1 dòng mới, ta luôn bắt đầu từ cột 1 ... Dòng 1, Cột 1 1 Dòng 2, Cột 1 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 42 Một ứng dụng của Stack Bài toán “N quân Hậu” ...nếu xảy ra “xung đột” với 1 quân hậu khác, ta sẽ dịch chuyển quân hậu sang phải… Dòng 1, Cột 1 1 Dòng 2, Cột 3 22 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 43 2 Một ứng dụng của Stack Bài toán “N quân Hậu” Khi không còn “xung đột”, ta kết thúc và tăng giá trị của biến … lên 1 Dòng 1, Cột 1 Dòng 2, Cột 3 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 44 Một ứng dụng của Stack Bài toán “N quân Hậu” Tiếp tục xét dòng thứ 3...vị trí cột đầu bị “xung dột”… Dòng 1, Cột 1 2 Dòng 2, Cột 3 Dòng 3, Cột 1 23 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 45 Một ứng dụng của Stack Bài toán “N quân Hậu” …ta dịch chuyển quân hậu sang phải, nhưng đều xảy ra “xung đột”... Dòng 1, Cột 1 2 Dòng 2, Cột 3 Dòng 3, Cột 2 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 46 Một ứng dụng của Stack Bài toán “N quân Hậu” …không còn vị trí để dịch chuyển Dòng 1, Cột 1 2 Dòng 2, Cột 3 Dòng 3, Cột 4 24 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 47 Một ứng dụng của Stack Bài toán “N quân Hậu” Khi duyệt hết 1 dòng: ppop stack, pgiảm giá trị biến theo dõi đi 1, pvà xử lý tiếp theo trên dòng trước đó… Dòng 1, Cột 1 1 Dòng 2, Cột 3 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 48 Một ứng dụng của Stack Bài toán “N quân Hậu” Xử lý tiếp trên dòng 2, dịch chuyển phần tử sang phải… Dòng 1, Cột 1 1 Dòng 2, Cột 4 25 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 49 Một ứng dụng của Stack Bài toán “N quân Hậu” Vị trí cột 4 không “xung đột” à chọn, tăng giá trị biến theo dõi lên 1, xét tiếp dòng 3… Dòng 1, Cột 1 Dòng 2, Cột 4 2 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 50 Một ứng dụng của Stack Bài toán “N quân Hậu” Trên dòng 3, ta lại bắt đầu từ cột 1… Dòng 1, Cột 1 2 Dòng 2, Cột 4 Dòng 3, Cột 1 26 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 51 Stack – Tóm lại p Stack có nhiều ứng dụng: p Lưu vết trong thuật toán “back-tracking” p Tính giá trị biểu thức toán học (thuật toán Balan ngược) p Khử đệ qui p … Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 52 Hàng đợi (Queue) Ví dụ: hàng đợi mua vé, phải sắp vào cuối hàng 27 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 53 Hàng đợi (Queue) Định nghĩa p Queue là 1 cấu trúc: p gồm nhiều phần tử có thứ tự p hoạt động theo cơ chế “Vào trước – Ra trước” (FIFO – First In, First Out) Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 54 Hàng đợi (Queue) Định nghĩa p Các thao tác cơ bản trên Queue: p InitQueue: khởi tạo Queue rỗng p IsEmpty: kiểm tra Queue rỗng ? p IsFull: kiểm tra Queue đầy ? p EnQueue: thêm 1 phần tử vào cuối Queue, có thể làm Queue đầy p DeQueue: lấy ra 1 phần tử ở đầu Queue, có thể làm Queue rỗng p QueueFront, QueueRear: kiểm tra phần tử đầu và cuối Queue 28 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 55 Hàng đợi (Queue) Queue: Các phần tử thêm vào cuối (Rear), và lấy ra ở đầu (Front) Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 56 Hàng đợi (Queue) Minh họa các thao tác Thao tác EnQueue 29 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 57 Hàng đợi (Queue) Minh họa các thao tác Thao tác DeQueue Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 58 Hàng đợi (Queue) Minh họa các thao tác Thao tác QueueFront 30 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 59 Hàng đợi (Queue) Minh họa các thao tác Thao tác QueueRear Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 60 Hàng đợi (Queue) Xây dựng hàng đợi p Có 2 cách để xây dựng hàng đợi p Sử dụng mảng 1 chiều p Sử dụng danh sách liên kết đơn 31 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 61 Hàng đợi (Queue) Xây dựng hàng đợi, sử dụng mảng p Dùng 1 mảng (QArray) để chứa các phần tử p Dùng 1 số nguyên (QMax) để lưu số phần tử tối đa trong hàng đợi p Dùng 2 số nguyên (QFront, QRear) để xác định vị trí Đầu, Cuối hàng đợi p Dùng 1 số nguyên (QNumItems) để lưu số phần tử hiện có trong hàng đợi Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 62 Hàng đợi (Queue) Xây dựng hàng đợi, sử dụng mảng 37 22 15 3 QArray QMax QNumItems QFront QRear Front Rear 7 4 1 4 [0] [1] [2] [3] [4] [5] [6] 32 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 63 Hàng đợi (Queue) Xây dựng hàng đợi, sử dụng mảng // Giả sử Queue chứa các phần tử kiểu nguyên (int) // Khai báo cấu trúc Queue typedef struct QUEUE { int *QArray; int QMax; int QNumItems; int QFront; int QRear; }; Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 64 Hàng đợi (Queue) Xây dựng hàng đợi, sử dụng mảng Các phần tử đang chứa trong hàng đợi 33 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 65 Hàng đợi (Queue) Xây dựng hàng đợi, sử dụng mảng p Giải pháp là gì ? Có nên Sử dụng 1 mảng vô cùng lớn ? p Khi thêm nhiều phần tử, sẽ làm “tràn” mảng à “Tràn giả” Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 66 Hàng đợi (Queue) Xây dựng hàng đợi, sử dụng mảng p Giải pháp cho tình huống “tràn giả”: xử lý mảng như là 1 danh sách vòng 34 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 67 Hàng đợi (Queue) Xây dựng hàng đợi, sử dụng mảng p Thao tác “Khởi tạo Queue rỗng” int InitQueue(QUERE &q, int MaxItems) { q.QArray = new int[MaxItems]; if (q.QArray==NULL) return 0; // Không cấp phát được bộ nhớ q.QMax = MaxItems; q.QNumItems = 0; // chưa có phần tử nào trong Queue q.QFront = q.QRear = -1; return 1; // khởi tạo thành công } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 68 Hàng đợi (Queue) Xây dựng hàng đợi, sử dụng mảng p Thao tác “Kiểm tra Queue rỗng” int IsEmpty(const QUEUE &q) { if (q.QNumItems==0) return 1; // Queue rỗng return 0; // Queue không rỗng } 35 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 69 Hàng đợi (Queue) Xây dựng hàng đợi, sử dụng mảng p Thao tác “Kiểm tra Queue đầy” int IsFull(const QUEUE &q) { if (q.QNumItems==q.QMax) return 1; // Queue đầy return 0; // Queue không đầy } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 70 Hàng đợi (Queue) Xây dựng hàng đợi, sử dụng mảng p Thao tác “EnQueue”: thêm 1 phần tử vào cuối Queue int EnQueue(QUEUE &q, int newitem) { if (IsFull(q)) return 0; // Queue đầy, không thêm vào được q.QRear++; if (q.QRear==q.QMax) // “tràn giả” q.QRear = 0; // Quay trở về đầu mảng q.QArray[q.QRear] = newitem; // thêm phần tử vào cuối Queue if (q.QNumItems==0) q.QFront = 0; q.QNumItems++; return 1; // Thêm thành công } 36 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 71 Hàng đợi (Queue) Xây dựng hàng đợi, sử dụng mảng p Thao tác “DeQueue”: lấy ra 1 phần tử ở đầu Queue int DeQueue(QUEUE &q, int &itemout) { if (IsEmpty(q)) return 0; // Queue rỗng, không lấy ra được itemout = q.QArray[q.QFront]; // lấy phần tử đầu ra q.QFront++; q.QNumItems--; if (q.QFront==q.QMax) // nếu đi hết mảng … q.QFront = 0; // … quay trở về đầu mảng if (q.QNumItems==0) q.QFront = q.QRear = -1; return 1; // Thêm thành công } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 72 Hàng đợi (Queue) Xây dựng hàng đợi, sử dụng mảng p Thao tác “QueueFront”: kiểm tra phần tử ở đầu Queue int QueueFront(const QUEUE &q, int &itemout) { if (IsEmpty(q)) return 0; // Queue rỗng, không kiểm tra // lấy phần tử đầu ra itemout = q.QArray[q.QFront]; return 1; } 37 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 73 Hàng đợi (Queue) Xây dựng hàng đợi, sử dụng mảng p Thao tác “QueueRear”: kiểm tra phần tử ở cuối Queue int QueueRear(const QUEUE &q, int &itemout) { if (IsEmpty(q)) return 0; // Queue rỗng, không kiểm tra // lấy phần tử cuối ra itemout = q.QArray[q.QRear]; return 1; } Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 74 Hàng đợi (Queue) – Ví dụ ứng dụng p Quản lý việc thực hiện các tác vụ (task) trong môi trường xử lý song song p Hàng đợi in ấn các tài liệu p Vùng nhớ đệm (buffer) dùng cho bàn phím p Quản lý thang máy p Trắc nghiệm: Cho 1 chuỗi str. Kiểm tra xem chuỗi str có đối xứng ? 38 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 75 Hàng đợi (Queue) p Bài tập lý thuyết: Hãy xây dựng 1 Queue bằng cách s