Thuật toán ngăn xếp - Stack

Kiểu dữ liệu ngăn xếp Stack trong Turbo Pascal
Bùi Văn Tân
Các bạn yêu thích lập trình thân mến! Chắc các bạn không xa lạ gì với cấu trúc dữ liệu kiểu
ngăn xếp (Stack) hoạt động theo cơ chế First In Last Out. Stack là một cấu trúc dữ liệu cơ
bản có ứng dụng nhiều trong việc giải quyết các bài toán tin học. Nó có vai trò đặc biệt
trong các thuật toán duyệt và khử đệ quy… Stack được coi như một kiểu dữ liệu trừu
tượng với hai thao tác cơ bản là đưa một phần tử vào đỉnh Stack (Push) và lấy ra một phần
tử từ đỉnh Stack (Pop). Điều đáng nói là chính vì Stack rất hay dùng nên mỗi lần giải một
bài toán cần dùng đến cấu trúc dữ liệu Stack thì ta lại phải cài đặt Stack. Điều này làm tốn
kém thời gian và hơn nữa làm thuật toán chính giải quyết bài toán trở nên phức tạp và
rườm rà. Mình xin chia sẻ cùng các bạn cách cài đặt Stack trở thành một kiểu dữ liệu của
Pascal (TP70) bằng cách tạo một Unit khai báo kiểu dữ liệu StackType. Sau đây là chương
trình mô tả Unit Stack.pas.
Unit Stack
Interface
Uses crt;
Type
StackType = object
Top: integer; {con trỏ đỉnh Stack}
elementize: integer; {kích thước một phần tử dữ liệu}
Data: array[1..32767] of byte;
Procedure init(size: integer);
Function Empty: boolean;
Function Full: boolean;
Procedure Push(var Item);
Procedure Pop(var Item);
End;
Implementation
{ *** Phương thức khởi tạo Stack *** }
Procedure StackType.Init(size: integer);
Begin
Top: =0; {Khởi tạo con trỏ Stack}
Fillchar(Data,sizeof(Data),0); Elementsize:=size; {Khởi tạo kích thước của một phần tử
Stack}
End;
{ *** Phương thức kiểm tra Stack rỗng *** }
Function StackType.Empty: boolean;
Begin
Empty: =(top=0);
End;
{ *** Phương thức kiểm tra Stack đầy *** }
Function StackType.Full: boolean;
Begin
Full:=(top + elementsize> 32767);
End;
{ *** Phương thức đưa một phần tử vào Stack *** }
Procedure StackType.Push (var Item);
Var i:integer;
Tem: array[1..1] of byte Absolute Item;
Begin
If not (Full) then
Begin
For i:=1 to elementsize do
Data[top + i]: =Tem[i];
Top: = top +elementsize;
End Else Write(‘Over Stack’);
End;
{ *** Phương thức lấy một phần tử ra khỏi Stack *** }
Procedure StackType.Pop(var Item);
Var i: integer;
Tem:array[1..1] of byte Absolute Item;
If not (empty) then
Begin
For i:=1 to elementsize do
Tem[i]: =Data[top-elementsize + i];
Top:=top – elementsize;
End Else Writeln(‘ Empty Stack’);
End;
End {end of Unit}
- Trên đây là toàn bộ chương trình nguồn của Unit Stack.Pas được viết bằng TP70 có sử
dụng kĩ thuật lập trình hướng đối tượng. Các bạn hoàn toàn có thể chuyển đổi các phương
thức thành các thủ tục và hàm để áp dụng kĩ thuật lập trình cấu trúc truyền thống.
- Các bạn có thể áp dụng kĩ thuật mảng động, khai thác vùng nhớ động (HEAP) để Stack
có kích thước lớn và hữu dụng hơn. Ở đây chương trình hoàn toàn mang tính giới thiệu
phương pháp.
- Sau khi biên dịch unit Stack.pas ta thu được unit Stack.tpu. Bây giờ, bạn hoàn toàn có thể
khai báo các biến kiểu StackType với một lưu ý là trước khi dùng bạn phải gọi phương
thức INIT để khởi tạo.
- Sau đây là một ví dụ áp dụng kiểu dữ liệu Stack để lưu trữ một danh sách sinh viên.
{ demo.pas }
Program demo_Stacktype;
Uses crt, stacktype; {nhớ khai báo sử dụng Unit Stacktype}
Type
Sinhvien=record Name: string[20]; Diem: integer;
End;
Var ch: char; sv: sinhvien; s: Stacktype;
Begin
Clrscr;
S.Init(sizeof(sinhvien));{bạn nhớ phải khởi tạo Stack}
repeat
Write( ‘nhap ho ten: ’ ) ; readln(sv.name);
Write( ‘Nhap diem: ’ ) ; readln(sv.diem);
Write( ‘ban co tiep tuc khong y/n’ ) ; ch:=readkey;
Until ch in [‘k’, ‘K’, ‘n’, ‘N’];
While not ( s.empty ) do
Begin
S.Pop(sv);
Writeln( sv.name: 20, sv.diem:14 ) ;
End;
Readln;
End.
Trên đây là chương trình mang tính mô tả phương pháp thực hiện. Các bạn có thể sử dụng
kỹ thuật mảng động khai thác vùng nhớ để có được Stack với kích thước lớn và hữu dụng
hơn. Mình rất mong được sự đóng góp ý kiến của các bạn gần xa.