Bài giảng Cấu trúc dữ liệu và giải thuật - Stack and Queue - Ngô Hữu Dũng
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Stack and Queue - Ngô Hữu Dũng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
- bai_giang_cau_truc_du_lieu_va_giai_thuat_stack_and_queue_ngo.pdf
Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Stack and Queue - Ngô Hữu Dũng
- INDUSTRIAL UNIVERSITY OF HO CHI MINH CITY Data structures and algorithms Stack and Queue Dr. Ngô Hữu Dũng
- Introduction Stack (LIFO – last in, first Queue (FIFO – first in, out: a collection of items first out): a collection of in which only the most items in which first items recently added item may entered are the first ones to be removed. be removed. 2 Cấu trúc dữ liệu và giải thuật - Stack&Queue
- Stack vs. Queue Stack – Ngăn xếp Last In First Out (LIFO) Push 34 Top Thao tác Pop Push 56 Pop 45 Queue – Hàng đợi 37 First In First Out (FIFO) Thao tác deQueue 34 56 45 37 enQueue enQueue deQueue Front Rear 3 Cấu trúc dữ liệu và giải thuật - Stack&Queue
- Push 34 Top Pop 56 45 37 Stack – Last in, first out Stack Ngăn xếp 4 Cấu trúc dữ liệu và giải thuật - Stack&Queue
- Khái niệm Stack Lưu trữ một tập các phần tử theo một trật tự nhất định Nguyên tắc: Last in, first out Vào sau cùng, ra trước tiên Top: Phần tử trên cùng Push 34 Top Chèn phần tử vào top Pop Thao tác push 56 Chèn vào đầu danh sách 45 Xuất phần tử từ top 37 Thao tác pop Xoá phần tử ở đầu danh sách 5 Cấu trúc dữ liệu và giải thuật - Stack&Queue
- Applications Balancing of symbols Infix to Postfix /Prefix conversion Redo-undo features at many places like editors, Photoshop. Forward and backward feature in web browsers Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem. Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and Sudoku solver 6 Cấu trúc dữ liệu và giải thuật - Stack&Queue
- Thao tác trên Stack Push: Thêm một phần tử vào stack Nếu stack chưa đầy thì thêm phần tử ở top Pop: Xoá một phần tử từ stack Nếu stack không rỗng thì xoá phần tử ở top Top: Lấy phần tử ở top initStack: khởi tạo Stack isEmpty: Kiểm tra stack rỗng? Trả về true nếu stack rỗng isFull: Kiểm tra stack đầy? Trả về true nếu stack đầy 7
- Tổ chức dữ liệu Array Linked list 1. struct Stack 1. struct Node 2. { 2. { 3. int top; 3. int data; 4. int capacity; 4. struct Node* next; 5. int* array; 5. }; 6. }; 6. struct Stack 7. struct Stack* tStack; 7. { 8. Node *top; 9. }; 8
- Thao tác Push vào Stack PUSH Top 9
- Thao tác Pop khỏi stack Top POP 10
- Stack – Sử dụng mảng Top 6 3 9 Stack 9 3 6 0 1 2 3 4 5 6 7 8 9 11
- Stack số nguyên – Sử dụng mảng struct 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; 12
- Stack số nguyên – Sử dụng mảng bool InitStack(STACK& s, int MaxItems) { s.StkArray = new int[MaxItems]; if (s.StkArray == NULL) return false; s.StkMax = MaxItems; s.StkTop = -1; return true; } 13
- Stack số nguyên – Sử dụng mảng bool IsEmpty(const STACK &s) { if (s.StkTop==-1) return true; return false; } 14
- Stack số nguyên – Sử dụng mảng bool IsFull(const STACK &s) { if (s.StkTop==s.StkMax-1) return true; return false; } 15
- Stack số nguyên – Sử dụng mảng bool Push (STACK &s, int newitem) { if (IsFull(s)) return false; s.StkTop++; s.StkArray[s.StkTop] = newitem; return true; } 16
- Stack số nguyên – Sử dụng mảng bool Pop(STACK &s, int &outitem) { if (IsEmpty(s)) return false; outitem = s.StkArray[s.StkTop]; s.StkTop ; return true; } 17
- Bài tập Viết hàm nhập và xuất Stack số nguyên 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à 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) 18
- Stack – Ví dụ ứng dụng Kiể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 19
- Stack – Sử dụng DSLK StkCnt StkTop N 7 7 Data Link 9 9 Data Link 4 4 Data Link 20
- Stack – Sử dụng DSLK Cấu tạo đầu stack stack StkCnt StkCnt StkTop StkTop CấuNtạo một phần tử end stack node Data Link end node Data Link 21
- Stack số nguyên – Sử dụng DSLK typedef struct tagSTACK_NODE { int Data; tagSTACK_NODE *pNext; } STACK_NODE; typedef struct STACK { int StkCount; STACK_NODE *StkTop; }; 22
- Stack – Sử dụng DSLK VD: Thực hiện một số thao tác trên stack STACK s; InitStack(s); StkCnt StkTop Push(s, 7); N Push(s, 4); 74 Pop(s, x); // x = ? Data Link 23
- Stack số nguyên – Sử dụng DSLK void InitStack(STACK &s) { s.StkTop = NULL; s.StkCount = 0; } 24
- Stack số nguyên – Sử dụng DSLK bool IsEmpty(const STACK &s) { if (s.StkTop == NULL) return true; return false; } 25
- Stack số nguyên – Sử dụng DSLK bool IsFull (const STACK s) { STACK_NODE* temp = new STACK_NODE; if (temp == NULL) return true; delete temp; return false; } 26
- Stack số nguyên – Sử dụng DSLK bool Push(STACK &s, int newitem) { if (IsFull(s)) StkCnt StkTop return false; N STACK_NODE *pNew = new STACK_NODE; pNew->Data = newitem; 74 Data Link pNew->pNext = s.StkTop; s.StkTop = pNew; s.StkCount++; return true; } 27
- Stack số nguyên – Sử dụng DSLK bool Pop(STACK &s, int &outitem) { StkCnt StkTop if (IsEmpty(s)) N temp return false; STACK_NODE *temp = s.StkTop; 4 outitem = s.StkTop->Data; Data Link s.StkTop = s.StkTop->pNext; delete temp; 7 s.StkCount ; Data Link return true; } outitem = 4 28
- Stack – Ứng dụng Stack 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ử đệ quy 29
- 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 stack Trong khi stack chưa rỗng Pop một phân hoạch từ stack Chọ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ục Push 2 phân hoạch bên trái và phải trục vào stack 30
- Stack – Quick Sort Push phân hoạch đầu tiên (0, n-1) vào stack Trong khi stack chưa rỗng Pop một phân hoạch từ stack Chọ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ục Push 2 phân hoạch bên trái và phải trục vào stack Stack rỗng Stop t 1 53 4 75 357 0 1 2 3 4 (3,4) i j 31 (0,4)(0,1)
- deQueue 34 56 45 37 enQueue Front Rear Queue – First in, first out Queue Hàng đợi 32 Cấu trúc dữ liệu và giải thuật - Stack&Queue
- Queue Phòng vé 33
- Queue – Định nghĩa Hà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) 34
- Queue – Định nghĩa Các thao tác cơ bản trên hàng đợi: InitQueue: khởi tạo hàng đợi rỗng IsEmpty: 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 đầy DeQueue: lấy ra 1 phần tử từ đầu Queue, có thể làm Queue rỗng 35
- Queue Minh họa thao tác EnQueue Minh họa thao tác DeQueue 36
- Cách xây dựng Queue Sử dụng mảng một chiều Sử dụng danh sách liên kết đơn 37
- Queue – Sử dụng mảng Dù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 đợi Dùng 2 số nguyên (QFront, QRear) để xác định vị trí đầu, cuối hàng đợi Dùng 1 số nguyên (QNumItems) để lưu số phần tử hiện có trong hàng đợi 38
- Queue – Sử dụng mảng 0 1 2 3 4 5 6 Qarray 37 22 15 3 QMax = 7 QNumItems = 4 QFront = 1 QRear = 4 39
- Queue số nguyên – Sử dụng mảng typedef struct QUEUE { int* QArray; int QMax; int QNumItems; int QFront; int QRear; }; 40
- Queue số nguyên – Sử dụng mảng Khi thêm nhiều phần tử sẽ xảy ra hiện tượng “tràn giả” 0 1 2 3 4 5 6 Qarray 37 22 15 3 7 9 QMax = 7 QNumItems = 6 QFront = 1 QRear = 6 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? 41
- Queue số nguyên – Sử dụng mảng Xử lý mảng như một danh sách liên kết vòng 0 1 2 3 4 5 6 Qarray 37 22 15 3 7 9 QMax = 7 QNumItems = 6 QFront = 1 QRear = 6 42
- Queue số nguyên – Sử dụng mảng VD: Cho queue như sau Chỉ số mảng 0 1 2 3 4 5 6 QArray 11 7 19 21 81 QMax 7 QNumItems 5 QFront 1 QRear 5
- Queue số nguyên – Sử dụng mảng 1. Thêm giá trị 123 vào hàng đợi Chỉ số mảng 0 1 2 3 4 5 6 QArray 11 7 19 21 81 123 QMax 7 QNumItems 6 QFront 1 QRear 6
- Queue số nguyên – Sử dụng mảng 2. Lấy một phần tử khỏi hàng đợi Chỉ số mảng 0 1 2 3 4 5 6 QArray 11 7 19 21 81 123 QMax 7 QNumItems 5 QFront 2 QRear 6
- Queue số nguyên – Sử dụng mảng 3. Thêm giá trị 456 vào hàng đợi Chỉ số mảng 0 1 2 3 4 5 6 QArray 456 11 7 19 21 81 123 QMax 7 QNumItems 6 QFront 2 QRear 0
- Queue số nguyên – Sử dụng mảng bool 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; } 47
- Queue số nguyên – Sử dụng mảng bool IsEmpty(QUEUE q) { if (q.QNumItems == 0) return true; return false; } 48
- Queue số nguyên – Sử dụng mảng bool IsFull(QUEUE q) { if (q.QMax == q.QNumItems) return true; return false; } 49
- Queue số nguyên – Sử dụng mảng bool 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; } 50
- Queue số nguyên – Sử dụng mảng bool 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; } 51
- Queue số nguyên – Sử dụng mảng bool QueueFront(const QUEUE &q, int &itemout) { if (IsEmpty(q)) return false; itemout = q.QArray[q.QFront]; return true; } 52
- Queue số nguyên – Sử dụng mảng bool QueueRear(const QUEUE &q, int &itemout) { if (IsEmpty(q)) return false; itemout = q.QArray[q.QRear]; return true; } 53
- Queue – Ví dụ ứng dụng Quản lý việc thực hiện các tác vụ (task) trong môi trường xử lý song song Hàng đợi in ấn các tài liệu Vùng nhớ đệm (buffer) dùng cho bàn phím Quản lý thang máy 54
- Queue – Sử dụng DSLK typedef struct tagNODE { int data; tagNODE* pNext; } NODE, *PNODE; typedef struct tagQUEUE { int NumItems; PNODE pFront, pRear; } QUEUE; 55
- Queue – Sử dụng DSLK Các thao tác cơ bản bool 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); 56
- Queue – Sử dụng DSLK bool InitQueue(QUEUE &q) { q.NumItems = 0; q.pFront = q.pRear = NULL; return true; } 57
- Queue – Sử dụng DSLK bool IsEmpty(const QUEUE& q) { return (q.NumItems==0); } 58
- Queue – Sử dụng DSLK bool IsFull(const QUEUE &q) { PNODE tmp = new NODE; if (tmp==NULL) return true; delete tmp; return false; } 59
- Queue – Sử dụng DSLK bool 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; } 60
- Queue – Sử dụng DSLK bool 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; } 61