Giải SGK Chuyên đề Tin học 12 Bài 2. Kiểu dữ liệu ngăn xếp

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.

Dùng kiểu dữ liệu mảng để biểu diễn ngăn xếp.

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

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?

Tìm hiểu các hàm cơ bản của ngăn xếp

Đọ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).

Xâu kí tự được gọi là biểu thức nếu nó là rỗng hoặc chỉ chứa các ki tự “(“ và “)”

Ví dụ: "((()())())". Xâu biểu thức được gọi là đúng nếu vị trí các dáu ngoặc được sắp xếp hợp lí theo tự nhiên. Ví dụ các xâu sau là biểu thức đúng:

()

(()())

Ví dụ các xâu biểu thức sau là sai:

((())

))()()

Có thể định nghĩa khái niệm biểu thức đúng bằng đệ quy như sau:

- Xâu rỗng là đúng.

- Nếu xâu A, B đúng thì xâu AB đúng.

- Nếu xâu A là đúng thì xâu (A) đúng.

Cho trước xâu biểu thức A, viết chương trình kiểm tra xem A có là biểu thức đúng hay không. Yêu cầu sử dụng kiểu dữ liệu ngăn xếp.

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.

Lưu ý:

- Biến topldx cho biết đỉnh top của ngăn xếp.

- Ngăn xếp là rỗng thì topldx = -1. Khi topldx = N-1 thì ngăn xếp bị tràn (overflow), không thể thêm phần tử mới vào ngăn xếp S.

- Viết hàm stackOverflow(S) trả về True nếu ngăn xếp S bị tràn; ngược lại trả về False. Hàm stackOverflow(S) sẽ tạo ngoại lệ ValueError(). Sử dụng hàm stackOverflow(S) để kiểm tra ngăn xếp S chưa bị tràn trước khi gọi hàm push(S, x)