Bài giảng Cơ sở dữ liệu: Ngăn xếp
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
xen một phần tử mới vào danh sách và loại bỏ một phần tử
khỏi danh sách chỉ được phép thực hiện ở một đầu của danh
sách.
2. Các phép toán trên danh sách
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ử ở đỉnh của ngăn xếp và gán giá trị của phần tử
này cho x
Procedure pop(var s: stack, var x: item);
Ví dụ: Nếu S là ngăn xếp, S=(a1, a2, ... an) và đỉnh của ngăn xếp ở
đầu bên phải. khi thực hiện push(x,S) ta được S=(a1, a2, ... an, x).
nếu n>=1 thì khi thực hiện pop(S,x) ta được S=(a1, a2, ... an-1) và
x=an.
4 Cài đặt danh sách bởi mảng
Ngăn xếp S= (a1, a2, ... an) được biểu diễn bởi mảng như hình sau:
1
2
a1
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
a1
1
2
a1
a2
1
2
a1
a2
2
a2
.
.
.
.
.
.
.
.
.
n
an
top
an
n
an
top
x
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 thủ tục và hàm thể hiện phép toán trên ngăn xếp được cài
đặ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;
15 trang
23360
Free
Bạn đang xem tài liệu "Bài giảng Cơ sở dữ liệu: Ngăn xếp", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_co_so_du_lieu_ngan_xep.ppt
