Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - Trần Minh Thái (2016)

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ì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 đợi, tổ chức dữ liệu dùng mảng 1 chiều, minh họa các ứng dụng
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - Trần Minh Thái (2016)Chương3.Tổchứcngănxếp(Stack)&Hàngđợi(Queue)trênmảngmộtchiều(3t) Trần Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn 1Nội dung• Trì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 đợi• Tổ chức dữ liệu dùng mảng 1 chiều• Minh họa các ứng dụng 2Ngăn xếp• Ngă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 đặt 3Ví dụ về Ngăn xếp Thành phần được lấy ra đầu tiên? 4Khái niệm Stack• Gồ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ếp 5Thao tác cơ bản trên Stack• InitStack: khởi tạo Stack rỗng• IsEmpty: kiểm tra Stack rỗng?• IsFull: kiểm tra Stack đầy? Push Pop• Push: thêm 1 phần tử vào Stack• Pop: lấy ra 1 phần tử khỏi Stack 6Thao tác Push vào Stack PUSH Top 7Thao tác Pop khỏi stack Top P OP 8Stack – Sử dụng mảng Top C B A Stack A B C 0 1 2 3 4 5 6 7 8 9 Top 9Ngăn xếp – Sử dụng mảng Top Top Top E D D D C Top C C C B B B B B Top A A A A A A Top 10Ví 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ỏistackpublic 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êucầu:• Cho phép người dùng lần lượt nhập vào Stack các số nguyên dương• Nếu nhập vào giá trị Stack – Ứ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 18Stack – Ứ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• Khử đệ quy• … 19Bài toán tháp HaNoi ...