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

Bài giảng Cấu trúc dữ liệu và giải thuật chương 3.2 cung cấp các kiến thức về ngăn xếp và hàng đợi trong cấu trúc dữ liệu và giải thuật. Chương này tập trung trình bày khái niệm “ngăn xếp” (Stack) và “hàng đợi” (Queue), minh họa các ứng dụng, các phương pháp xây dựng Stack và Queue. Mời các bạn cùng tham khảo.
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.2 - Trần Minh TháiChương 3.2. Ngăn xếp& Hàng đợiTrần Minh TháiEmail: minhthai@itc.edu.vnWebsite: 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)• Minh họa các ứng dụng• Các phương pháp xây dựng Stack và Queue 2Khái niệm Stack 3Khái niệm Stack• Gồ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ếp 4Thao 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 5Thao tác Push vào Stack PUSH Top 6Thao tác Pop khỏi stack Top P OP 7 Cách xây dựng Stack Mảng1chiều Danhsáchliênkết§ Viếtchươngtrìnhdễ § Phức tạp khi triển dàng,nhanhchóng khaichươngtrình§ Bị hạn chế do số § Không bị cố định về lượng phần tử cố số phần tử, phụ định thuộcvàobộnhớ§ Tốn chi phí tái cấp phátvàsaochépvùng nhớ nếu sử dụng mảngđộng 8Stack – Sử dụng mảng Top 6 3 9 Stack 9 3 6 0 1 2 3 4 5 6 7 8 9 9Stack 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ậ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) 16Stack – 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 17Stack – Sử dụng DSLK StkCnt StkTop N 7 7 Data Link 9 9  Data Link 4  4 Data Link 18 Stack – Sử dụng DSLK• Cấu tạo đầu stack stack StkCnt StkCnt StkTop StkTop • Cấu tạo một phần tử endstack N node Data Link endnode Data Link 19Stack số nguyên – Sử dụng DSLKtypedef struct tagSTACK_NODE{ int Data ...