ĐẠI HỌC PHÚ YÊN
KHOA KỸ THUẬT – CÔNG NGHỆ

BÁO CÁO BÀI TIỂU LUẬN
ĐÊ TÀI: NGĂN XẾP,HÀNG ĐỢI
TÍNH GIÁ TRỊ BIỂU THỨC THEO PHƯƠNG PHÁP NGHỊCH ĐẢO
BA LAN
GIÁO VIÊN HƯỚNG DẪN: TRẦN MINH CẢNH
SINH VIÊN THỰC HIỆN : NHÓM 2
LỚP : ĐẠI HỌC SƯ PHẠM TIN HỌC – C13
MÔN HỌC : CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
class="bi x0 yd w1 h6"
LỜI MỞ ĐẦU
Cấu trúc dữ liệu và thuật toán là một trong những môn học cơ
bản của sinh viên ngành Công nghệ thông tin. Các cấu trúc dữ liệu và
các giải thuật được xem như là 2 yếu tố quan trọng nhất trong lập
trình, đúng như câu nói nỗi tiếng của Niklaus Wirth: Chương trình=
Cấu trúc dữ liệu + Giải thuật (Programs=Data Structures+
Algorithms). Nắm vững các cấu trúc dữ liệu và các giải thuật là cơ sở
để sinh viên tiếp cận với việc thiết kế và xây dựng phần mềm cũng
như sử dụng các công cụ lập trình hiện đại.
Hai cấu trúc dữ liệu rất gần gũi với các hoạt đọng trong thực tế,
đó là ngăn xếp và hàng đợi.
Ngăn xếp là một dạng đặc biệt của danh sách mà việc bổ sung
hay loại bỏ một phần tử đều được thực hiện ở 1 đầu của danh sách.
Ngăn xếp còn được gọi là kiểu dữ liệu có nguyên tắc LIFO (Last In
First Out- Vào sau ra trước).
Hàng đợi là một cấu trúc dữ liệu gần giống với ngăn xếp, nhưng
phần tử được lấy ra khỏi hàng đợi không phải là phần tử mới nhất
được đưa vào mà là phần tử đã được lưu trong hàng đợi lâu nhất. Quy
luật này được gọi là vào trước ra trước (FIFO- First In First Out).

III. Chương trình Demo tính giá trị biểu thức nghịch đảo Ba
Lan …………………………………………………………… 20
A.NGĂN XẾP VÀ HÀNG ĐỢI
I.NGĂN XẾP(Stack)
1.Khái niệm:
Ngăn xếp là một dạng danh sách đặc biệt chỉ thực hiện được hai thao tác:
thêm một phần tử vào cuối danh sách (push) và lấy phần tử cuối ra khỏi danh
sách (pop).
Như vậy trong một ngăn xếp, phần tử vào sau sẽ lấy ra trước nên còn gọi là
danh sách kiểu LIFO (Last in first out).Vị trí của phần tử của phần tử cuối cùng
của ngăn xếp còn gọi là đỉnh(top)của ngăn xếp.
 Các thao tác trên ngăn xếp gồm hai thao thao tác cơ bản là:
• Push(x,S): Đưa phần tử x vào ngăn xếp .
• Pop(x,S): Lấy phần tử ở đỉnh ngăn xếp S ra và lưu vào biến x.
Ngoài ra, còn có các thao tác bổ sung:
a
4
a
3
a
2
a
1
Push
pop
• Init(S):Khởi tạo một ngăn xếp S rỗng.
• Full(S): Cho biết ngăn xếp S có đầy không.
• Clear(S): Làm rỗng ngăn xếp S.
• Gettop(S): Lấy phần tử ở đỉnh ngăn xếp.
• Length(S): Cho biết số phần tử của ngăn xếp.

End;
Var S: StackArr
3.Các phép toán:
a.Khởi tạo stack:
• Tạo 1 stack S rỗng : Top = 0

• Giá trị của Top sẽ cho biết số phần tử hiện hành có trong stack:
Procedure Init(var S: StackArr);
Begin
S.top := 0;
End;
• Khi cài đặt mảng 1 chiều, stack bị gia hạn bởi kích thước nên cần xây
dựng thêm một thao tác phụ cho stack:
Hàm Full sẽ kiểm tra đỉnh ngăn xếp, nếu Top =MaxLength thì ngăn xếp
đầy.
Function Full ( S: StackArr) : BooLean;
Begin
Full := (S.top = MaxLength);
End;
Hàm Empty sẽ kiểm tra đỉnh ngăn xếp, nếu top=0 thì ngăn xếp rỗng.
Function Empty(S :StackArr): Boolean;
Begin
Empty := (S.top =0);
End;
b.Các thao tác chính cho Stack:
 .Thêm một phần tử x vào đỉnh ngăn xếp S:
Thêm phần tử A vào ngăn xếp Push (S,A)

A
Procedure Pop(var x: ElementType; var S : StackArr);
Begin
If not Empty(S) then
With S do
C
C
B
Begin
x:= element[top];
dec(top);
end;
End;
 Nhận xét:
• Các thao tác trên đều làm việc với độ phức tạp 0(1)
• Việc cài đặt Stack thông qua mảng một chiều đơn giản và khá hiệu quả
• Tuy nhiên hạn chế lớn nhất của phương án cài đặt này là giới hạn về
kích thước của Stack:
Là ta cần phải biết trước kích thước tối đa của ngăn xếp (giá trị max trong khai
báo ở trên). Điều này không phải lúc nào cũng xác định được và nếu ta chọn
một giá trị bất kỳ thì có thể dẫn đến lãng phí bộ nhớ nếu kích thước quá thừa so
với yêu cầu hoặc nếu thiếu thì sẽ dẫn tới chương trình có thể không hoạt động .
b. Chương trình Demo các thao tác trên Stack
Program stack_by_array;
Const max =1000;
Var
Stack: Array[1 max] of integer;
Top: integer;
Procedure stack_init;
Begin

Hình ảnh của ngăn xếp S=(a
1
,a
2
,…,a
n
) tổ chức bằng danh sách liên kết như
sau:
a
1
Để bổ sung 1 phần tử vào danh sách, ta tạo ra 1 nút mới và thêm nó vào đầu
danh sách. Để lấy 1 phần tử khỏi ngăn xếp, ta chỉ cần lấy giá trị nút đầu tiên
và loại nút ra khỏi danh sách.
Đỉnh ngăn xếp Đáy ngăn xếp
 Khai báo
Type
StackLink = ^Cell;
Cell = Record
Data : ElementType;
Link : StackLink;
End;
Var S : StackLink;
 Các thao tác trong tổ chức ngăn xếp bằng danh sách liên kết
• Khởi tạo đỉnh ngăn xếp:
NIL
a
2
a
n
Thao tác này thực hiện việc gán giá trị null cho nút đầu ngăn xếp, cho biết

Procedure Pop(Var x:ElmentType; var S: StackLink);
Var p: StackLink;
Begin
If not Empty (S) then
Begin
x:= S^.Data;
p:= S;
S:= p^.Link;
NIL
Dispose(p);
End;
End;
• Làm rỗng ngăn xếp: xóa và thu hồi các ô nhớ.
Procedure Clear(var S: StackLink);
Var p : StackLink;
Begin
While not Empty(S) do
Begin
P:= S;
S:= p^.Link;
Dispose(p);
End;
End;
5. Các ứng dụng của ngăn xếp:
• Khử đệ quy
• Tính giá trị của các biểu thức
 Nhận xét:
Tổ chức ngăn xếp bằng danh sách liên kết thích hợp lưu trữ các loại dữ liệu
mà trình tự xuất ngược với trình tự lưu trữ.
II)Hàng đợi: (Queue)

n
a
1
a
2
… a
n
Queue = Record
Elemen:Array[1 Maxlength] of ElementType;
Front , Rear:0 Maxlength;
Var Q:Queue;
3.Các thao tác trên hàng đợi:
• Khởi tạo hàng đợi:
Procedure InitQueue(var Q:Queue);
Begin
Q.Front:=1;
Q.Rear:=0;
End;
• Hàm Emply:(kiểm tra hàng đợi rỗng)
Function Emply(Q:Queue):Boolean;
Begin
Emply := (Q.rear = 0);
End;
• Thêm vào một phần tử:
Thêm phần tử x vào hàng đợi Q
Procedure themQueue(x:ElementType;var Q:Queue);
Begin
If not Full(Q) then
Begin
Q.rear := Q.rear +1;

BaLan không cần dấu ngoặc nhưng vẫn thể hiện được thứ tự ưu tiên khi tính
giá trị biểu thức nên dễ dàng xây dựng thuật toán tính.
Ví dụ : Biểu thức dạng trung tố : 3+(5-2)*3/7-4
Chuyển sang dạng hậu tố là : 3 5 2 -3* 7/4 - +
Thuật toán chuyển biểu thức dạng trung tố sang dạng hậu tố :
Giả sử ta có một biểu thức E dạng trung tố trong đó ta có thể phân tích thành
các thành phần của biểu thức là các toán hạng và phép toán.
Dùng một ngăn xếp S mỗi phần tử là phép toán hoặc dấu ngoặc mở. Kết quả
đưa ra biểu thức hậu tố E
1
.
I.Thuật toán chuyển biểu thức dạng trung tố sang hậu tố.
1. Khởi tạo biểu thức E1, rỗng
2. Duyệt lần lượt từ trái sang phải các thành phần cảu biểu thức E1, với
mỗi thành phần x thực hiện :
2.1 Nếu x là toán hạng thì nối vào bên phải biểu thức E1.
2.2 Nếu x là dấu ngoặc mở thì đưa vào ngăn xếp
2.3 Nếu x là phép toán thì :
a. Đọc phần tử y ở đầu ngăn xếp.
b. Nếu độ ưu tiên của y cao hơn hoặc bằng x thì
- Lấy y ra khỏi ngăn xếp
- Nối y vào bên phải E1
- Lặp lại bước a.
c. Nếu độ ưu tiên của x cao hơn y thì đưa x vào ngăn xếp .
d. Nếu ngăn xếp rỗng thì đưa x vào ngăn xếp .
2.4 Nếu x là dấu ngoặc đóng thì :
a. Đọc phần tử y ở đầu ngăn xếp.
b. Nếu y là phép toán thì :
- Lấy y ra khỏi ngăn xếp
- Nối y vào bên phải biểu thức E1

(
(+
(+
(+*
(+*
(-
(-
ᴓ
*
*
-
-(
-(
-(+
-(+
-
-*
-*
ᴓ
2
2
2 7
2 7
2 7 3
2 7 3*+
2 7 3*+ 8
2 7 3 *+8-
2 7 3*+ 8-
2 7 3*+ 8-4
2 7 3*+ 8-4*

Ngăn xếp
*2
7
3
*
+
2
2 7
2 7 3
2 21
23
8
-
4
*
3
2
+
3
*
-
2
-
23 8
15
15 4
60
60 3
60 3 2
60 5

S := S + ' ';
for i := Length(S) - 1 downto 1 do {Thêm những dấu cách giữa toán hạng và
toán tử}
if (S[i] in Opt) or (S[i + 1] in Opt) then
Insert(' ', S, i + 1);
for i := Length(S) - 1 downto 1 do {Xoá những dấu cách thừa}
if (S[i] = ' ') and (S[i + 1] = ' ') then Delete(S, i + 1, 1);
end;
procedure Process(T: String); {Xử lý phần tử T đọc được từ biểu thức RPN}
var
x, y: Extended;
e: Integer;
begin
if not (T[1] in Opt) then {T là toán hạng}
begin
Val(T, x, e); Push(x); {Đổi T thành số và đẩy giá trị đó vào Stack}
end
else {T là toán tử}
begin
y := Pop; x := Pop; {Ra hai}
case T[1] of
'+': x := x + y;
'-': x := x - y;
'*': x := x * y;
'/': x := x / y;
end;
Push(x); {Vào một}
end;
end;
begin