Giáo án điện tử chuyên đề Khoa học máy tính 12 cánh diều 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!

KHỞI ĐỘNG

Hình 1. Ví dụ một cọc đĩa CD

Lan xếp các đĩa CD thành một cọc (Hình 1). Mỗi lần lấy đĩa ra khỏi cọc, Lan sẽ lấy lần lượt từng đĩa một từ trên xuống. Mỗi lần bổ sung, Lan cũng lần lượt xếp từng đĩa mới vào cọc.

Em hãy:

a) Cho biết với đĩa nằm ở đáy và đĩa nằm ở đỉnh cọc, đĩa nào được thêm vào cọc trước.

b) So sánh quy tắc thực hiện thao tác thêm vào và lấy đĩa ra khỏi cọc với thao tác thêm vào và lấy ra phần tử khỏi hàng đợi đã được học ở bài trước.

Hình 1. Ví dụ một cọc đĩa CD

Đĩa ở đáy được thêm vào cọc trước.

Đĩa ở đỉnh được thêm vào cọc sau.

Thao tác lấy đĩa ra

Thao tác thêm đĩa vào

Thêm đĩa vào đỉnh của cọc.

Lấy đĩa ra khỏi đỉnh của cọc.

Thao tác lấy đĩa ra

Thao tác thêm đĩa vào

Thêm đĩa vào đỉnh của cọc.

Lấy đĩa ra khỏi đỉnh của cọc.

Thao tác thêm vào và lấy ra phần tử khỏi hàng đợi

enqueue

dequeue

KIỂU DỮ LIỆU NGĂN XẾP

BÀI 2

NỘI DUNG BÀI HỌC

1

Một số ví dụ về ngăn xếp và cơ chế hoạt động

2

Kiểu dữ liệu ngăn xếp và các phép toán cơ bản trên ngăn xếp

NỘI DUNG BÀI HỌC

3

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

4

Thực hành

PHẦN 1.

MỘT SỐ VÍ DỤ VỀ NGĂN XẾP VÀ CƠ CHẾ HOẠT ĐỘNG

Hình 1. Ví dụ một cọc đĩa CD

Đỉnh

Đáy

Đọc thông tin và trả lời các câu hỏi sau đây:

• Em hãy quan sát Hình 1 và cho biết vị trí của đĩa đầu tiên và đĩa cuối cùng được thêm vào cọc.
• Thao tác thêm đĩa vào và lấy đĩa ra khỏi cọc được thực hiện tại vị trí nào của cọc?
• Theo em, đĩa CD ở vị trí nào sẽ được lấy ra khỏi cọc trước tiên?

Hình 1. Ví dụ một cọc đĩa CD

Đỉnh

Đáy

Hình 1 mô tả một cọc gồm rất nhiều đĩa CD được xếp theo thứ tự từ dưới lên trên.

Đĩa đầu tiên được thêm vào cọc sẽ nằm ở đáy, đĩa được thêm vào sau cùng sẽ nằm ở đỉnh của cọc.

Thao tác thêm đĩa vào và lấy đĩa ra khỏi cọc chỉ được phép thực hiện tại vị trí đỉnh của cọc.

Cơ chế hoạt động LIFO

push

pop

top

bottom

bottom

top

push

pop

Quy tắc vào sau ra trước - LIFO

• Đĩa CD nào được xếp vào cọc sau cùng thì sẽ được lấy ra khỏi cọc trước tiên.

Em hãy nêu một số ví dụ về ngăn xếp trong cuộc sống hằng ngày.

Em hãy đọc thông tin và trả lời câu hỏi sau đây:

Ví dụ:

Đồ chơi tháp gỗ 7 sắc cầu vồng.

Chồng ghế.

Quần áo được xếp thành chồng trong tủ.

ỨNG DỤNG CỦA NGĂN XẾP TRONG TIN HỌC

Tính năng quay lại trang vừa truy cập ngay trước trong các trình duyệt web

1

Tác vụ hoàn tác/làm lại: Chức năng Undo khi soạn thảo văn bản.

2

Giải quyết một số bài toán như tính giá trị của biểu thức số học, kiểm tra dấu ngoặc.

3

Theo dõi quá trình thực hiện của thuật toán quay lui, khử đệ quy,…

4

PHẦN 2.

KIỂU DỮ LIỆU NGĂN XẾP VÀ CÁC PHÉP TOÁN CƠ BẢN TRÊN NGĂN XẾP

Hoạt động 1

• Vẽ ngăn xếp S thu được sau khi Thái thực hiện hai thao tác thêm vào liên tiếp và một thao tác lấy ra.
• Cho biết Thái cần thực hiện những thao tác thêm vào và lấy ra theo thứ tự như thế nào để có thể thu được ngăn xếp S như ở Hình 3.

Cho dãy A gồm 10 số nguyên lẻ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19. Bạn Thái sẽ thực hiện một cách tuỳ ý các thao tác thêm vào và lấy ra trên ngăn xếp S ban đầu đang không có phần tử nào. Các thao tác thêm vào sẽ lấy ra lần lượt từng số trong dãy A để bổ sung vào ngăn xếp. Em hãy:

Đọc thông tin trong SGK và trả lời các câu hỏi sau đây:

• Ngăn xếp thuộc kiểu dữ liệu gì?
• Phép toán thêm vào (push) và lấy ra (pop) được thực hiện ở đỉnh (Top) hay đáy (Bottom) của ngăn xếp?
• Tại mỗi thời điểm, có thể truy cập được vào mấy phần tử của ngăn xếp?
• Có thể lấy ra khỏi ngăn xếp phần tử bất kì được không? Vì sao?
• Mỗi thao tác push sẽ thêm được mấy phần tử vào ngăn xếp?
• Theo em, các phần tử trong ngăn xếp có thể được truy cập một cách trực tiếp như ở kiểu dữ liệu mảng không?

Mô tả mô hình

• Ngăn xếp là một dãy tuyến tính các phần tử dữ liệu.

push

pop

top

bottom

bottom

top

push

pop

Cơ chế LIFO

Tại bất kì thời điểm nào cũng chỉ truy cập được vào một phần tử trên cùng (ở đỉnh) của ngăn xếp.

Mỗi thao tác thêm vào sẽ chỉ thêm được một phần tử vào vị trí ngay trên đỉnh của ngăn xếp.

Các phần tử trong ngăn xếp không được truy cập một cách trực tiếp.

Muốn lấy ra phần tử thứ i tính từ đỉnh ngăn xếp xuống.

phải thực hiện liên tiếp (i – 1) thao tác lấy ra để phần tử thứ i.

TRẢ LỜI HOẠT ĐỘNG 1

a

• Ngăn xếp S ban đầu rỗng, khi thực hiện liên tiếp hai thao tác thêm vào sẽ thu được ngăn xếp S như hình sau:
• Tiếp tục thực hiện một thao tác lấy ra sẽ thu được ngăn xếp S như hình sau:

b

Xuất phát từ ngăn xếp S rỗng, để thu được ngăn xếp S như ở Hình 3, Thái cần thực hiện các thao tác thêm vào và lấy ra theo thứ tự như sau:

• Hai thao tác thêm vào: thêm lần lượt 1 và 3 vào ngăn xếp.
• Một thao tác lấy ra: lấy 3 ra khỏi ngăn xếp.
• Hai thao tác thêm vào: thêm lần lượt 5 và 7 vào ngăn xếp.
• Một thao tác lấy ra: lấy 7 ra khỏi ngăn xếp.
• Bốn thao tác thêm vào: thêm lần lượt 9, 11, 13, 15 vào ngăn xếp.
• Hai thao tác lấy ra: lấy lần lượt 15 và 13 ra khỏi ngăn xếp.
• Một thao tác thêm vào: thêm 17 vào ngăn xếp.

PHẦN 3.

CÀI ĐẶT NGĂN XẾP

Hoạt động 2

Ví dụ: Ngăn xếp S ở Hình 4a có thể được biểu diễn bởi một mảng một chiều mô phỏng như ở Hình 4b. Các phần tử trong mảng theo thứ tự từ đầu đến cuối sẽ tương ứng với các phần tử trong ngăn xếp theo thứ tự từ đáy lên đỉnh.

Để cài đặt ngăn xếp với hai thao tác thêm vào (push) và lấy ra (pop), ta có thể dùng mảng một chiều. Khi đó, các phần tử trong mảng sẽ là các phần tử đang có trong ngăn xếp.

Hoạt động 2

Em hãy vẽ ngăn xếp S và xác định các giá trị tương ứng trong mảng mỗi khi thực hiện xong một thao tác của dãy lần lượt ba thao tác sau:

• Thêm vào ngăn xếp S một phần tử có giá trị 13.
• Thêm vào ngăn xếp S một phần tử có giá trị 15.
• Lấy ra một phần tử khỏi ngăn xếp S

TRẢ LỜI HOẠT ĐỘNG 2

• Ngăn xếp S và mảng một chiều sau khi thêm giá trị 13 vào ngăn xếp.

• Ngăn xếp S và mảng một chiều sau khi thêm giá trị 15 vào ngăn xếp.
• Ngăn xếp S và mảng một chiều sau khi lấy ra một phần tử khỏi ngăn xếp.

Đọc thông tin trong SGK và trả lời các câu hỏi sau đây:

• Từ kết quả của Hoạt động 2, em hãy nhận xét về sự thay đổi giá trị của biến Top khi thực hiện các thao tác thêm vào và lấy ra.
• Theo em, có thể sử dụng kiểu dữ liệu nào của Python để cài đặt ngăn xếp?
• Khi cài đặt ngăn xếp bằng mảng một chiều sử dụng kiểu dữ liệu danh sách thì phần tử ở đỉnh và đáy ngăn xếp có chỉ số như thế nào?

• Khi biểu diễn ngăn xếp S bởi mảng một chiều, ta cần một biến Top để lưu chỉ số trong mảng của phần tử đứng ở đỉnh của ngăn xếp.

S[0]

S[1]

S[…]

S[top]

bottom

top

Tính chất vào sau ra trước của ngăn xếp

Sau khi thực hiện một thao tác lấy ra, giá trị biến Top sẽ giảm đi 1 đơn vị.

Sau khi thực hiện một thao tác thêm vào, giá trị biến Top sẽ tăng lên 1 đơn vị và S[Top] sẽ tương ứng với phần tử mới được thêm vào.

Logo của Python

Trong Python, ngăn xếp S được cài đặt bằng danh sách kiểu list.

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

Phần tử ở đỉnh ngăn xếp có chỉ số len(S) – 1.

Không cần có biến Top.

• Một số hàm cơ bản thường được cài đặt khi làm việc với ngăn xếp:

Bảng 1. Một số hàm cơ bản trên ngăn xếp

• Hàm createStack() trong hình 5 trả về một danh sách rỗng để tạo ngăn xếp rỗng.
• Hàm top(S) trong hình 6 trả về phần tử đang đứng ở đỉnh ngăn xếp S nhưng không lấy nó ra khỏi S.
• Hàm push(S, data) trong hình 7 thêm data vào ngăn xếp S, nghĩa là thêm data vào cuối danh sách.

PHẦN 4.

THỰC HÀNH

--------------- Còn tiếp ---------------