Câu hỏi:

13/07/2024 327

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)

Xem lời giải

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

Giao bài

Quảng cáo

Trả lời:

Giải bởi Vietjack

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

Đang tải chế độ Học...

Hot: 1000+ đề thi giữa kì 1 lớp 1-12 đầy đủ các môn (Update 2026) (chỉ từ 60k). Tải ngay

ĐẶC QUYỀN VIP

Đăng ký VIP để học và luyện thi không giới hạn

Trọn bộ quyền lợi trên Vietjack, trong một tài khoản.

Phòng luyện thi cấp tốc: ĐGNL - ĐGTD, Tốt nghiệp THPT, Ôn vào 10, Ôn vào 6, Ôn Giữa kì/Cuối kì
Hơn 200K đề thi thử, đề minh hoạ, chính thức các năm
Với 3tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
Tải xuống đề thi [DOCX] với đầy đủ đáp án
Xem hàng ngàn bài giảng đính kèm củng cố thêm kiến thức
Bao gồm tất cả các bậc từ Tiểu học đến Đại học
Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện
Đăng ký ngay

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

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.

Xem đáp án

Lời giải

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

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?

Xem đáp án

Lời giải

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.

Câu 3