CẤU TRÚC DỮ LIỆU
VÀ GIẢI THUẬT
Lý thuyết


Phần 2 ((Chương
g 3 – tiếp)
p)
Ngăn xếp và Hàng đợi
„
„

Ngăn xếp
Hàng đợi

Vũ Anh Dũng - Khoa CNTT

2


Ngăn xếp ADT (Stack ADT)
„

„

Ngăn xếp là một danh sách đặc biệt mà thao
tác thêm (insert) và loại bỏ (delete) chỉ diễn
ra ở 1 đầu.
Ví trí tại đó phép thêm và xóa diễn ra luôn ở
cuối của danh sách và được gọi là top.


Vũ Anh Dũng - Khoa CNTT

5


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

Có thể sử dụng list hoặc vector
Sử dụng list,
list vector :
„ Thao tác push được thực hiện bằng việc
chèn
hè vào
à cuối
ối danh
d h sách
á h
„ Thao tác pop được thực hiện bằng cách
xóa phần
ầ tử ở cuối
ố danh sách
„ Thao tác top chỉ đơn thuần kiểm tra phần
tử ở cuối danh sách, và trả về giá trị
Vũ Anh Dũng - Khoa CNTT

6




8


Một số ứng dụng –
Cân bằng ký hiệu (Balancing)
„

Kiểm tra các dấu ngoặc trong quá trình
kiểm tra lỗi cú pháp
„
„
„
„

„

„

Tạo một ngăn xếp rỗng.
Đọc các ký tự dấu
Nế ký tự là một
Nếu
ộ ký hiệu
hiệ mở,
ở đặt
đặ nó
ó vào
à trong ngăn
ă xếp.

„

Vũ Anh Dũng - Khoa CNTT

10


Một số ứng dụng –
Biểu thức hậu tố (Postfix Exp)
Xét biểu thức :
4 99 * 1.06
4.99
1 06 + 5.99
5 99 + 6.99
6 99 * 1.06
1 06 =
„ Có thể sử dụng biểu thức Ba Lan dạng hậu
tố như
h sau :
4.99 1.06 * 5.99 + 6.99 1.06 * +
„

Vũ Anh Dũng - Khoa CNTT

11


Một số ứng dụng –
Biểu thức hậu tố (Postfix Exp)
„


Tiếp theo 8 được đNy vào

Bây giờ ‘*’ được nhìn thấy, do vậy 8 và 5
được lấy
ấ ra và 5 * 8 = 40 được đNy
N vào

Vũ Anh Dũng - Khoa CNTT

14


Một số ứng dụng –
Biểu thức hậu tố (Postfix Exp)
„

„

Tiếp theo ‘+’ được nhìn thấy, do vậy 40 và
5 được
ợ lấyy ra và 5 + 40 = 45 được
ợ đNy
y vào

3 được đNy
N vào

Vũ Anh Dũng - Khoa CNTT


thức ở dạng
ạ g chuNn ((được
ợ gọ
gọi theo cách khác
là trung tố - infix) sang dạng hậu tố - postfix
Chúng ta chỉ xét một bài toán nhỏ với các
phép +, *, (, )
Ví dụ : a + b * c + ( d * e + f ) * g
Được chuyển thành a b c * + d e * f + g * +
Vũ Anh Dũng - Khoa CNTT

17


Một số ứng dụng –
Chuyển từ trung tố sang hậu tố
„

Một số quy tắc :
„ Gặp toán hạng : chuyển qua đầu ra
„ Gặp toán tử, hoặc dấu mở ngoặc : đưa
vào stack
„ Toán tử được đưa ra đầu ra sau khi xử lý,
nhưng
h
dấ ngoặc
dấu
ặ thì
hì không
khô



Một số ứng dụng –
Chuyển từ trung tố sang hậu tố
„

Tiếp theo * được đọc. Mục ở đỉnh của ngăn
xếp
p toán tử có q
quyền
y ưu tiên thấp
p hơn so
với *, do vậy không có gì được đưa ra và *
ợ đặt
ặ vào ngăn
g xếp.
p Tiếpp theo,, c được
ợ
được
đọc và đưa ra output

Vũ Anh Dũng - Khoa CNTT

20


Một số ứng dụng –
Chuyển từ trung tố sang hậu tố
„


p

Vũ Anh Dũng - Khoa CNTT

22


Một số ứng dụng –
Chuyển từ trung tố sang hậu tố

„

Bây giờ ta đọc ), do vậy ngăn xếp được làm
rỗng cho tới (.
( Chúng ta đưa ra +

Vũ Anh Dũng - Khoa CNTT

23


Một số ứng dụng –
Chuyển từ trung tố sang hậu tố

„

C ối cùng
Cuối
ù