TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu - Chương 5: Ngăn xếp - Hàng đợi

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 .

Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.