Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 1
Cấutrúcdữ liệuvàGiảithuật
Chương III:
Stack và Queue
Danh sách kiểungănxếp - Stack
– Stack
z Mộtkiểudanhsáchtuyến tính đặc
biệt
z Phép bổ sung và phép loạibỏ tuân
thủ theo cơ chế “vào sau ra trước”
(last in first out) , đượcthựchiện ở
đầu đỉnh
đỉnh
đáy
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 2
Danh sách kiểungănxếp - Stack
– Hai thao tác cơ bản đốivới danh sách kiểungăn
xếp
z push(Element e) : bổ sung phầntử vào Stack
z Element pop(): Loạibỏ và trả ra giá trị củaphầntửở
đỉnh Stack
– Các thao tác khác
z Int size(): Trả ra số các phầntử trong Stack
z Boolean isEmpty(): KiểmtraxemStack córỗng không
z Element top(): Trả ra giá trị củaphầntửởđỉnh Stack
Các thao tác cơ bảncủa Stack
Top

[9,8,7]-push(7)
[9,8]-push(8)
[9]-push(9)
[]trueisEmpty()
[]5pop()
[5]7pop()
[5,7]7top()
[5,7]-push(7)
[5]3pop()
[5,3]-push(3)
[5]-push(5)
[ ]-create()
StackOutputThao tác
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 4
Ứng dụng củaStack
– Lưutrữ các trang web đãtừng được duyệttrên
Web browser
– Cài đặt thao tác Undo trong các phầnmềmsoạn
thảo
– Lưudanhsáchcáclờigọi hàm trong Java Virtual
Machine
Lưutrữ kế tiếpcủa Stack
z Stack có thểđượclưutrữ bởimộtvector lưutrữ S, gồmn
ô nhớ kế tiếp nhau
z Đỉnh stack đượcxácđịnh bởimộtchỉ số T
– T sẽ đượccậpnhậtnếucóthaotácbổ sung hay loạibỏ
đượcthựchiệntrênstack
S

end;
2. Y:= S[T];
S[T] := null;
T:= T-1;
End
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 6
Hiệunăng và Hạnchế
z Hiệunăng
– n là số phầntử củastack
– Không gian lưutrữ : O(n)
– Cácthaotáccơ bảncóđộ phứctạpO(1)
z Hạnchế
– Kích thướctối đaphải đượcxácđịnh trướcvà
không được thay đổi
– Xảyratrànstack
Lưutrữ móc nối đốivới Stack
– Cách tiếpcận1
z Đỉnh của Stack được coi là phầntử nằm ởđầu danh sách
z pop() : Lấyraphầntửđầu tiên trong danh sách móc nối
z push(o) : Bổ sung mộtphầntử vào đầudanhsáchmócnối
Đỉnh Stack
L
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 7
Lưutrữ móc nối đốivới Stack
Đỉnh Stack
L

Lưutrữ móc nối đốivới Stack
– Loạibỏ nút
int pop ( STACKNODEPTR *top) {
int item; STACKNODEPTR temp;
temp = *top;
item = (*top)->item;
*top = (*top)->next;
free (temp);
return item;
}
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 9
Danh sách kiểuhàngđợi-Queue
z Queue
z Queue (Hàng đợi) là mộtkiểu
danh sách tuyến tính đặcbiệt
z Phép bổ sung và loạibỏ hoạt
động theo cơ chế “vào trước
ra trước” (first in first out) ; bổ
sung ở một đầuthìloạibỏở
đầukia
lốisau
lối
trước
Danh sách kiểuhàngđợi-Queue
– Hai hàm cơ bản đốivới danh sách kiểuhàngđợi
z enqueue(Element e)
z Element dequeue()
– Các hàm khác

– Sử dụng mộtvector lưutrữ Q gồmn ô nhớ kế tiếpnhauđể
biểudiễnmột Queue
– Cầnnắm được hai chỉ số
 R: Chỉ số củaphầntử nằm ở lốisaucủaQ
 F: Chỉ số củaphầntửởlốitrướccủaQ
Q
1
23 rf
Lưutrữ kế tiếp đốivớiQueue
z Khi Queue rỗng thì F = R = 0
z Khi bổ sung thêm mộtphầntử vào Queue thì R tăng lên 1
z Khi lấyramộtphầntử trong Queue thì F tăng lên 1
z Nhược điểmcủacáchtổ chứclưutrữ này
– Các phầntử trong Queue sẽ dịch chuyểnkhắpkhônggiannhớ
nếuliêntụcthựchiệnbổ sung rồiloạibỏ
– Hiệntượng TRÀN vẫnxảy ra khi vector lưutrữ Q vẫncònchỗ
nhưng R = n
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 12
Lưutrữ kế tiếp đốivớiQueue
z Khắcphụccácvấn đề bằng cách coi vector lưutrữ
Queue đượctổ chứcdướidạng vòng
– Q[1] được coi nhưđứng sau Q[n]
F
R
Q[1]
Q[2]
Q[3]
Q[n]

z Giảithuậtbổ sung vào Queue đượclưutrữ trong vector Q
gồmn phầntử và đượctổ chứcdướidạng thường
Procedure ENQUEUE(Q,F,R,X)
Begin
1. if (R >= n) then begin
write(‘QUEUE TRÀN’);
return;
end;
2. {Q rỗng} if F = 0 then F:= R:= 1;
3. else R:= R+ 1;
4. Q[R] := X;
End
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 14
Lưutrữ kế tiếp đốivớiQueue
z Giảithuậtlấyra(loạibỏ ) khỏi Queue
Procedure DEQUEUE(Q,F,R, Y)
Begin
{ Y là biếnlưutrữ phầntửđượclấyra}
1. if F = 0 then begin
write(‘QUEUE CẠN’);
return;
end;
2. Y:= Q[F]; {lưu giá trị củaphầntử cầnlấy}
3. if F = R=1 then F:= R:= 0; { Queue chỉ còn mộtphầntử}
4. else F:= F+ 1;
End
Lưutrữ kế tiếp đốivớiQueue
z Bài tập: Hãy viếtgiảithuậtthựchiệnbổ sung và loạibỏ

Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 16
Lưutrữ móc nối đốivới Queue
z Giảithuậtbổ sung mộtphầntử vào Queue lưutrữ trong
danh sách móc nối–Bổ sung vào cuối danh sách
Procedure ENQUEUE(F,R,X)
Begin
1. {Khởitạo nút mới} Call New(p);
INFO(p) := X; LINK(p) := Null;
2. {Danh sách đã cho rỗng} if F = Null then F:= R:= p;
3. else LINK(R) := p; R:= p;
End
Lưutrữ móc nối đốivới Queue
z Giảithuậtloạibỏ phầntử khỏi Queue – Loạibỏ phầntử
đầu tiên trong danh sách
Procedure DEQUEUE(F,R, Y)
Begin
{ Y là biếnlưutrữ phầntửđượclấyra}
1. p:= F; Y:= INFO(p);
2. {Danh sách ban đầuchỉ có mộtphầntử}
if (F = R) and (F <> Null) then F:= R:= Null;
2. else F:= LINK(p);
3. Call Dispose(p) ;
End
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 17
Hàng đợihaiđầu-DEQueue
z DeQueue

nội 18
Lưutrữ móc nốivới DeQueue
z DeQueue đượclưutrữ sử dụng cấu trúc danh sách
móc nối kép (Doubly Linked – List)
– Mỗi nút trong danh sách ngoài trường INFO chứadữ
liệucòncó2 trường con trỏ
z PREV
z NEXT
– Cầnnắm được hai con trỏ, con trỏ L trỏ tớinútcực
trái, con trỏ R trỏ tới nút cựcphảicủa danh sách
– Với danh sách rỗng , L = R = NULL
L
BCGH
R
Lưutrữ móc nối đốivới DeQueue
z Giảithuậtbổ sung phầntử vào đầumột DeQueue lưu
trữ trong một danh sách nốikép
z Giảithuậtloạibỏ phầntửđầumột DeQueue lưutrữ
trong mộtdanhsáchnốikép
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 19
Bài toán đổisố cơ số
– Bài toán: Viếtmộtsố trong hệ thập phân thành số
trong hệ cơ số b bấtkỳ
z Ví dụ:
– (356)
10
= (101100100)
2

2
2
0
1
0
1
1
0
0
1
0
0
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 20
Bài toán đổicơ số sử dụng Stack
– Thuật toán:
z Đầu vào: Số n trong hệ thậpphân
z Đầura: Số tương ứng với n trong hệđếmcơ số b
z Thựchiện
1. Lấychữ số tạobởin%b. ĐẩyvàoStack
2. Thay n bằng n/b để tiếptụclấycácchữ số tiếp theo trong
kếtquả
3. Lặplạibước 1 và 2 cho đếnkhikếtquả của phép chia là
0
4. Lầnlượtlấycácchữ số ra khỏi Stack và in chúng ra kết
quả
Bài toán đổicơ số sử dụng Stack
4
6

Mỗidấu “(”, “{”, or “[” đềuphảicómộtdấu đóng tương ứng
“)”, “}”, or “[”
z Đúng: ( )(( )){([( )])}
z Đúng : ((( )(( )){([( )])}
z Sai: )(( )){([( )])}
z Sai: ({[ ])}
z Sai: (
– Viếtgiảithuậtnhậnmộtxâuđầuvàogồmcácký
tự mở , đóng ngoặc. Kiểmtraxâucóhợplệ
không
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 22
Function ParenMatch(X,n):
{ X là mộtxâubaogồm n ký tự mở, đóng ngoặc. Giảithuậttrả ra giá trị true nếuxâuX
chứamộtsố hợplệ cặp ngoặc, nếu không trả ra giá trị false}
KhởitạoS làmộtstack rỗng
for i =1 to n do begin
if X[i] là mộtngoặcmở then
S.push(X[i])
else if X[i] là một ngoặc đóng then begin
if S.isEmpty() then
return false {không có ngoặ
cmở tương ứng}
if S.pop() không hợpkiểuvới X[i] then
return false {cặp ngoặc đóng mở khác kiểu}
end
end
if S.isEmpty() then
return true { tấtcả cặp ngoặchợplệ}

Toán hạng 1
Toán hạng 2
Toán tử
Biểuthứcsố họcvới ký pháp Balan
A B C/ + D + A / B C DA + B / C – D
A B + C D - // + A B – C D(A + B ) / (C-D)
A B C * + + A * B CA + B* C
A B + C ** + A B C (A+B) * C
A B ++ A BA+B
Dạng hậutốDạng tiềntốDạng trung tố
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà
nội 24
Bài toán tính giá trị củabiểuthứcdạng hậutố
z Tính giá trị củamộtbiểuthứcdạng hậutố sử dụng Stack
– Đầuvào: Xâukýtự biểudiễnbiểuthứcdạng hậutố
z A B + C – D E * /
z Các giá trị của các biếnsố
z Các bước chính trong giảithuật
– Đọcbiểuthứcdạng hậutố từ trái qua phải
– Nếukýtự được đọclàmột toán hạng thì lưugiátrị vào stack
– Nếukýtự được đọclàmột toán tử X thì lầnlượtlấytừ stack
ra 2 giá trị, thựchiệnphéptoánX với2 giátrịđó, nạpkết
quả vào stack
– Thựchiệncácbướctrênđến khi toàn bộ biểuthức đã được
đọc
Bài toán tính giá trị củabiểuthứcdạng hậutố
Procedure EVALUATE (P, VAL)
Begin { P là biểuthứcdạng hậutố cần tính, VAL là biếnsẽ lưugiátrị tính được}
1. Ghi thêm dấu‘)’vàocuốiP để đánh dấu điểmkếtthúc

Stack
VAL
Chuyểnbiểuthứcdạng trung tố sang dạng hậutố
– Bài toán
z Xét biểuthứcsố họcdạng trung tố gồm các phép toán
cộng, trừ, nhân, chia, lũythừa và các dấungoặc
z Viếtbiểuthứcdạng hậutố tương ứng vớibiểuthức
trung tốđầuvào
– Để thựchiện, trong biểuthức trung tố cầnbiết
z Thứ tựưutiêncủa các phép toán : Lũythừa Æ Nhân,
Chia Æ Cộng, Trừ
z Qui tắckếthợp: Nếu có hai phép toán cùng thứ tựưu
tiên
– Lũythừa: Phảitrước, trái sau. 2^3^4 = 2^(3^4)
– Các phép toán khác : Trái trước, phảisau
z Dầungoặc: Ưutiênnhất