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

Chương 3. Tổ chức ngăn xếp (Stack) & Hàng đợi (Queue) trên mảng một chiềuTrầ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 đợiMinh 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 – Sử dụng mảngstruct ttStack{ 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};typedef struct ttStack STACK;11Ngăn xếp số nguyên – Sử dụng mảngint InitStack(STACK& s, int MaxItems){ s.StkArray = new int[MaxItems]; if (s.StkArray == NULL) return 0; s.StkMax = MaxItems; s.StkTop = -1; return 1; //Khởi tạo thành công }12Ngăn xếp số nguyên – Sử dụng mảngint IsEmpty(const STACK &s){ if (s.StkTop==-1) return 1; return 0;}13Stack số nguyên – Sử dụng mảngint IsFull(const STACK &s){ if (s.StkTop==s.StkMax-1) return 1; return 0;}14Stack số nguyên – Sử dụng mảngint Push (STACK &s, int newitem){ if (IsFull(s)==1) return 0; s.StkTop++; s.StkArray[s.StkTop] = newitem; return 1;}15Stack số nguyên – Sử dụng mảngint Pop(STACK &s, int &outitem){ if (IsEmpty(s)) return 0; outitem = s.StkArray[s.StkTop]; s.StkTop--; return 1;}16Bài tậpViết hàm nhập, xuất Stack số nguyên dương sao cho: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ênChuyể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, * > +a *1 (b +c) *2 dmatch )*1 = *240 Tạo stack opStack rỗng để lưu các toán tử, danh sách list rỗng để lưu kết quả Tách chuỗi biểu thức infix thành danh sách các token Duyệt các token từ trái sang phải3.1. Nếu token là toán hạng thì thêm vào cuối list3.2. Nếu token là dấu ( thì push vào opstack3.3. Nếu token là dấu ) thì pop toán tử trong opstack cho đến khi gặp dấu mở ngoặc. Lần lượt thêm toán tử vào cuối list3.4. Nếu token là *, /, +, hay – thì push opstack (Lưu ý: trước khi push phải kiểm tra và pop toán tử trong opstack nếu toán tử này có độ ưu tiên ≥ độ ưu tiên của token và thêm vào cuối list) Khi xét hết các token thì pop tất cả những toán tử còn lại trong opstack và lần lượt thêm vào cuối list(1) Toán tử đượ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 toán tử đ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 0Độ ưu tiênBà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é43cinemarkQueue – Đị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)44Queue45ABACBADCBADCBrearfrontrearfrontrearfrontrearfrontrearfrontQueue – Đị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ỗng46QueueMinh họa thao tác EnQueueMinh họa thao tác DeQueue47Queue – Sử dụng mảngDù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 đợi48Queue – Sử dụng mảng0123456Qarray3722153QMax = 7QNumItems = 4QFront = 1QRear = 449Queue số nguyên – Sử dụng mảngtypedef struct QUEUE { int* QArray; int QMax; int QNumItems; int QFront; int QRear;};50Queue số nguyên – Sử dụng mảngKhi 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 = 651Queue số nguyên – Sử dụng mảngXử lý mảng như một danh sách liên kết vòng0123456Qarray372215379QMax = 7QNumItems = 6QFront = 1QRear = 652Chỉ số mảng0123456QArray 117192181 QMax7 QNumItems5QFront1QRear5VD: Cho queue như sauQueue số nguyên – Sử dụng mảng1. Thêm giá trị 123 vào hàng đợiQueue số nguyên – Sử dụng mảngChỉ số mảng0123456QArray 117192181 123QMax7 QNumItems6QFront1QRear62. Lấy một phần tử khỏi hàng đợiQueue số nguyên – Sử dụng mảngChỉ số mảng0123456QArray 117192181 123QMax7 QNumItems5QFront2QRear63. Thêm giá trị 456 vào hàng đợiQueue số nguyên – Sử dụng mảngChỉ số mảng0123456QArray 456117192181 123QMax7 QNumItems6QFront2QRear0Queue số nguyên – Sử dụng mảngint InitQueue(QUEUE &q, int MaxItem){ q.QArray = new int[MaxItem]; if (q.QArray == NULL) return 0; q.QMax = MaxItem; q.QNumItems = 0; q.QFront = q.QRear = -1; return 1;}57Queue số nguyên – Sử dụng mảngint IsEmpty(QUEUE q){ if (q.QNumItems == 0) return 1; return 0;}58Queue số nguyên – Sử dụng mảngint IsFull(QUEUE q){ if (q.QMax == q.QNumItems) return 1; return 0;}59Queue số nguyên – Sử dụng mảngint EnQueue(QUEUE &q, int newitem){ if (IsFull(q)==1) return 0; q.QRear++; if (q.QRear==q.QMax) q.QRear = 0; q.QArray[q.QRear] = newitem; if (q.QNumItems==0) q.QFront = 0; q.QNumItems++; return 1;}60Queue số nguyên – Sử dụng mảngint DeQueue(QUEUE &q, int &itemout){ if (IsEmpty(q)==1) return 0; itemout = q.QArray[q.QFront]; q.QFront++; q.QNumItems--; if (q.QFront==q.QMax) q.QFront = 0; if (q.QNumItems==0) q.QFront = q.QRear = -1; return 1;}61Queue số nguyên – Sử dụng mảngint QueueFront(const QUEUE &q, int &itemout){ if (IsEmpty(q)==1) return 0; itemout = q.QArray[q.QFront]; return 1;}62Queue số nguyên – Sử dụng mảngint QueueRear(const QUEUE &q, int &itemout){ if (IsEmpty(q)==1) return 0; itemout = q.QArray[q.QRear]; return 1;}63Bà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ẻ64Queue – 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áy65