Chương IV. NGĂN XẾP (STACK) VÀ HÀNG
ĐỢI (QUEUE)
I. ĐỊNH NGHĨA STACK
Stack là 1 kiểu danh sách đặc biệt mà phép bổ sung và phép loại bỏ luôn thực
hiện ở 1 đầu; được gọi là đỉnh (top)
Có thể hình dung cơ cấu của stack như 1 chồng đĩa. Đưa thêm 1 đĩa mới vào
thì đặt nó vào đầu phía trên (đỉnh), lấy 1 đĩa ra thì cũng lấy đựơc từ đầu đó. Đĩa
đưa vào sau cùng, chính là đĩa đang nằm ở đỉnh, và nó cũng chính là đĩa sẽ được
lấy ra trước tiên. Còn đĩa đưa vào đầu tiên lại đang ở vị trí được gọi là đáy
(bottom) và chính nó là đĩa được lấy ra sau cùng.
Như vậy stack hoạt động theo cơ chế : “vào-sau-ra-trước” (last-in-first-out).
Do đó stack được gọi là danh sách kiểu LIFO. Stack có thể rỗng nghĩa là không có
phần tử nào.
II. LƯU TRỮ KẾ TIẾP ĐỐI VỚI STACK
Đó chính là cách cài đặt stack bởi 1 vectơ lưu trữ Stack, S bao gồm n ô nhớ kế
tiếp nhau. Như vậy phần tử ở đỉnh stack sẽ được định vị bởi 1 chỉ số i nào đó , mà
ta coi như 1 địa chỉ tương đối (địa chỉ thực-địa chỉ tuyệt đối-sẽ đựơc xác định như
đã nêu ở mục 2.2.2 thuộc chương 2).
Có thể coi i những giá trị của 1 con trỏ T, trỏ tới đỉnh stack. Người ta quy ước
T=0 nghĩa là stack rỗng.Như vậy, T=i thì stack có i phần tử. Rõ ràng 0≤T≤n, khi
T=n thì stack sẽ đầy, lúc đó nếu có phép bổ sung 1 phần tử mới vào stack thì sẽ
không thực hiện được, vì “không còn chỗ”; ta nói là có hiện tượng TRÀN
(Overflow) và tất nhiên việc xử lý phải ngừng lại.Còn nếu T=0 nghĩa là stack đã
rỗng, mà lại có phép loại bỏ 1 phần tử ra khỏi stack thì phép xử lý này cũng không
thực hiẹn được. Ta nói : có hiện tượng CẠN (Underflow).Sau đây là hình ảnh cài
đặt của stack với 3 phần tử :
• • • • •
S[1]
S[2]
S[3]
S
Đáy
của
stack
T
Hình 4.1
Khi bổ sung 1 phần tử mới vào thì T tăng lên 1, còn lại khi loại bỏ 1 phần tử
ra khỏi stack thì T giảm đi 1.
Hai thủ tục dưới đây thể hiện 2 phép xử lí này.
Void PUSH(S,T,X);
/*Thực hiện việc bổ sung phần tử X vào Stack, cài đặt bởi Vectơ S mà T
đang trỏ tới đỉnh*/
{
/*Kiểm tra xem Stack đã đầy chưa*/
If (T=n)
{
printf (“Stack sẽ TRÀN/n”);
return;
}
/*Chuyển con trỏ*/
T=T+1;
/*Nạp X vào*/
S[T]=X;
}
Void POP(S,T,X);
/*Thực hiện việc loại phần tử đang ở đỉnh Stack ra khỏi Stack và bảo lưu
thông tin của phần tử này vào Y*/
{
/*Kiểm tra xem Stack có cạn không*/
If (T=0)
{
printf (“Stack đã CẠN/n”);
return;
}
/*Bảo lưu thông tin của phần tử sẽ bị loại*/
Y=S[T];
/*Chuyển con trỏ*/
T=T-1;
}
III. ÁP DỤNG CỦA STACK
1. Bài toán đổi cơ số từ thập phân sang nhị phân
Ta đã biết : dữ liệu lưu trữ trong bộ nhớ của MTĐT đều được biểu diễn dưới
dạng số nhị phân (với 2 chữ só 0 và 1). Như vậy là số thập phân xuất hiện trong
chương trình đều phải chuyển đổi sang nhị phân . Trước khi xử lí và các kết quả
dưới dạng số nhị phân sẽ được đổi sang thập phân để hiển thị cho người dùng biết
(vì người dùng vốn đã quen với số thập phân rồi).
Một cách tổng quát : số thập phân bao gồm 2 phần, phần nguyên và phần
phấnó thập phân – mà ta quen gọi là phần lẻ. Việc chuyển đổi sang số nhị phân,
ứng với 2 phần, có khác nhau. Ở đây ta chỉ xét tới việc chuyển phần nguyên thôi,
hay nói cách khác : ta sẽ xét tới việc chuyển đổi 1 số nguyên dưới dạng thập phân
sang nhị phân.
Trước hết ta cần thấy rằng :
Ở dạng số thập phân 274 biểu diễn cho con số có giá trị là:
2 . 102 + 3 . 101 + 4 . 100
Nếu đem con số này chia cho 10 và để ý tới các số dư ta sẽ thấy:
Mã số 274 chính là dạng hiển thị của các số dư, theo thứ tự xuất hiện và
ngược lại.
Tương tự như vậy, mã số nhị phân của 1 con số, cho dưới dạng thập phân,
cũng sẽ được xác định với phép chia và lấy số dư, chỉ có khác là bây giờ thực hiện
phép chia với 2 và dư số sẽ là số 0 hoặc 1 thôi.
Như vậy rõ ràng là trong cách chuyển đổi này các số dư đã được tạo ra sau
lại hiển thị trước. Cơ chế sắp xếp này rất phù hợp với cơ chế hoạt động của stack.
Vì vậy trong giải thuật chuyển đổi số nguyên từ thập phân sang nhị phân, người ta
thường sử dụng 1 stack để lưu trữ số dư, sau đó lại lấy các số này lại từ stack để
hiển thị thành mã số nhị phân.
Giả sử stack được cài đặt bởi 1 vectơ lưu trữ S, mà T là con trỏ, trỏ tới đỉnh;
lúc đầu stack rỗng, nghĩa là T=0.
Có thể viết giải thuật chuyển đổi 1 số nguyên N sang dạng nhị phân bằng
thủ tục như sau :
Void CHANGE(N);
{
m=N
/*Tính số dư và nạp vào Stack(S)*/
While m!=0
{
R=m mod 2; /*Tính số dư*/
PUSH(S,T,R); /*Nạp R vào Stack S*/
M=m div 2; /*Thay m bằng thương của phép chia m cho 2*/
}
/*Hiện thử từng chữ số nhị phân trong mã số biểu diễn N*/
While T!=0
{
Call POP(S,T,X); /*Lấy số ra khỏi Stack */
Printf(X);
}
}
Ví dụ:
N=39
Ta có mã số nhị phân biểu diễn chp số 39 : 100111
Khi thực hiện CHANGE(N) thì:
2. Biểu thức số học với kí pháp BA _ LAN
Ta xét 1 biểu thức số học với các phép toán 2 ngôi như các phép : cộng(+),
trừ(-), nhân(∗), chia(/), luỹ thừa(↑) v.v…
39
2
19
2
9
2
4
2
2
2
1
2
0
Số dư
được nạp
vào Stack
S
1
1
1
1
1
1
1
1
1
0
1
1
1
0
0
1
1
1
0
0
1
Lấy số từ
Stack ra để
hiển thị
1
1
1
1
1
1
1
1
1
0
1
1
1
0
0
1
0
0
1
1
1
Hình 4.2
Ta thấy, với phép toán này thì toán tử (dấu phép toán) bao giờ cũng đặt ở
giữa 2 toán hạng (vì vậy ta nói : biểu thức số học thông thường được viết theo kí
pháp trung tố (ifix notation). Với kí pháp này thì nhiều khi để phân biệt 2 toán
hạng ứng với 1 toán tử ta bắt buộc phải dùng các cặp dấu ngoặc đơn hoặc nếu
không thì phải chấp nhận 1 thứ tự ưu tiên giữa các phép toán như đã được qui
định trong các ngôn ngữ lập trình. Cụ thể là thứ tự ưu tiên được xếp theo trình tự
sau :
1. Phép luỹ thừa
2. Phép nhân, phép chia
3. Phép cộng, phép trừ
Các phép toán cùng thứ tự ưu tiên thì sẽ được thục hiện theo trình tự : trái
trước, phải sau (trong biểu thức).
Ví dụ : A + B ∗ C – D
sẽ được thực hiện theo trình tự :
B ∗ C
rồi A +(B ∗ C)
và cuối cùng là : (A +(B ∗ C)) – D
tương tự như vậy
A ∗ B↑ – C / D + E
sẽ được thực hiện :
B↑
rồi : A ∗ (B↑)
C / D
A ∗ (B↑) – (C / D)
cuối cùng là :
(A ∗ (B↑) – (C / D)) + E
(Chú ý là : dấu ngoặc trong cách viết trên ta thêm vào để phân biệt toán hạng
ứng với 1 toán tử).
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
và 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
khá “cồng kềnh”.
Trong những năm đầu 1950, nhà toán học Ba Lan : Jan Lukasiewcz đã đưa
ra dạng kí pháp mới để biểu diễn các biểu thức mà không cần tới dấu ngoặc, đó là
kí pháp tiền tố (preix notation) và hậu tố (postfix notation) mà gọi chung là kí
pháp Ba – Lan (Polish notation)
a. Biểu thức dạng tiền tố và hậu tố