tailieunhanh - Bài giảng Cấu trúc dữ liệu: Chương 7 - Nguyễn Xuân Vinh

Bài giảng Cấu trúc dữ liệu - Chương 7: Stack - Queue trình bày về khái niệm, các thao tác, hiện thực, ứng dụng của ngăn xếp (stack) và hàng đợi (queue). Đây là tài liệu tham khảo thuộc chuyên ngành Công nghệ thông tin. | STACK - QUEUE Teacher: Nguyễn Xuân Vinh Email: nguyenxuanvinh@ CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] Nội dung Ngăn xếp Hàng đợi 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 Hàng đợi 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 Vì thế, việc thêm một đối tượng vào Stack hoặc lấy một đối tượng ra khỏi Stack được thực hiện theo cơ chế LIFO (Last In First Out - Vào sau ra trước) Các đối tượng có thể được thêm vào Stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi Stack Các phép toán cần có trên Stack Stack hỗ trợ 2 thao tác chính: “Push”: Thao tác thêm 1 đối tượng vào Stack “Pop”: Thao tác lấy 1 đối tượng ra khỏi Stack Ví dụ: 5 3 2 - - 4 6 5 2 3 Push Pop 4 Stack – Các thao tác insertions and deletions permitted at one end— 6 7 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(): . | STACK - QUEUE Teacher: Nguyễn Xuân Vinh Email: nguyenxuanvinh@ CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] Nội dung Ngăn xếp Hàng đợi 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 Hàng đợi 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 Vì thế, việc thêm một đối tượng vào Stack hoặc lấy một đối tượng ra khỏi Stack được thực hiện theo cơ chế LIFO (Last In First Out - Vào sau ra trước) Các đối tượng có thể được thêm vào Stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi Stack Các phép toán cần có trên Stack Stack hỗ trợ 2 thao tác chính: “Push”: Thao tác thêm 1 đối tượng vào Stack “Pop”: Thao tác lấy 1 đối tượng ra khỏi Stack Ví dụ: 5 3 2 - - 4 6 5 2 3 Push Pop 4 Stack – Các thao tác insertions and deletions permitted at one end— 6 7 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 Stack – Các thao tác 8 Mảng 1 chiều Danh sách LK Kích thước stack khi quá thiếu, lúc quá thừa Danh sách liên kết! Push / Pop hơi phức tạp Push/Pop khá dễ dàng Hiện thực Stack 8 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 ( lúc đó trong Stack đang chứa top+1 phần tử) Như vậy, để khai báo một Stack, ta cần một mảng 1 chiều list, và 1 biến số nguyên top cho biết chỉ số của đỉnh Stack: class Stack { int list[] = new int[N]; int top; }; 9 Hiện thực Stack dùng mảng Ngăn xếp được cài đặt bằng mảng phải có: Một biến top dùng để lưu vị trí con trỏ hiện tại. Một mảng dùng để lưu giá trị của ngăn xếp. Khởi tạo ngăn xếp rỗng: Ngăn xếp rỗng là ngăn xếp không chứa bất kỳ phần tử nào Đỉnh ngăn xếp không trỏ tới phần tử nào. Kiểm tra ngăn xếp