Cấu trúc dữ liệu và giải thuật - Chương 3: Ngăn xếp và Hàng đợi

Chương 3.2. Ngăn xếp & Hàng đợiTrần Minh TháiEmail: minhthai@itc.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)Minh họa các ứng dụngCác phương pháp xây dựng Stack và Queue2Khái niệm Stack3Khái niệm StackGồm nhiều phần tửHoạt động theo cơ chế “Vào sau – Ra trước” (LIFO – Last In, First Out)Đỉnh ngăn xếp4Thao 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 StackPushPop5Thao tác Push vào Stack6TopPUSHThao tác Pop khỏi stack7TopPOPCách xây dựng Stack8Mảng 1 chiềuDanh sách liên kếtViết chương trình dễ dàng, nhanh chóngBị hạn chế do số lượng phần tử cố địnhTốn chi phí tái cấp phát và sao chép vùng nhớ nếu sử dụng mảng độngPhức tạp khi triển khai chương trìnhKhông bị cố định về số phần tử, phụ thuộc vào bộ nhớStack – Sử dụng mảng9369360123456789StackTop9Stack 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;10Stack số nguyên – Sử dụng mảngbool InitStack(STACK& s, int MaxItems){ s.StkArray = new int[MaxItems]; if (s.StkArray == NULL) return false; s.StkMax = MaxItems; s.StkTop = -1; return true; }11Stack số nguyên – Sử dụng mảngbool IsEmpty(const STACK &s){ if (s.StkTop==-1) return true; return false;}12Stack số nguyên – Sử dụng mảngbool IsFull(const STACK &s){ if (s.StkTop==s.StkMax-1) return true; return false;}13Stack số nguyên – Sử dụng mảngbool Push (STACK &s, int newitem){ if (IsFull(s)) return false; s.StkTop++; s.StkArray[s.StkTop] = newitem; return true;}14Stack số nguyên – Sử dụng mảngbool Pop(STACK &s, int &outitem){ if (IsEmpty(s)) return false; outitem = s.StkArray[s.StkTop]; s.StkTop--; return true;}15Bài tậpViết hàm nhập và xuất Stack số nguyênKhai 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)16Stack – Ví dụ ứng dụngKiểm tra sự tương ứng của các cặp ngoặc đơn trong một biểu thức( ( A + B ) / C ( A + B ) / C)Đảo ngược một chuỗi ký tựCá Ăn Kiến  nếiK nĂ áC??17Stack – Sử dụng DSLK974NStkCntStkTop7DataLink9DataLink4DataLink18Stack – Sử dụng DSLKCấu tạo đầu stackCấu tạo một phần tửNStkCntStkTopDataLinkstack StkCnt StkTop end stacknode Data Link end node19Stack số nguyên – Sử dụng DSLKtypedef struct tagSTACK_NODE { int Data; tagSTACK_NODE *pNext;} STACK_NODE;typedef struct STACK { int StkCount; STACK_NODE *StkTop;};20Stack – Sử dụng DSLKVD: Thực hiện một số thao tác trên stackSTACK s;InitStack(s);Push(s, 7);Push(s, 4);Pop(s, x); // x = ?NStkCntStkTop7DataLink4DataLink21Stack số nguyên – Sử dụng DSLKvoid InitStack(STACK &s){ s.StkTop = NULL; s.StkCount = 0;}22Stack số nguyên – Sử dụng DSLKbool IsEmpty(const STACK &s){ if (s.StkTop == NULL) return true; return false;}23Stack số nguyên – Sử dụng DSLKbool IsFull (const STACK s){ STACK_NODE* temp = new STACK_NODE; if (temp == NULL) return true; delete temp; return false;}24Stack số nguyên – Sử dụng DSLKbool Push(STACK &s, int newitem){ if (IsFull(s)) return false; STACK_NODE *pNew = new STACK_NODE; pNew->Data = newitem; pNew->pNext = s.StkTop; s.StkTop = pNew; s.StkCount++; return true;}NStkCntStkTop7DataLink4DataLink25Stack số nguyên – Sử dụng DSLKbool Pop(STACK &s, int &outitem){ if (IsEmpty(s)) return false; STACK_NODE *temp = s.StkTop; outitem = s.StkTop->Data; s.StkTop = s.StkTop->pNext; delete temp; s.StkCount--; return true;}NStkCntStkTop7DataLink4DataLinktempoutitem = 426Stack – Ứng dụngStack có nhiều ứng dụng:Lưu vết trong thuật toán “back-tracking” (theo dõi dấu vết)Tính giá trị biểu thức toán học (thuật toán Balan ngược)Khử đệ quy27Stack – 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 stack28Stack – 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ỗngStop29QueuePhòng vé30Queue – Đị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)31Queue – Đị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ỗng32QueueMinh họa thao tác EnQueueMinh họa thao tác DeQueue33Cách xây dựng QueueSử dụng mảng một chiềuSử dụng danh sách liên kết đơn34Queue – 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 đợi35Queue – Sử dụng mảng0123456Qarray3722153QMax = 7QNumItems = 4QFront = 1QRear = 436Queue số nguyên – Sử dụng mảngtypedef struct QUEUE { int* QArray; int QMax; int QNumItems; int QFront; int QRear;};37Queue 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 = 638Queue 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 = 639Chỉ 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ảngbool InitQueue(QUEUE &q, int MaxItem){ q.QArray = new int[MaxItem]; if (q.QArray == NULL) return false; q.QMax = MaxItem; q.QNumItems = 0; q.QFront = q.QRear = -1; return true;}44Queue số nguyên – Sử dụng mảngbool IsEmpty(QUEUE q){ if (q.QNumItems == 0) return true; return false;}45Queue số nguyên – Sử dụng mảngbool IsFull(QUEUE q){ if (q.QMax == q.QNumItems) return true; return false;}46Queue số nguyên – Sử dụng mảngbool EnQueue(QUEUE &q, int newitem){ if (IsFull(q)) return false; 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 true;}47Queue số nguyên – Sử dụng mảngbool DeQueue(QUEUE &q, int &itemout){ if (IsEmpty(q)) return false; 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 true;}48Queue số nguyên – Sử dụng mảngbool QueueFront(const QUEUE &q, int &itemout){ if (IsEmpty(q)) return false; itemout = q.QArray[q.QFront]; return true;}49Queue số nguyên – Sử dụng mảngbool QueueRear(const QUEUE &q, int &itemout){ if (IsEmpty(q)) return false; itemout = q.QArray[q.QRear]; return true;}50Queue – 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áy51Queue – Sử dụng DSLKtypedef struct tagNODE{ int data; tagNODE* pNext;} NODE, *PNODE;typedef struct tagQUEUE{ int NumItems; PNODE pFront, pRear;} QUEUE;52Queue – Sử dụng DSLKCác thao tác cơ bảnbool InitQueue(QUEUE &q);bool IsEmpty(const QUEUE &q);bool IsFull(const QUEUE &q);bool EnQueue(QUEUE &q, int newitem);bool DeQueue(QUEUE &q, int& itemout);53Queue – Sử dụng DSLKbool InitQueue(QUEUE &q){ q.NumItems = 0; q.pFront = q.pRear = NULL; return true;}54Queue – Sử dụng DSLKbool IsEmpty(const QUEUE& q){ return (q.NumItems==0);}55Queue – Sử dụng DSLKbool IsFull(const QUEUE &q){ PNODE tmp = new NODE; if (tmp==NULL) return true; delete tmp; return false;}56Queue – Sử dụng DSLKbool EnQueue(QUEUE &q, int newitem){ if (IsFull(q)) return false; PNODE p = new NODE; p->data = newitem; p->pNext = NULL; if (q.pFront==NULL && q.pRear==NULL) q.pFront = q.pRear = p; else { q.pRear->pNext = p; q.pRear = p; } q.NumItems++; return true;}57Queue – Sử dụng DSLKbool DeQueue(QUEUE &q, int &itemout){ if (IsEmpty(q)) return false; PNODE p = q.pFront; q.pFront = p->pNext; itemout = p->data; q.NumItems--; delete p; if (q.NumItems==0) InitQueue(q); return true;}58