Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 1
CấutrúcdữliệuvàGiảithuật
Chương III:
Stack và Queue
Danh sách kiểungănxếp - Stack
–Stack
zMộtkiểudanhsáchtuyến tính đặc
biệt
zPhép bổsung và phép loạibỏtuân
thủtheo cơchế“vào sau ra trước”
(last in first out) , đượcthựchiệnở
đầuđỉnh
đỉnh
đáy
Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 2
Danh sách kiểungănxếp - Stack
–Hai thao tác cơbảnđốivới danh sách kiểungăn
xếp
zpush(Element e) : bổsung phầntửvào Stack
zElement pop(): Loạibỏvà trảra giá trịcủaphầntửở
đỉnh Stack
–Các thao tác khác
zInt size(): Trảra sốcác phầntửtrong Stack
zBoolean isEmpty(): KiểmtraxemStack córỗng không
zElement top(): Trảra giá trịcủaphầntửởđỉnh Stack
Các thao tác cơbảncủa Stack
Top
Stack
Top
Push
Dat a
Stack
Top
Đẩymộtphầntử
vào stack
Stack
Overflow
Dat a
Trường hợpStack đầy
Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 3
Các thao tác cơbảncủa Stack
Pop
Top
Stack
Top
Stack
Data
Lấyraphầntửởđỉnh
stack
Top Stack
Underflow
Trường hợp Stack cạn
Danh sách kiểungănxếp
[9,8,7]3size()
[9,8,7]-push(7)
[9,8]-push(8)
[9]-push(9)
[]trueisEmpty()
[]5pop()
[5]7pop()
[5,7]7top()
[5,7]-push(7)
[5]3pop()
[5,3]-push(3)
[5]-push(5)
[ ]-create()
StackOutputThao tác
Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 4
Ứng dụng củaStack
–Lưutrữcác trang web đãtừng được duyệttrên
Web browser
–Cài đặt thao tác Undo trong các phầnmềmsoạn
thảo
–Lưudanhsáchcáclờigọi hàm trong Java Virtual
Machine
Lưutrữkếtiếpcủa Stack
zStack có thểđượclưutrữbởimộtvector lưutrữS, gồmn
ô nhớkếtiếp nhau
zĐỉnh stack đượcxácđịnh bởimộtchỉsốT
–T sẽ đượccậpnhậtnếucóthaotácbổsung hay loạibỏ
đượcthựchiệntrênstack
S
123 t
…
N
Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 5
Lưutrữkếtiếpcủa Stack
zGiảithuậtbổsung mộtphầntửvào Stack đượclưutrữkế
tiếpProcedure PUSH(S,T,X)
Begin
{S: vector lưutrữcó n ô nhớ; T: chỉsốcủaphầntửđỉnh stack
hiệnthời; X là giá trịcần thêm vào }
1. if T >= n then begin
write(‘STACK TRÀN’);
return;
end;
2. T:= T+1;
S[T] := X;
End
Lưutrữkếtiếpcủa Stack
zGiảithuậtlấyraphầntửởđỉnh củaStack đượclưutrữ
kếtiếp
Procedure POP(S,T, Y)
Begin
{S: stack đang xét ; T: chỉsốcủaphẩntửtạiđỉnh stack hiệnthời;
Phầntửđượclấyrasẽđượcbảolưusửdụng biếnY }
1. if T = 0 then begin
write(‘STACK CẠN’); return;
end;
2. Y:= S[T];
S[T] := null;
T:= T-1;
End