Bài 2. Kiểu dữ liệu ngăn xếp

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

Sau bài học này em sẽ:

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?

1. Biểu diễn ngăn xếp bằng mảng một chiều

Hoạt động 1. 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 một chiều. Trả lời các câu hỏi sau:

Chúng ta sẽ quan sát ngăn xếp được cài đặt bằng một danh sách (kiểu list của Python). Sau đây là các trường hợp của ngăn xếp.

Hình 2.1a. Ngăn xếp rỗng

đáy (bottom)

đỉnh (top)

Trong ví dụ trên, chúng ta thấy trong quá trình thêm vào và lấy ra các phần tử của ngăn xếp S thì đỉnh (top) luôn là phần tử cuối của danh sách.

Ngăn xếp được cài đặt bằng mảng một chiều (danh sách thuộc kiểu list của Python). Phép toán push(S, x) thêm x vào cuối mảng. Phép toán pop(S) lấy ra phần tử cuối của mảng. Đỉnh (top) là phần tử cuối của mảng.

2. Các phép toán của kiểu dữ liệu ngăn xếp

Hoạt động 2. Tìm hiểu các hàm của kiểu dữ liệu 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).

Sau đây là 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.

def Stack():
return []

Lệnh tạo ngăn xếp S (S là danh sách rỗng):

S = Stack()

def push(S, x):
S.append(x)

Lệnh gọi hàm:

Ngăn xếp có thể được cài đặt bằng danh sách (kiểu list của Python). Các hàm cơ bản trên ngăn xếp S gồm Stack(), isEmptyStack(S), push(S, x), pop(S) và top(S).

LUYỆN TẬP

VẬN DỤ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:

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.

Lưu ý: