Ngăn X pế
1. Đ nh nghĩa
ị
ộ ạ
Ngăn x p là m t d ng c a danh sách, trong đó phép toán ủ m i vào danh sách và lo i b m t ph n t ầ ử m t đ u c a ủ
ạ ỏ ộ ệ ở ộ ầ c phép th c hi n ự ỉ ượ ỏ
ế xen m t ph n t ầ ử ớ ộ kh i danh sách ch đ danh sách.
2. Các phép toán trên danh sách
ỗ ở ạ
ể ế ỗ
ể
ế ỉ
ủ ầ đ nh c a ngăn x p và gán giá tr c a ph n ị ủ ế
1 kh i t o danh sách r ng Procedure intialize(var s: stack); 2 ki m tra ngăn x p r ng. Function empty (var s: stack):boolean; 3 ki m tra ngăn x p đ y ế ầ Function full (var s: stack):boolean; 4 Thêm m t ph n t x vào đ nh c a ngăn x p ủ ầ ử ộ Procedure push(x: Item, var s: stack) 5 Lo i ph n t ạ ầ ử ở ỉ này cho x t ử
Procedure pop(var s: stack, var x: item);
ế Ví d :ụ N u S là ngăn x p, S=(a ế ở
ệ ả
1, a2, ... an) và đ nh c a ngăn x p ỉ 1, a2, ... an, ượ 1, a2, ... an-1) ượ
ủ c S=(a c S=(a ự ệ
ế đ u bên ph i. khi th c hi n push(x,S) ta đ ự ầ x). n u n>=1 thì khi th c hi n pop(S,x) ta đ ế và x=an.
4 Cài đ t danh sách b i m ng
ở ả
ặ
Ngăn x p S= (a ế
ượ
c bi u di n b i m ng nh hình sau: ả
ư
ễ
ể
ở
1, a2, ... an) đ
1
a1
2
a2
. . .
top
an
max
Const max = N; Type Item =.......; Stack = record Top: 0...max;
Element array[1..max] of Item;
End; Var S: stack;
ế ự ủ ụ
- Các th t c và hàm th c hi n các phép toán trên ngăn x p. ệ Procedure initialize(S:Stack); Begin s.top: = 0; end; function Empty(var S:Stack):boolean; begin Empty:=(s.top=0); End; Function Full(var S: stack):boolean; Begin Full: =(s.top=max); End;
Procedure push( x:Item, var S: Stack, var ok : boolean); Begin With s do If full(S) then ok:=false Else Begin
Top:=top+1; Elment[top]:=X; Ok:=true;
End;
End;
ễ
ể
Bi u di n phép toán PUSH trên hình v ẽ sau:
1
1
1
a1
a1
a1
2
2
2
a2
a2
a2
. . .
. . .
. . .
top
n
an
an
n
an
x
top
top
max
max
max
Procdure pop(var S:Stack, var X:Item, var ok:boolean); Begin
With S do If empty(S) then ok:= false Else Begin
X:=Element[top];
Top:=top-1; Ok:=true;
End; End;
5. Cài đ t ngăn x p b i danh sách liên k t ế
ế ở
ặ
S
an
an-1
a1
...
Type Stack = ^cell; Cell = record Infor: Item; Next: Stack;
End; Var S: Stack;
c cài ủ ụ ế ượ
- Các th t c và hàm th hi n phép toán trên ngăn x p đ ể ệ ế . đ t b i danh sách liên k t ặ ở
Procedure initialize(Var S:Stack);
Begin
S := NIL;
end; Function Empty(VarS:Stack):Boolean;
Begin
Empty := (S = NIL);
End;
S
X
...
P
Procedure PUSH(Var S : Stack; X : Item, Var ok : boolean); Var P : Stack; Begin New(P); P^.Info := X; p^.Next := S; S := P; ok:= true; End;
s
…
an
an-1
a1
Procedure POP(Var S : Stack; Var X : Item; Var OK : Boolean); Var P : Stack; Begin If Empty(S) Then OK := False Else begin P := S; X := S^.Info; S := S^.Next; OK := True; Dispose(P); end; End;
