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

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PPTX | Số trang:58

Thêm vào BST

Báo xấu

134
lượt xem 14
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

Chương 3.2. Ngăn xếp & Hàng đợi Trần Minh Thái Email: minhthai@itc.edu.vn Website: www.minhthai.edu.vn 1
Nộ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 2
Khái niệm Stack 3
Khá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 4
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 Pop • Push: thêm 1 phần tử vào Stack • Pop: lấy ra 1 phần tử khỏi Stack 5
Thao tác Push vào Stack PUSH Top 6
Thao tác Pop khỏi stack Top P OP 7
Cách xây dựng Stack Mảng 1 chiều Danh sách liên kết § Viết chương trình dễ § Phức tạp khi triển dàng, nhanh chóng khai chương trì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ộ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 8
Stack – Sử dụng mảng Top 6 3 9 Stack 9 3 6 0 1 2 3 4 5 6 7 8 9 9
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; 10
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; } 11
Stack số nguyên – Sử dụng mảng bool IsEmpty(const STACK &s) { if (s.StkTop==-1) return true; return false; } 12
Stack số nguyên – Sử dụng mảng bool IsFull(const STACK &s) { if (s.StkTop==s.StkMax-1) return true; return false; } 13
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; } 14
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; } 15
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) 16
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 17
Stack – 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ử end stack N node Data Link end node Data Link 19
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; 20