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

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS làm việc độc lập và trả lời các câu hỏi:

+ 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?

-  GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, thảo luận nhóm đôi thực hiện hoạt động Làm SGK tr.11:

Hình 4 biểu diễn một ngăn xếp. Cho biết:

a) Phần tử nào ở đỉnh của ngăn xếp.

b) Sau khi lấy ra một phần tử, thì ngăn xếp gồm các phần tử nào.

c) Sau khi thêm phần từ "x" vào, thì phần tử nào ở đỉnh của ngăn xếp.

Hình 4. Ngăn xếp với các phần tử là các số, phép toán, dấu ngoặc

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tìm hiểu nội dung mục 1 SGK tr.10 – 11 và trả lời các câu hỏi mà GV đưa ra.

- GV quan sát và trợ giúp HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- HS lần lượt trả lời các câu hỏi.

- HS khác nhận xét, bổ sung. 

Hướng dẫn trả lời câu hỏi hoạt động Làm SGK tr.11:

a) Phần tử ở đỉnh của ngăn xếp là ).

b) Sau khi lấy ra một phần tử, thì ngăn xếp gồm các phần tử 2; +; 1; (.

c) Sau khi thêm phần từ "x" vào, thì phần tử ở đỉnh của ngăn xếp là x.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- Từ kết quả thảo luận của nhóm, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chính xác hoá lại các nội dung kiến thức.

- GV chốt kiến thức theo hoạt động Ghi nhớ:

• 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ử. 

• Hai thao tác cơ bản trên ngăn xếp là thao tác thêm vào (push) và thao tác lấy ra (pop) đều ở đỉnh ngăn xếp (top). Hai thao tác này thể hiện cơ chế hoạt động "Vào sau – Ra trước" (LIFO – Last In, First Out).

- GV chuyển sang nội dung tiếp theo.

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 CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS hoạt động cá nhân, tìm hiểu nội dung phần a, mục 1 SGK tr.11 và trả lời câu hỏi sau:

+ 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?

- GV chia lớp thành các nhóm 2 – 3 HS, mỗi nhóm tìm hiểu về cách cài đặt ngăn xếp trong Python và viết các hàm cơ bản của ngăn xếp ra giấy, sau đó GV cùng HS phân tích đúng sai và rút ra kết luận.

- GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, trả lời câu hỏi hoạt động Làm SGK tr.12:

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?

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tìm hiểu nội dung mục 2 SGK tr.11 – 12, trả lời câu hỏi và thảo luận, thực hiện các nhiệm vụ mà GV đưa ra.

- GV quan sát và trợ giúp HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời 5 HS lên bảng, mỗi HS viết một hàm.

Hướng dẫn trả lời câu hỏi hoạt động Làm SGK tr.12:

Câu 1. Để biểu diễn ngăn xếp bằng mảng một chiều, cần sử dụng biến top để quản lí đỉnh ngăn xếp. Phần tử ở đáy ngăn xếp luôn có chỉ số 0 khi sử dụng kiểu list để biểu diễn.

Câu 2. Kiểu list của Python là cấu trúc dữ liệu tuyến tính nên có thể dùng để biểu diễn ngăn xếp.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét và gọi một số HS đứng tại vị trí giải thích ý nghĩa của từng câu lệnh trong các hàm trên bảng sau đó chạy chương trình cho HS quan sát kết quả.

- GV chính xác hoá lại các nội dung kiến thức.

- GV chốt kiến thức theo hoạt động Ghi nhớ: 

• Ngăn xếp là một dãy các phần tử. Do đó, ngăn xếp có thể được biểu diễn bằng mảng một chiều hoặc danh sách (kiểu list của Python). 

• Khi ngăn xếp là danh sách (kiểu list), hàm thêm vào push() dùng hàm append() của kiểu list và hàm lấy ra pop() dùng hàm pop() của kiểu list. 

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.