Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương 3. Tổ chức ngăn xếp (Stack) & Hàng đợi (Queue) trên mảng một chiều - Trần Minh Thái

Chương 3. Tổ chức ngăn xếp (Stack) & Hàng đợi (Queue) trên mảng một chiều (3t)Trần Minh TháiEmail: minhthai@huflit.edu.vnWebsite: www.minhthai.edu.vn1Nội dungTrình bày khái niệm Ngăn xếp (Stack) và Hàng đợi (Queue)Các thao tác trên Ngăn xếp và Hàng đợiTổ chức dữ liệu dùng mảng 1 chiềuMinh họa các ứng dụng2Ngăn xếpNgăn xếp là gì?Cách khai báo cấu trúc ngăn xếp dùng mảng một chiều?Các ứng dụng Cài đặt3Ví dụ về Ngăn xếp4Thành phần được lấy ra đầu tiên?Khái niệm StackGồm nhiều phần tử lưu trữ theo thứ tựHoạt động theo cơ chế “Vào sau – Ra trước” (LIFO – Last In, First Out)Đỉnh ngăn xếp5Thao tác cơ bản trên StackInitStack: khởi tạo Stack rỗngIsEmpty: kiểm tra Stack rỗng?IsFull: kiểm tra Stack đầy?Push: thêm 1 phần tử vào StackPop: lấy ra 1 phần tử khỏi StackPushPop6Thao tác Push vào Stack7TopPUSHThao tác Pop khỏi stack8TopPOPStack – Sử dụng mảngABCABC0123456789StackTop9TopNgăn xếp – Sử dụng mảng10 BADCBACBADCBAEDCBATopTopTopTopTopATopVí dụ ngăn xếp chứa số nguyên dươngclass CMyStack{ 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 //Các phương thức xử lý}11Ngăn xếp số nguyên – Khởi tạopublic bool InitStack(int MaxItems){ StkArray = new int[MaxItems]; if (StkArray == null) return false; StkMax = MaxItems; StkTop = -1; return true; }12Ngăn xếp số nguyên – Kiểm tra rỗngpublic bool IsEmpty(){ if (StkTop==-1) return true; return false;}13Stack số nguyên – Kiểm tra đầypublic bool IsFull(){ if (StkTop==StkMax-1) return true; return false;}14Stack số nguyên – Thêm vào stackpublic bool Push (int newitem){ if (IsFull()) return false; StkTop++; StkArray[StkTop] = newitem; return true;}15Stack số nguyên – Lấy phần tử khỏi stackpublic int Pop(){ if (IsEmpty()) return -1; int outitem = StkArray[StkTop]; StkTop--; return outitem;}16Bài tậpViết phương thức nhập và xuất Stack số nguyên dương. Yêu cầu:Cho phép người dùng lần lượt nhập vào Stack các số nguyên dươngNếu nhập vào giá trị = 1) { ThapHaNoi (discs-1, fromPole, aux, toPole); d = fromPole.pop(); toPole.push(d); ThapHaNoi (discs-1, aux, toPole, fromPole); } } Stack – Quick SortĐể khử đệ quy cho Quick Sort, ta sử dụng một stack để lưu lại các partition (phân hoạch) cần tiến hành sắp xếp.Ý tưởng:Push phân hoạch đầu tiên (0, n-1) vào stackTrong khi stack chưa rỗngPop một phân hoạch từ stackChọn phần tử trục trên phân hoạch nàyĐiều chỉnh phân hoạch tương ứng với trụcPush 2 phân hoạch bên trái và phải trục vào stack29Stack – Quick SortPush phân hoạch đầu tiên (0, n-1) vào stackTrong khi stack chưa rỗngPop một phân hoạch từ stackChọn phần tử trục trên phân hoạch nàyĐiều chỉnh phân hoạch tương ứng với trụcPush 2 phân hoạch bên trái và phải trục vào stack(0,4)1547301234ijt1347501234(0,1)(3,4)1345701234Stack rỗngStop30Thực thi biểu thứcGiả sử có biểu thức X = a / b - c + d * e - a * cVới a = 4, b = c = 2, d = e = 3Diễn giải 1: ((4/2)-2)+(3*3)-(4*2)=0 + 8+9=1Hay diễn giải 2:(4/(2-2+3))*(3-4)*2=(4/3)*(-1)*2=-2.66666 Máy tính sẽ tính như thế nào?31precedence rule + associative ruleCon ngườiTrình biên dịchPostfix: Không dấu ngoặc, không độ ưu tiênVí dụ tính 6/2-3+4*2  postfix: 62/3-42*+Chuyển Infix thành Postfix(1) Biểu thức đầy đủ dấu ngoặc a / b - c + d * e - a * c --> ((((a / b) - c) + (d * e)) – (a * c))Tất cả phép toán đặt bên phải dấu ngoặc tượng ứng ((((a / b) - c) + (d * e)) – (a * c))(3) Xoá tất cả dấu ngoặc ab/c-de*+ac*- /-*+*-Thứ tự toán hạng trong Infix và Postfix không đổia + b * c, độ ưu tiên * > +a *1 (b +c) *2 dmatch )*1 = *2Cho biểu thức:10*2+(5*(8+4))-3Chuyển sang dạng PostfixMô phỏng quá trình tính giá trị của biểu thức PostfixBài tập(1) Phép toán được lấy ra khỏi stack khi độ ưu tiên trong stack (isp: in-stack precedence) là lớn hơn hay bằng với độ ưu tiên của phép toán mới đang xét (icp: incoming precedence)(2) Dấu ( có độ ưu tiên trong stack thấp và độ ưu tiên đang xét cao ( ) + - * / % eosisp 0 19 12 12 13 13 13 0icp 20 19 12 12 13 13 13 0Quy luậtBài tậpKhai báo cấu trúc và viết hàm tạo Stack từ chuỗi ký tự str (mỗi phần tử Stack là ký tự)Khai báo cấu trúc và viết hàm tạo Stack từ chuỗi ký tự str (mỗi phần tử Stack là một từ - từ cách nhau bởi khoảng trắng)Cài đặt thuật toán QuickSort dùng StackCài đặt chương trình chuyển từ Infix sang Postfix42QueuePhòng vé43Queue – Định nghĩaHàng đợi là một cấu trúc:Gồm nhiều phần tử có thứ tựHoạt động theo cơ chế “Vào trước, ra trước” (FIFO - First In First Out)44Queue – Định nghĩaCác thao tác cơ bản trên hàng đợi:InitQueue: khởi tạo hàng đợi rỗngIsEmpty: kiểm tra hàng đợi rỗng?IsFull: kiểm tra hàng đợi đầy?EnQueue: thêm 1 phần tử vào cuối hàng đợi, có thể làm hàng đợi đầyDeQueue: lấy ra 1 phần tử từ đầu Queue, có thể làm Queue rỗng45QueueMinh họa thao tác EnQueueMinh họa thao tác DeQueue46QueueDùng 1 mảng (QArray) để chứa các phần tử.Dùng 1 số nguyên (QMax)để lưu số phần tử tối đa trong hàng đợiDùng 2 số nguyên (QFront, QRear) để xác định vị trí đầu, cuối hàng đợiDùng 1 số nguyên (QNumItems) để lưu số phần tử hiện có trong hàng đợi47Queue0123456Qarray3722153QMax = 7QNumItems = 4QFront = 1QRear = 448Ví dụ queue số nguyên dươngclass CMyQueue{ int [] QArray; int QMax; int QNumItems; int QFront; int QRear; //Các phương thức}49Queue số nguyênKhi thêm nhiều phần tử sẽ xảy ra hiện tượng “tràn giả”Giải pháp? Nối dài mảng (mảng động) hay sử dụng một mảng vô cùng lớn?0123456Qarray372215379QMax = 7QNumItems = 6QFront = 1QRear = 650Queue số nguyênXử lý mảng như một danh sách vòng0123456Qarray372215379QMax = 7QNumItems = 6QFront = 1QRear = 651Chỉ số mảng0123456QArray 117192181 QMax7 QNumItems5QFront1QRear5VD: Cho queue như sauQueue số nguyên1. Thêm giá trị 123 vào hàng đợiQueue số nguyênChỉ số mảng0123456QArray 117192181 123QMax7 QNumItems6QFront1QRear62. Lấy một phần tử khỏi hàng đợiQueue số nguyênChỉ số mảng0123456QArray 117192181 123QMax7 QNumItems5QFront2QRear63. Thêm giá trị 456 vào hàng đợiQueue số nguyênChỉ số mảng0123456QArray 456117192181 123QMax7 QNumItems6QFront2QRear0Queue số nguyên – Khởi tạopublic bool InitQueue (int MaxItem){ QArray = new int[MaxItem]; if (QArray == NULL) return false; QMax = MaxItem; QNumItems = 0; QFront = QRear = -1; return true;}56Queue số nguyên – Kiểm tra rỗngpublic bool IsEmpty(){ if (QNumItems == 0) return true; return false;}57Queue số nguyên – Kiểm tra đầypublic bool IsFull(){ if (QMax == QNumItems) return true; return false;}58Queue số nguyên – Thêm phần tử vào queuepublic bool EnQueue(int newitem){ if (IsFull()) return false; QRear++; if (QRear==QMax) QRear = 0; QArray[QRear] = newitem; if (QNumItems==0) QFront = 0; QNumItems++; return true;}59Queue số nguyên – Lấy phần tử khỏi queuepublic int DeQueue(){ if (IsEmpty()) return -1; int itemout = QArray[QFront]; QFront++; QNumItems--; if (QFront==QMax) QFront = 0; if (QNumItems==0) QFront = QRear = -1; return true;}60Queue số nguyên – Xem giá trị đầupublic int QueueFront(){ if (IsEmpty()) return -1; return QArray[QFront];}61Queue số nguyên – Xem giá trị cuốipublic int QueueRear(){ if (IsEmpty()) return -1; return QArray[QRear];}62Bài tập áp dụngViết chương trình nhập/ xuất hàng đợi số nguyên (dùng mảng 1 chiều). Cho biết trong hàng đợi có bao nhiêu số lẻ.63Queue – Ví dụ ứng dụngQuản lý việc thực hiện các tác vụ (task) trong môi trường xử lý song songHàng đợi in ấn các tài liệuVùng nhớ đệm (buffer) dùng cho bàn phímQuản lý thang máy64