SỞ GD & ĐT THANH HOÁ
Thực hiện: Nguyễn Đặng Phú
Trong thiết kế nhiều loại chương trình, việc chọn cấu trúc dữ liệu là vấn đề quan trọng. Kinh nghiệm trong việc xây dựng các hệ thống lớn cho thấy khó khăn của việc triển khai chương trình, chất lượng và hiệu năng của kết quả cuối cùng phụ thuộc rất nhiều vào việc chọn cấu trúc dữ liệu tốt nhất. Sau khi cấu trúc dữ liệu được chọn, người ta thường dễ nhận thấy thuật toán cần sử dụng. Đôi khi trình tự công việc diễn ra theo thứ tự ngược lại: cấu trúc dữ liệu được chọn do những bài toán quan trọng nhất định có thuật toán chạy tốt nhất với một số cấu trúc dữ liệu cụ thể. Trong cả hai trường hợp, việc lựa chọn cấu trúc dữ liệu là rất quan trọng.
I.MỞ ĐẦU
Các cấu trúc dữ liệu thường dùng:
■ Mảng
■ Ngăn xếp
■ Hàng đợi
■ Danh sách liên kết
■ Cây
■ Đồ thị

II. ĐỊNH NGHĨA
Stack là một kiểu danh sách tuyến tính đặc biệt mà phép
bổ sung và phép loại bỏ luôn luôn thực hiện ở một đầu gọi là
đỉnh (top)
Có thể hình dung nó như cơ cấu của một hộp chứa đạn
súng trường hoặc súng tiểu liên. Lắp đạn vào hay lấy đạn ra
cũng chỉ ở một đầu hộp. Viên đạn mới nạp vào sẽ nằm ở đỉnh
còn viên nạp đầu tiên sẽ nằm ở đáy.Viên đạn vào sau cũng
chính là viên lên nòng súng trước tiên
Nguyên tắc “vào sau ra trước” như vậy của stack đã đưa tới
một tên gọi khác: danh sách kiểu LIFO. Stack có thể rỗng hoặc
bao gồm một số phần tử.
1
2
3
4
4
II. ĐỊNH NGHĨA
III. LƯU TRỮ STACK BẰNG MẢNG (LƯU TRỮ KẾ TIẾP)
Có thể lưu trữ Stack bởi một véc tơ lưu trữ S gồm n phần tử
nhớ kế tiếp. Nếu T là địa chỉ của phần tử đỉnh của Stack thì T
sẽ có giá trị biến đổi khi Stack hoạt động (vì vậy người ta gọi
T là một biến trỏ-variable pointer). Nếu ta quy ước dùng địa chỉ
tương đối (như chỉ số) thì khi Stack rỗng T=0. Khi một phần tử
mới bổ sung vào Stack, T sẽ tăng lên 1. Khi một phần tử bị loại
ra khỏi Stack, T sẽ giảm đi 1.
Có thể thấy cấu trúc dữ liệu của Stack như hình sau:
1
2
3
4
5
III. LƯU TRỮ STACK
► Giải thuật bổ sung đối với Stack:
{Giải thuật bổ sung phần tử X vào Stack lưu trữ bởi véc tơ S có n phần tử. Ở đây T là con trỏ, trỏ tới đỉnh Stack }
1. {Xét xem Stack có TRÀN(overflow) không? Hiện tượng
TRÀN xảy ra khi S không còn chỗ để tiếp tục lưu trữ các phần
tử của Stack nữa. Lúc này sẽ thông báo TRÀN và kết thúc. }
If T>=n then
begin
write(‘STACK TRÀN’);
return
end;
2. {Chuyển con trỏ}
T:=T+1;
3. {Bổ sung phần tử mới X}
S[T]:=X;
4. return
♦Procedure PUST(S,T,X)
III. LƯU TRỮ STACK
♦ Procedure POP(S,T,Y)
► Giải thuật loại bỏ đối với Stack:
{Giải thuật này thực hiện việc loại bỏ phần tử ở đỉnh Stack
S đang trỏ bởi T. Phần tử bị loại sẽ được thu nhận và đưa ra
bởi Y}
1.{Xét xem Stack có CẠN (underflow) không? Hiện tượng
CẠN xảy ra khi Stack đã rỗng, không còn phần tử nào để loại
nữa, lúc đó sẽ in ra thông báo cạn và kết thúc }
If T<=0 then
begin
write(‘STACK CẠN’);
return
end;
3. {Đưa phần tử bị loại ra}
Y:=S[T+1]
2. {Chuyển con trỏ}
T:=T-1;
4. return
III. LƯU TRỮ STACK
* Chú ý: Xử lý với nhiều Stack:
Có những trường hợp cùng một lúc ta phải xử lý nhiều Stack
Như vậy có thể xảy ra tình trạng một Stack này đã bị tràn trong
khi không gian dự trữ cho Stack khác vẫn còn chỗ trống (Tràn
cục bộ).
Làm thế nào để khắc phục được?
Nếu là 2 Stack thì có thể giải quyết dễ dàng. Ta không quy
định kích thước tối đa cho từng Stack nữa mà không gian nhớ
dành ra sẽ được dùng chung. Ta sẽ đặt hai Stack ở 2 đầu sao
cho hướng phát triển của chúng ngược nhau.
Như vậy có thể một Stack này dùng lấn sang quá nửa không gian dự trữ nếu như Stack kia chưa dùng đến. Do đó hiện tượng Tràn chỉ xảy ra khi toàn bộ không gian nhớ dành cho chúng đã được dùng hết.
III. LƯU TRỮ STACK
Nhưng nếu số lượng Stack từ 3 trở lên thì không thể làm
theo kiểu như vậy được, mà phải có một giải pháp linh hoạt
hơn. Chẳng hạn có 3 Stack, lúc đầu không gian nhớ có thể
chia đều cho cả 3.
Nhưng nếu có một Stack nào đó phát triển nhanh bị TRÀN
trước mà Stack khác vẫn còn chỗ thì phải dồn chỗ cho nó bằng
cách đẩy Stack đứng sau sang phải hoặc lùi chính Stack đó
sang trái trong trường hợp có thể. Như vậy thì đáy của các
Stack phải được phép di động và dĩ nhiên các giải thuật bổ
sung và loại bỏ phần tử đối với các Stack hoạt động theo kiểu
này cũng phải thay đổi theo
III. LƯU TRỮ STACK
IV. ỨNG DỤNG CỦA STACK
► Đổi cơ số
Ta biết rằng dữ liệu lưu trữ trong bộ nhớ của MTĐT đều được biểu diễn nhị phân. Như vậy nghĩa là các số xuất hiện trong chương trình đều phải chuyển đổi thập phân sang nhị phân trước khi thực hiện các phép xử lý.
Khi đổi một số nguyên từ thập phân sang nhị phân thì người
ta dùng phép chia liên tiếp cho 2 và lấy số dư (là các chữ số nhị phân) theo chiều ngược lại.
IV. ỨNG DỤNG
Ví dụ: đổi số 26 sang số nhị phân
Như vậy rõ ràng trong các biến đổi này các số dư được tạo
ra sau lại được hiển thị trước. Cơ chế sắp xếp này chính là cơ
chế của Stack. Để thực hiện biến đổi ta sẽ dùng một Stack để
lưu trữ số dư qua từng phép chia: khi thực hiện phép chia thì
nạp số dư vào Stack, sau đó lấy chúng lần lượt từ Stack ra để
hiển thị.
IV. ỨNG DỤNG
(01011)
IV. ỨNG DỤNG
*Giải thuật chuyển đổi như sau:
Program CHUYEN_DOI
{Giải thuật này thực hiện chuyển đổi biểu diễn cơ số 10 của
một số nguyên dương N sang cơ số 2 và hiển thị biểu diễn cơ
số 2 này}
1. Read(N);
2. While N ≠ 0 do
begin
R:= N mod 2;{Tính số dư R trong phép chia N cho 2}
call PUSH(S,T,R); {nạp R vào đỉnh Stack S}
N:=N div 2;{Thay N bằng thương của phép chia N cho 2}
end;
3. While S chưa rỗng do
begin
call POP(S,T,R);
write(R);
end;
4. return
IV. ỨNG DỤNG
►Biểu thức số học và ký pháp BaLan
1. Đặt vấn đề
Thông thường, trong các biểu thức số học,với phép toán 2
ngôi như phép cộng, phép trừ, phép nhân, phép chia phép luỹ
thừa (ký hiệu bởi )…dấu phép toán (toán tử) bao giờ cũng
được đặt ở giữa 2 toán hạng (ký pháp trung tố).
Với cách biểu diễn này, việc sử dụng các cặp dấu ngoặc để
phân biệt các toán hạng (cũng là để phân biệt thứ tự thực hiện
các phép toán) là cần thiết.
Ví dụ: Hai biểu thức sau:
a) (A+B)*C b) A+(B*C).
là hoàn toàn khác nhau. Với a) thì phép cộng được thực hiện
trước rồi mới tới phép nhân, còn với b) thì ngược lại.
Trong trường hợp không muốn dùng dấu ngoặc thì lại phải
theo quy ước về thứ tự ưu tiên thực hiện các phép toán, như
đã quy định trong các ngôn ngữ lập trình.
IV. ỨNG DỤNG
Ví dụ : Với biểu thức:
A+B*C-D/E F
thì thứ tự thực hiện sẽ như sau:
♦ E F
♦ A+(B*C)
♦ B*C
♦ D/(E F)
♦ (A+B*C)-(D/E F)
Rõ ràng cách viết biểu thức theo ký pháp trung tố với việc sử
dụng dấu ngoặc hoặc thứ tự ưu tiên giữa các phép toán đã
khiến cho việc tính toán giá trị biểu thức trở nên “cồng kềnh”
Nhà toán học BaLan J.Lukasiewicz là người đầu tiên phát
hiện rằng dấu ngoặc là không cần thiết, thông qua cách biểu
diễn biểu thức số học theo ký pháp hậu tố hoặc tiền tố mà gọi
chung là ký pháp BaLan
IV. ỨNG DỤNG
2. Biểu thức dạng hậu tố và tiền tố
Với ký pháp hậu tố toán tử được đặt sau toán hạng một và
toán hạng hai.
Ví dụ:
A+B thì dưới dạng hậu tố sẽ được viết là AB+
E/F - EF/
(A+B)*C - AB+C*
A+B*C - ABC*+
Với ký pháp tiền tố thì việc đặt toán tử sẽ ngược lại
Ví dụ:
A+B thì dưới dạng tiền tố sẽ được viết là +AB
E/F - /EF
A+B*C - +A*BC
(A+B)/(C-D)+E - +/+AB-CDE
Dựa theo quy tắc của các ký pháp nêu trên, ta có thể viết
được biểu thức dưới dạng hậu tố, hoặc tiền tố nếu như từ dạng
trung tố, với mỗi toán tử ta xác định được toán hạng 1 và toán
hạng 2 ứng với nó.

IV. ỨNG DỤNG
3. Tính giá trị của biểu thức dạng hậu tố
Xét một biểu thức dạng hậu tố, và để đơn giản, ta giả sử
rằng: mỗi ký tự trong biểu thức (xâu ký tự) biểu diễn cho một
Biến, hằng hoặc toán tử
Để ý ta sẽ thấy: khi duyệt biểu thức từ trái sang phải, hễ gặp
một toán tử thì hai toán hạng đứng sát ngay trước nó sẽ được
tác động bởi toán tử này để tạo thành một toán hạng mới cho
toán tử gặp tiếp theo.
Do đó việc tính giá trị của một biểu thức hậu tố có thể thực
hiện theo các bước sau:
B1: Đọc biểu thức hậu tố từ trái qua phải:
-Nếu ký tự được đọc X là toán hạng thì bảo lưu giá trị.
-Nếu ký tự được đọc X là toán tử thì 2 giá trị vừa được bảo
lưu sẽ lần lượt được lấy ra và tác động toán tử X vào giữa
giá trị lấy ra sau với giá trị lấy ra trước và bảo lưu kết quả lai.
B2: Lặp lại bước 1 cho đến khi kết thúc biểu thức. Giá trị
cuối cùng được bảo lưu, chính là giá trị của biểu thức.
IV. ỨNG DỤNG
* Giải thuật tính giá trị của biểu thức hậu tố
Procedure EVAL(P,VAL)
{Thủ tục này tính giá trị của biểu thức hậu tố P, tương ứng với
giá trị của các biến; kết quả sẽ được gán cho VAL. Ở đây có sử
dụng một Stack S với T trỏ tới đỉnh; thoạt đầu T=0(Stack rỗng)}
1. Ghi thêm dấu “)” vào cuối biểu thức P làm dấu kết thúc;
Repeat
Đọc ký tự X trong P, khi duyệt từ trái qua phải;
if X là một toán hạng then
call PUSH(S,T,X)
else
begin
call POP(S,T,Y);
call POP(S,T,Z);
W:=Z(X)Y; {(X) chỉ toán tử X}
call PUSH(S,T, W);
end;
until gặp dấu kết thúc”)”;
3. call POP(S,T,VAL);
4. return
IV. ỨNG DỤNG
Với biểu thức hậu tố AB+CDA+ -*
Nếu A=1; B=5; C=8; D=4
thì hình ảnh của Stack S, khi tính giá trị biểu thức sẽ như sau:
Ví dụ minh hoạ:
IV. ỨNG DỤNG
4. Chuyển đổi biểu thức từ dạng trung tố sang hậu tố
Trong biểu thức dạng trung tố nếu xuất hiện dấu ngoặc mở “(” thì phải có dấu ngoặc đóng “)” tương ứng với nó, với các cặp dấu ngoặc lồng nhau thì dấu ngoặc mở gặp trước lại tương ứng với dấu ngoặc đóng gặp sau. Ngoài ra khi gặp toán tử thì phải chờ xác định được toán hạng 2 rồi mới đặt toán tử này vào sau toán hạng 2. Vì vậy trong giải thuật chuyển đổi người ta phải sử dụng một Stack để bảo lưu dấu ngoặc mở (để chờ dấu ngoặc đóng tương ứng) và toán tử (để chờ toán hạng 2 tương ướng).
IV. ỨNG DỤNG
* Giải tuật chuyển đổi biểu thức trung tố sang biểu thức hậu tố
Procedure POLISH(Q,P);
{Q là biểu thức viết dưới dạng trung tố, giải thuật này biến đổi Q sang dạng hậu tố P, thoạt đầu P rỗng }
Thêm dấu “)” vào cuối Q; {để làm dấu kết thúc}
call PUSH(S,T,”)”); {dấu ngoặc mở này tương ứng với dấu
ngoặc đóng mới thêm vào cuối Q}
2. Repeat
Đọc ký tự X trong Q khi duyệt từ trái qua phải;
Case
X là toán hạng: Bổ sung thêm X vào P;
X là dấu ngoặc mở : call PUSH(S,T,”(”);
X là toán tử : While thứ tự ưu tiên của S[T]>= thứ tự
ưu tiên của do
begin
call POP(S,T, W);
bổ sung thêm W vào P
end;
X
X
Call PUSH(S,T,” ”);
X
IV. ỨNG DỤNG
X là dấu ngoặc đóng:
repeat
call POP(S,T, W);
Bổ sung thêm W vào P;
until gặp dấu “(”;
loại dấu “(” ra khỏi tack S;
End case
Until Stack rỗng;
3. return
IV. ỨNG DỤNG
Ví dụ: Q:=(A+B)*C+D.
Áp dụng giải thuật POLISH ta có bảng minh hoạ sau: