Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 2: Kiểu dữ liệu 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 trả lời các câu hỏi để ôn tập lại kiến thức về kiểu dữ liệu list của Python và một số hàm, phương thức có liên quan sẽ được sử dụng để cài đặt ngăn xếp.

+ List là gì?

+ Để tạo list rỗng, em sử dụng lệnh nào?

+ Trong Python, list có bị giới hạn phần tử không?

+ Phần tử cuối của list A có chỉ số như thế nào?

+ Phương thức nào dùng để bổ sung thêm phần tử vào cuối của danh sách?

+ Phương thức nào dùng để xoá phần tử cuối cùng của list A và trả về giá trị của phần tử này?

- GV yêu cầu HS thảo luận theo 2 – 3 HS, trả lời câu hỏi Hoạt động 1 - Dùng kiểu dữ liệu mảng để biểu diễn ngăn xếp SGK tr.9:

Quan sát, trao đổi, thảo luận để tìm hiểu cách biểu diễn ngăn xếp bằng mảng một chiều. Trả lời các câu hỏi sau:

+ Có thể biểu diễn ngăn xếp bằng mảng một chiều được không?

+ Cần có các biến nào để thực hiện các phép toán cơ bản trên ngăn xếp?

- GV yêu cầu HS thảo luận theo nhóm 2 – 3 HS và trả lời các câu hỏi:

+ Theo em, ngăn xếp được cài đặt bằng một danh sách (kiểu list của Python) có những trường hợp nào?

- GV tổng hợp cách dùng kiểu dữ liệu danh sách (list) của Python để biểu diễ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, trả lời câu hỏi Củng cố tr.10 SGK:

Câu 1. Dãy các số 1, 2, 3, 4, 5, 6 lần lượt được đưa vào ngăn xếp S bằng lệnh push(). Người thực hiện làm như sau: Cứ thực hiện push(S,x) hai lần thì lại pop(S) một lần. Dãy số kết quả thu được bao gồm những số nào?

Câu 2. Giả sử chúng ta lần lượt thực hiện dãy các lệnh sau (ngăn xếp S ban đầu là rỗng): push(S,1); push(S,2); pop(S); push(S,3); pop(S); pop(S).

Dãy các phần tử lần lượt được đưa ra khỏi ngăn xếp là các số nào?

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.9 – 10 và thảo luận 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

- Đại diện các nhóm HS trả lời.

- Các nhóm khác đưa ra ý kiến nhận xét.

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: 

• Ngăn xếp được cài đặt bằng mảng một chiều (danh sách thuộc kiểu list của Python). 

• Phép toán push(S, x) thêm x vào cuối mảng. 

• Phép toán pop(S) lấy ra phần tử cuối của mảng. 

• Đỉnh (top) là phần tử cuối của mảng.

* Ôn tập lại kiến thức:

- List là một dãy các phần tử tuyến tính, đánh chỉ số từ 0.

- Có thể tạo list rỗng bằng lệnh A = [] hoặc A = list().

- List trong Python có thể có không hạn chế các phần tử.

- Có thể bổ sung thêm phần tử vào cuối của danh sách bằng phương thức append().  

Ví dụ: A.append(x) sẽ bổ sung x vào cuối dãy A. 

- Phần tử cuối của list A có chỉ số len(A) –1 hoặc –1.

- Phương thức (hàm) A.pop() sẽ xoá phần tử cuối của A và trả về giá trị phần tử này.

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

Ngăn xếp được cài đặt bằng một danh sách (kiểu list của Python) có các trường hợp sau:

a) Khởi tạo ngăn xếp S rỗng: Đặt S là danh sách rỗng. 

Hình 2.1a. Ngăn xếp rỗng

b) Phép toán push(S,x):

- Dùng để thêm x vào đỉnh top của ngăn xếp S, nghĩa là thêm x vào cuối danh sách. 

- Đáy (bottom) của ngăn xếp là phần tử đầu tiên và đỉnh (top) của ngăn xếp là phần tử cuối của danh sách.

Ví dụ: Hình 2.1b minh hoạ quá trình thêm các giá trị 3, 8, –1, 18, 10, 7 vào ngăn xếp:

Hình 2.1b. Ngăn xếp với phép toán 
thêm vào

c) Phép toán pop(S) dùng để lấy ra và trả về phần tử ở đỉnh (top) của ngăn xếp S, nghĩa là lấy ra phần tử cuối của danh sách.

Ví dụ: Hình 2.1c minh hoạ ngăn xếp sau khi lấy ra một phần tử.

Hình 2.1c. Ngăn xếp với phép toán lấy ra

Có thể biểu diễn ngăn xếp bằng list của Python:

Lưu ý: Dùng kiểu dữ liệu danh sách (list) của Python để biểu diễn ngăn xếp chỉ là một cách và không phải là cách duy nhất. Có nhiều cách biểu diễn khác nhưng trong phạm vi Bài 2 chỉ học cách này.

Hướng dẫn trả lời câu hỏi Hoạt động 1 SGK tr.9:

- Có thể biểu diễn ngăn xếp bằng mảng một chiều.

- Các biến cần có để thực hiện các phép toán cơ bản trên ngăn xếp:

+ top: phần tử cuối của mảng.

+ bottom: phần tử đầu của mảng.

Hướng dẫn trả lời câu hỏi Củng cố SGK tr.10:

Câu 1. Dãy số kết quả thu được bao gồm các số: 1, 3, 5.

Câu 2. Dãy các phần tử lần lượt được đưa ra khỏi ngăn xếp là các số: 2, 3, 1.

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 đọc Hoạt động 2 - Tìm hiểu các hàm của kiểu dữ liệu ngăn xếp SGK tr.10:

Đọc, trao đổi để biết các hàm cơ bản của ngăn xếp được cài đặt bằng danh sách (kiểu list của Python).

- GV chia lớp thành các nhóm 2 – 3 HS, mỗi nhóm thực hiện 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 Củng cố tr.12 SGK:

Câu 1. Sửa lại hàm pop(S) và top(S) trong hoạt động trên như sau: Nếu ngăn xếp rỗng thì thông báo: “Ngăn xếp rỗng không thể thực hiện được lệnh này”.

Câu 2. Vì sao các hàm cơ bản trên ngăn xếp S được cài đặt bằng danh sách (kiểu list của Python) không cần sử dụng biến top và biến bottom?

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.10 – 11 và thảo luận theo nhóm thực hiện nhiệm vụ.

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

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: 

• Ngăn xếp có thể được cài đặt bằng danh sách (kiểu list của Python). 

• Các hàm cơ bản trên ngăn xếp S gồm Stack(), isEmptyStack(S), push(S,x), pop(S) và top(S).

2. Tìm hiểu các hàm của kiểu dữ liệu ngăn xếp

Một số hàm cơ bản của ngăn xếp được cài đặt bằng danh sách (kiểu list của Python):

* Đỉnh (top) của ngăn xếp S luôn là phần tử cuối của danh sách S, nghĩa là biến top = len(S) – 1. Do đó không cần có biến top.

a) Hàm Stack() dùng để tạo ngăn xếp rỗng, hàm trả về danh sách rỗng:

Lệnh tạo ngăn xếp S rỗng (S là danh sách rỗng):

b) Hàm push(S,x) dùng để thêm x vào đỉnh (top) của ngăn xếp, nghĩa là thêm x vào cuối danh sách S bằng hàm append():

Lệnh gọi hàm:

c) Hàm isEmptyStack(S):

- Trả về True nếu ngăn xếp S rỗng.

- Ngược lại trả về False.

d) Hàm pop(S):

- Lấy ra phần tử tại đỉnh (top) của ngăn xếp S và trả về phần tử này. 

- Nếu S rỗng thì hàm báo lỗi ngoại lệ ValueError và dừng chương trình.

Lệnh gọi hàm:

e) Hàm top(S):

- Trả về phần tử tại đỉnh (top) của ngăn xếp S (phần tử cuối: S[len(S)-1] hoặc 
S[-1]) và phần tử này vẫn còn trong ngăn xếp S (ngăn xếp S không bị thay đổi). 

- Nếu S rỗng thì hàm báo lỗi ngoại lệ ValueError và dừng chương trình.

Lệnh gọi hàm:

Một số ví dụ thiết lập và làm việc với ngăn xếp:

Ví dụ 1. Các lệnh sau thiết lập ngăn xếp rỗng và thêm 10 vào ngăn xếp:

Ví dụ 2. Đoạn mã sau lấy ra và in các phần tử của ngăn xếp S cho đến ngăn xếp S là rỗng:

Hướng dẫn trả lời câu hỏi Củng cố SGK tr.12:

Câu 1. 

- Hàm pop(S):

- Hàm top(S):

Câu 2. Khi sử dụng list để biểu diễn ngăn xếp thì luôn có chỉ số phần tử ở đáy là 0, chỉ số phần tử ở đỉnh là len(S)-1, do đó không cần các biến top hay bottom.