BÀI 2: KIỂU DỮ LIỆU NGĂN XẾP

Chào mừng các em đến với bài học ngày hôm nay!

A. KHỞI ĐỘNG

Theo em, những kiểu dữ liệu sau có thể được dùng để thiết lập dữ liệu ngăn xếp không? Tại sao?

a) Sử dụng kiểu mảng có chiều dài cố định N, với số tự nhiên N khá lớn.

b) Sử dụng kiểu dữ liệu danh sách liên kết (đã học ở chương trình Tin học 11 – Định hướng Khoa học máy tính).

c) Sử dụng kiểu dữ liệu list của Python.

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

Hoạt động 1. Dùng kiểu dữ liệu mảng để biểu diễn 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?

…………………………

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

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

…………………………………………

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

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?

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

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.

…………………………..

C. LUYỆN TẬP

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

Câu 1. Biến top của ngăn xếp S có chỉ số là

A. len(S) + 1.

B. 1.

C. len(S).

D. len(S) – 1.

Câu 2. Để thêm x vào cuối danh sách S, ta sử dụng hàm nào?

A. S.push(x).

B. S.pop(x).

C. S.append(x).

D. S.top(x).

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

A. EmptyStack.

B. ValueError.

C. Invalid.

D. StackError.

Câu 4. Nếu ngăn xếp S là rỗng thì hàm isEmptyStack(S) sẽ trả về giá trị gì?

A. 0.

B. Error.

C. False.

D. True.

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

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

B. Trả về phần tử tại đáy (bottom) của ngăn xếp S và phần tử này vẫn còn trong ngăn xếp S.

C. Trả về phần tử tại đỉnh (top) của ngăn xếp S và phần tử này vẫn còn trong ngăn xếp S.

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

Gợi ý trả lời:

D. VẬN DỤNG

Ngăn xếp S được cài đặt bằng mảng T có N phần tử, phần tử đầu tiên có chỉ số 0. Hãy viết các hàm cơ bản trên ngăn xếp S.

Hướng dẫn về nhà:

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

- Xem trước nội dung Bài 3: Thực hành kiểu dữ liệu ngăn xếp.

Xin trận trọng cảm ơn sự quan tâm theo dõi của các em, hẹn gặp lại!