Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài giảng "Cấu trúc dữ liệu - Chương 5: Ngăn xếp - Hàng đợi" cung cấp cho người học các kiến thức cơ bản về: Khái niệm Stack, các thao tác trên Queue, hiện thực Queue, ứng dụng Queue, các thao tác trên Stack, hiện thực Stack, ứng dụng của Stack. . | Chương 5: NGĂN XẾP – HÀNG ĐỢI (Stack - Queue) Nội dung Ngăn xếp (Stack) Hàng đợi (Queue) Nội dung Ngăn xếp (Stack) Khái niệm Stack Các thao tác trên Stack Hiện thực Stack Ứng dụng của Stack Stack - Khái niệm Stack là một danh sách mà các đối tượng được thêm vào và lấy ra chỉ ở một đầu của danh sách (A stack is simply a list of elements with insertions and deletions permitted at one end) Vì thế, thao tác trên Stack được thực hiện theo cơ chế LIFO (Last In First Out - Vào sau ra trước) Stack – Các thao tác Stack hỗ trợ 2 thao tác chính: Push: Thêm 1 đối tượng vào Stack Pop: Lấy 1 đối tượng ra khỏi Stack Ví dụ: 5 2 3 - - 4 Stack cũng hỗ trợ một số thao tác khác: isEmpty(): Kiểm tra xem Stack có rỗng không Top(): Trả về giá trị của phần tử nằm ở đầu Stack mà không hủy nó khỏi Stack. Nếu Stack rỗng thì lỗi sẽ xảy ra 5 2 3 Push Pop 4 insertions and deletions permitted at one end— Stack – Hiện thực Stack (Implementation of a Stack) Mảng 1 chiều Danh sách LK Kích thước stack khi quá thiếu, lúc quá thừa Cấp phát động! Push / Pop khá phức tạp Push/Pop khá dễ dàng Việc ci đặt stack thơng qua mảng một chiều đơn giản vkhhiệu quả. Tuy nhin, hạn chế lớn nhất của phương n ci đặt ny lgiới hạn về kích thước của stack N. Gitrị của N cĩ thể qunhỏ so với nhu cầu thực tế hoặc qulớn sẽ lm lng phí bộ nhớ. Hiện thực Stack dùng mảng (Implementation of a Stack using Array) Có thể tạo một Stack bằng cách khai báo một mảng 1 chiều với kích thước tối đa là N (ví dụ: N =1000) Stack có thể chứa tối đa N phần tử đánh số từ 0 đến N-1 Phần tử nằm ở đỉnh Stack sẽ có chỉ số là top Như vậy, để khai báo một Stack, ta cần một mảng 1 chiều, và 1 biến số nguyên top cho biết chỉ số của đỉnh Stack: struct Stack { DataType list[N]; int top; }; Hiện thực Stack dùng mảng (tt.) (Implementation of a Stack using Array) Các hàm cần cài đặt: Init( Stack &s ): Khởi tạo Stack isEmpty( Stack s ) Push( Stack &s , DataType x ) Pop( Stack &s ) Top( Stack &s ) Khi cài đặt bằng . | Chương 5: NGĂN XẾP – HÀNG ĐỢI (Stack - Queue) Nội dung Ngăn xếp (Stack) Hàng đợi (Queue) Nội dung Ngăn xếp (Stack) Khái niệm Stack Các thao tác trên Stack Hiện thực Stack Ứng dụng của Stack Stack - Khái niệm Stack là một danh sách mà các đối tượng được thêm vào và lấy ra chỉ ở một đầu của danh sách (A stack is simply a list of elements with insertions and deletions permitted at one end) Vì thế, thao tác trên Stack được thực hiện theo cơ chế LIFO (Last In First Out - Vào sau ra trước) Stack – Các thao tác Stack hỗ trợ 2 thao tác chính: Push: Thêm 1 đối tượng vào Stack Pop: Lấy 1 đối tượng ra khỏi Stack Ví dụ: 5 2 3 - - 4 Stack cũng hỗ trợ một số thao tác khác: isEmpty(): Kiểm tra xem Stack có rỗng không Top(): Trả về giá trị của phần tử nằm ở đầu Stack mà không hủy nó khỏi Stack. Nếu Stack rỗng thì lỗi sẽ xảy ra 5 2 3 Push Pop 4 insertions and deletions permitted at one end— Stack – Hiện thực Stack (Implementation of a Stack) Mảng 1 chiều Danh sách LK
