Bài giảng Cấu trúc dữ liệu và giải thuật - Ngăn xếp

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Ngăn xếp

1. 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. 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);
3. 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. 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 a1 2 a2 . . . top an max
5. Const max = N; Type Item = ; Stack = record Top: 0 max; Element array[1 max] of Item; End; Var S: stack;
6. - 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;
7. 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;
8. Biểu diễn phép toán PUSH trên hình vẽ sau: 1 a1 1 a1 1 a1 2 a2 2 a 2 a2 2 . . . . . . . . . top a n an n n an top top x max max max
9. 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;
10. 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;
11. - 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;
12. 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;
13. s an an-1 a1
14. 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;