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

Những kiểu dữ liệu sau có thể được dùng để thiết lập dữ liệu ngăn xếp:

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.

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

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

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

+ Biến S là danh sách rỗng.

+ Biến x là phần tử của mảng.

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ố: 2,3,1.

- Hàm Stack() dùng để tạo ngăn xếp rỗng.

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

- Hàm Pop dùng để lấy ra phần tử tại đỉnh của top.

- Hàm Top trả về phần tử tại đỉnh của Top.

Sửa lại hàm pop(S):

def pop(S):

if isEmptyStack(S):

raise ValueError(“Ngăn xếp rỗng không thể thực hiện được lệnh này”)

else:

return S.pop()

Sửa lại hàm top(S):

def top(S):

if isEmptyStack(S):

raise ValueError(“Ngăn xếp rỗng không thể thực hiện được lệnh này”)

else:

return S[len(S)-1]

Vì đỉnh (top) của ngăn xếp S luôn là phần tử cuối cùng của danh sách S. Do vậy không cần biến top.

Vì đáy (bottom) của ngăn xếp S luôn là phần tử đầu tiên của danh sách S. Do vậy không cần biến bottom.

def length(S):

count = 0

while S:

S.pop()

count += 1

return count

def is_valid_expression(expression):

# Khởi tạo ngăn xếp rỗng

stack = []

# Tạo một từ điển để ghép các dấu ngoặc đóng với dấu ngoặc mở tương ứng

matching_parentheses = {')': '(', '}': '{', ']': '['}

# Duyệt qua từng ký tự trong biểu thức

for char in expression:

if char in matching_parentheses.values():

stack.append(char)

elif char in matching_parentheses.keys():

if not stack or stack.pop() != matching_parentheses[char]:

return False

return not stack

def push(S, x):

try:

if not S.stackOverflow():

S.topldx += 1

S.T[S.topldx] = x

except ValueError as e:

print(e)

def pop(S):

if S.isEmpty():

raise IndexError(“Ngăn xếp rỗng!")

item = S.T[S.topldx]

S.T[S.topldx] = None

S.topldx -= 1

return item

def isEmptyStack(S):

return S.topldx == -1

def isFull(S):

return S.topldx == self.size - 1