STACK & QUEUE NGĂN XẾP & HÀNG ĐỢI

• Trình bày khái niệm Stack và Queue • Minh họa các ứng dụng • Các phương pháp xây dựng Stack và Queue dựa trên nh ữngcấu trúc dữ liệu đã
Nội dung trích xuất từ tài liệu:
STACK & QUEUE NGĂN XẾP & HÀNG ĐỢISTACK & QUEUENGĂN XẾP & HÀNG ĐỢI Nội dung• Trình bày khái niệm Stack và Queue• Minh họa các ứng dụng• Các phương pháp xây dựng Stack và Queue dựa trên nh ững cấu trúc dữ liệu đã biết•Stack •Queue –Ví dụ –Ví dụ –Định nghĩa –Định nghĩa –Các thao tác cơ bản –Các thao tác cơ bản –Xây dựng Stack –Xây dựng QueueNgăn xếp (Stack)Chồng khay Chồng tiền Chồng sách Chồng áo sơ cà phê xu mi Các ví dụ về Ngăn xếpNgăn xếp - Định nghĩa• Stack là 1 cấu trúc: • gồm nhiều phần tử có thứ tự • hoạt động theo cơ chế “Vào sau – Ra trước” (LIFO – Last In, First Out) Đỉnh ngăn xếp Ngăn xếp - Định nghĩa Push Pop• Các thao 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: thêm 1 phần tử vào đỉnh Stack, có th ể làm Stack đầy • Pop: lấy ra 1 phần tử từ đỉnh Stack, có thể làm Stack rỗng • StackTop: kiểm tra phần tử đầu StackNgăn xếp• Minh họa thao tác Push Data TopNgăn xếp• Minh họa thao tác Pop Data TopNgăn xếp• Minh họa thao tác StackTop  Ngăn xếp không thay đổi ? Data ? Top Ngăn xếp• Có hai cách để xây dựng ngăn xếp • Sử dụng mảng 1 chiều • Sử dụng danh sách liên kết đơnMảng 1 chiều Danh sách liên kết đơn- Viết chương trình dễ Phức tạp khi triển khai chương trìnhdàng, nhanh chóng- Bị hạn chế do số lượng Không bị cố định về sốphần tử cố định phần tử, phụ thuộc vào bộ nhớ- Tốn chi phí tái cấp phát vàsao chép vùng nhớ nếu sửdụng mảng động Ngăn xếp – Sử dụng mảng Xây dựng ngăn xếp bằng mảng 1 chiềuTop 6 3 StkTop 9 Đỉnh ngăn xếp Stack 9 3 6 0 1 2 3 4 5 6 7 8 9 Ngăn xếp có 3 phần tửNgăn xếp – Sử dụng mảng• // Giả sử Stack chứa các phần tử kiểu nguyên• // (int) - Khai báo cấu trúc Stack struct STACK { 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};Ngăn xếp – Sử dụng mảng• Thao tác “Khởi tạo Stack rỗng”int InitStack(STACK& s, int MaxItems){ s.StkArray = new int[MaxItems]; if (s.StkArray == NULL) return 0; // Không cấp phát được bộ nhớ s.StkMax = MaxItems; s.StkTop = -1; // chưa có phần tử nào trong Stack return 1; // khởi tạo thành công}Ngăn xếp – Sử dụng mảng• Thao tác “Kiểm tra Stack rỗng”int IsEmpty(const STACK &s){ if (s.StkTop==-1) return 1; // Stack rỗng return 0; // Stack không rỗng}Ngăn xếp – Sử dụng mảng• Thao tác “Kiểm tra Stack đầy”int IsFull(const STACK &s){ if (s.StkTop==s.StkMax-1) return 1; // Stack đầy return 0; // Stack chưa đầy}Ngăn xếp – Sử dụng mảng• Thao tác “Push”: thêm một phần tử vào đỉnh Stackint Push (STACK& s, int newitem){ if (IsFull(s)) return 0; // stack đầy, không thể thêm s.StkTop++; s.StkArray[s.StkTop] = newitem; return 1; // thêm thành công}Ngăn xếp – Sử dụng mảng• Thao tác “Pop”: lấy ra 1 phần tử từ đỉnh Stackint Pop(STACK& s, int& outitem){ if (IsEmpty(s)) return 0; // Stack rỗng, không lấy ra được outitem = s.StkArray[s.StkTop]; s.StkTop--; return 1; // lấy ra thành công}Ngăn xếp – Sử dụng mảng• Thao tác “StackTop”: kiểm tra 1 phần tử ở đỉnh Stack, không làm thay đổi Stackint StackTop(const STACK s, int& outitem){ if (IsEmpty(s)) return 0; // Stack rỗng, không lấy ra được outitem = s.StkArray[s.StkTop]; return 1; // lấy ra thành công}Ngăn xếp – 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 Ngăn xếp – Sử dụng DSLK StkCnt StkTop N 7 7 Data Link 9 9  Data Link  4 4 Data Link Ngăn xếp – Sử dụng DSLK• Cấu tạo đầu stack StkCnt StkTop stack StkCnt N StkTop end stack• Cấu tạo một phần tử trong stack node Data Link end node Data Link ...