Giáo án điện tử chuyên đề Khoa học máy tính 12 chân trời Bài 1.2: Ngăn xếp

BÀI 1.2: NGĂN XẾP

Xin chào các em học sinh đến với tiết học ngày hôm nay!

A. KHỞI ĐỘNG

Quan sát Hình 1 và cho biết cách thêm đĩa mới vào và lấy ra một đĩa từ chồng đĩa.

Hình 1. Ngăn xếp chứa các đĩa

B. HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Tìm hiểu về ngăn xếp

+ Ngăn xếp là gì? 

+ Cơ chế hoạt động của ngăn xếp là gì? Em hãy mô tả cơ chế đó.

+ Ngoài các thao tác push và pop, em còn có thể thực hiện những thao tác nào trên ngăn xếp?

Dự kiến sản phẩm:

1. Ngăn xếp

- Khái niệm: Ngăn xếp là một cấu trúc dữ liệu tuyến tính dùng để lưu danh sách các phần tử, trong đó việc thêm một phần tử mới và lấy một phần tử hiện có diễn ra ở cùng một đầu, gọi là đỉnh (top) của ngăn xếp. 

- Cơ chế hoạt động: 

Ý nghĩa: Phần tử nào được thêm vào ngăn xếp sau cùng thì sẽ được lấy ra trước tiên, phần tử nào được thêm vào ngăn xếp đầu tiên sẽ được lấy ra sau cùng. Trong đó:

+ Thao tác thêm mới phần tử vào đỉnh ngăn xếp được gọi là push. 

+ Thao tác lấy phần tử ra khỏi đỉnh ngăn xếp được gọi là pop.

Hình 2. Cơ chế LIFO của ngăn xếp

- Trên ngăn xếp, ngoài thao tác push và pop, có thể thực hiện thêm các thao tác:

+ top: trả về giá trị của phần tử ở đỉnh ngăn xếp.

+ Kiểm tra ngăn xếp rỗng.

Hình 3. Thao tác push, pop trên ngăn xếp và đỉnh top.

Hoạt động 2. Biểu diễn và cài đặt ngăn xếp bằng mảng một chiều

+ Các thao tác thêm vào hoặc lấy ra được thực hiện ở vị trí nào của ngăn xếp?

Câu 1. Để biểu diễn ngăn xếp bằng mảng một chiều, em cần sử dụng những thông tin gì?

Câu 2. Vì sao có thể dùng danh sách (kiểu list của Python) để biểu diễn ngăn xếp?

Dự kiến sản phẩm:

2. Biểu diễn và cài đặt ngăn xếp bằng mảng một chiều

a) Biểu diễn ngăn xếp bằng mảng một chiều

- Tương tự như hàng đợi, ngăn xếp dùng để lưu trữ dãy các phần tử tương tự mảng một chiều. 

Có thể dùng mảng một chiều để biểu diễn ngăn xếp. 

- Các thao tác thêm vào hoặc lấy ra chỉ diễn ra ở đỉnh của ngăn xếp. 

Ví dụ: 

Hình 5a. Ngăn xếp

Hình 5b. Biểu diễn ngăn xếp bằng
 mảng một chiều

Hình 5. Biểu diễn ngăn xếp

b) Cài đặt ngăn xếp

- Trong Python, ngăn xếp được cài đặt bằng danh sách kiểu list. Trong đó, đầu lấy ra và đầu thêm vào phần tử luôn ở cuối danh sách. 

- Các phép toán cơ bản cho ngăn xếp được cài đặt thông qua các hàm sau:

+ Khởi tạo ngăn xếp rỗng:

+ Kiểm tra ngăn xếp rỗng:

+ Phép toán push: 

• Thêm phần từ vào đỉnh ngăn xếp. 

• Diễn ra ở đỉnh ngăn xếp. 

• Phần tử ở đáy ngăn xếp luôn có chỉ số bằng 0.

+ Phép toán pop: thao tác pop bắt đầu bằng việc kiểm tra ngăn xếp có rỗng hay không. Nếu không, trả về phần tử cuối mảng.

+ Phép toán top: trả về giá trị của phần tử ở đỉnh ngăn xếp bằng cách trả về giá trị của phần tử cuối mảng.

C. LUYỆN TẬP

Hoàn thành phiếu bài tập sau:

Khoanh tròn vào chữ cái đứng trước câu trả lời đúng nhất:

Câu 1. Thao tác thêm phần tử vào đỉnh ngăn xếp là

A. enqueue.

B. pop.

C. dequeue.

D. push.

Câu 2. Đỉnh của ngăn xếp có chỉ số là

A. 0.  

B. len(stack).                  

C. len(stack) – 1.             

D. 1.

Câu 3. Để thêm x vào đỉnh ngăn xếp, ta sử dụng hàm nào của kiểu list? 

A. stack.top(x).       

B. stack.push(x).

C. stack.append(x).                 

D. stack.pop(x).

Câu 4. Hàm pop(stack) sẽ báo lỗi gì nếu ngăn xếp rỗng?

A. EmptyStack.

B. ValueError.

C. Invalid.

D. StackError.

Câu 5. Hàm top(stack) được dùng để làm gì?

A. Trả về giá trị của phần tử ở đáy ngăn xếp.

B. Trả về giá trị và xoá phần tử ra khỏi đỉnh ngăn xếp.

C. Trả về giá trị và xoá phần tử ra khỏi đáy ngăn xếp.

D. Trả về giá trị của phần tử ở đỉnh ngăn xếp.

………………………..

Gợi ý trả lời:

D. VẬN DỤNG

Câu 1. Để tính giá trị một biểu thức số học bằng máy tính, một số nhà khoa học đã sử dụng cách biểu diễn dạng tiền tố (hay còn gọi là kí pháp Ba lan). Ví dụ, biểu thức số học (2–7/3)*(4–1) sẽ được chuyển sang dạng tiền tố có dạng *–2/73–41 (toán tử đặt trước toán hạng) trước khi tính giá trị. Sử dụng các hàm initStack(), push() để tạo ngăn xếp có các phần tử như sau:

Sau đó, sử dụng các hàm push(), pop() để ngăn xếp trên có kết quả là:

Câu 2. Theo em dùng danh sách liên kết để biểu diễn ngăn xếp được hay không?

Câu 3. Tạo tệp stack.py chứa các hàm push(), pop(), top(), isEmptyStack() của ngăn xếp. Sau đó: 

- Tạo ngăn xếp rỗng.

- Thực hiện các hàm push() với giá trị thích hợp để ngăn xếp có kết quả như Hình 6a.

- Thực hiện các hàm push(), pop() với các giá trị thích hợp để ngăn xếp có kết quả như Hình 6b.

HƯỚNG DẪN VỀ NHÀ

- Xem lại kiến thức đã học ở Bài 1.2.

- Xem trước nội dung Bài 1.3: Ứng dụng của hàng đợi.