Bài giảng Cấu trúc dữ liệu và giải thuật - Các cấu trúc dữ liệu cơ bản - Văn Chí Nam

Giảng viên: 
Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến 
Danh sách liên kết 
Ngăn xếp 
Hàng đợi 
2 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
3 
 Giới thiệu 
 Các loại danh sách liên kết 
 Các thao tác trên danh sách liên kết 
 So sánh danh sách liên kết và mảng 
 Ứng dụng 
4 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
5 
 Mảng: cấu trúc dữ liệu quen thuộc 
 Tập có thứ tự 
 Số lượng phần tử cố định (tĩnh) 
 Cấp phát vùng nhớ liên tục 
 Truy xuất phần tử thông qua chỉ số 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
6 
 Đánh giá thao tác trên mảng: 
 Truy xuất phần tử? 
 Cập nhật? 
 Chèn phần tử? 
Xoá phần tử? 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
7 
 Thực tế: 
Không xác định được chính xác số lượng phần tử 
 Danh sách bệnh nhân: tăng/giảm. 
 Danh sách sinh viên: tăng/giảm. 
Vùng nhớ thay đổi trong quá trình sử dụng 
=> Không đủ vùng nhớ cấp phát liên tục. 
=> Cấu trúc dữ liệu động đáp ứng nhu cầu 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
8 
 Danh sách liên kết đơn 
 singly linked list 
 uni-directional linked list 
 Danh sách liên kết kép 
 doubly linked list 
 bi-directional linked list 
 Danh sách liên kết vòng 
 circularly linked list 
 ring list 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
9 
 Mỗi phần tử có MỘT liên kết đến phần tử phía 
sau nó. 
12 99 37 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
10 
 Mỗi phần tử có HAI liên kết đến phần tử đứng 
sau và trước nó. 
12 99 37 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
11 
 Có mối liên kết giữa phần tử cuối và phần tử 
đầu 
 12 99 37 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
12 
 Phần tử (Node, Element) 
 Phần tử = Dữ liệu + Liên kết 
Ví dụ: 
 Phần tử có 1 liên kết 
 Phần tử có 2 liên kết 
 Phần tử rỗng 
12 
99 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
13 
 Phần tử có dữ liệu gồm 1 thành phần 
 Phần tử có dữ liệu gồm 3 thành phần 
 Phần tử có dữ liệu gồm 1 cấu trúc 
number 
number id name 
number id name 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
14 
 Sinh viên tự viết phần cài đặt cho các ví dụ trên 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
15 
 Mỗi danh sách liên kết bao gồm: 
 Con trỏ đến phần tử đầu (hoặc/và cuối) danh sách. 
 (Các) phần tử trên danh sách 
 Dữ liệu 
 Các mối liên kết 
12 99 37 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
16 
Head 
Head Tail 
12 99 37 
12 99 37 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
17 
 Thêm phần tử 
 Duyệt danh sách 
 Xoá phần tử 
 Xoá danh sách 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
18 
 Vào đầu danh sách 
 Sau một phần tử 
 Vào cuối danh sách 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
19 
 Vào đầu danh sách: 
Nếu danh sách rỗng 
 Phần tử vừa thêm là phần tử đầu danh sách 
Ngược lại, 
Head 
12 99 37 1 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
20 
 Sau một phần tử (pNode): 
Nếu danh sách rỗng? 
Nếu danh sách khác rỗng? 
 Tạo node mới có dữ liệu là Data. 
 Cập nhật lại liên kết của CurNode và node vừa tạo. 
 X 
CurNode 
12 99 37 
1 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
21 
 Đảm bảo việc truy xuất đến tất cả các phần tử 
trên danh sách 
 Thuật toán: 
 Bắt đầu từ phần tử đầu tiên 
 Trong khi chưa hết danh sách 
 Xử lý phần tử hiện hành 
 Di chuyển đến phần tử kế tiếp 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
22 
 Đầu danh sách 
 Cuối danh sách 
 Sau một phần tử 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
23 
 Đầu danh sách 
Nếu danh sách rỗng: 
Nếu danh sách khác rỗng: 
 Cập nhật lại Head 
 Xóa Head cũ 
Head 
12 99 37 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
24 
 Cuối danh sách: 
Danh sách rỗng? 
Danh sách khác rỗng: 
 tìm con trỏ cuối danh sách Tail 
 Cập nhật lại Tail 
 Xóa Tail cũ 
Tail 
12 99 37 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
25 
 Sau một phần tử (CurNode) 
 - Trường hợp chung: 
 - Trường hợp đặc biệt: 
CurNode cần xóa 
12 99 37 21 
CurNode 
Head 
99 37 
CurNode 
21 37 
Head 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
26 
 Danh sách liên kết bao gồm các phần tử được 
cấp phát động. 
 Phải xoá các phần tử trên danh sách sau khi đã 
sử dụng xong danh sách. 
 Thuật toán: 
Duyệt qua các phần tử trên danh sách 
Xoá từng phần tử 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
27 
 Một dãy tuần tự các node 
 Giữa hai node có (các) liên kết 
 Các node không cần phải lưu trữ liên tiếp nhau 
trong bộ nhớ 
 Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung 
lượng bộ nhớ) 
 Thao tác Chèn/Xóa không cần phải dịch chuyển 
phần tử 
 Có thể truy xuất đến các phần tử khác thông 
qua con trỏ liên kết 
 Cần xác định trước số phần tử. 
 Cần cấp phát vùng nhớ liên tục 
đủ lớn để lưu trữ mảng  lãng 
phí nếu không dùng hết. 
 Truy xuất ngẫu nhiên, đơn giản, 
nhanh chóng. 
 Không cần 
 Thêm/xóa phần tử cuối: O(1) 
 Thêm/xóa phần tử giữa: O(n) 
28 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
Danh sách liên kết Mảng 
 Số phần tử không cần xác định 
trước. 
 Cấp phát vùng nhớ riêng lẻ cho 
từng phần tử. 
 Truy xuất tuần tự, danh sách liên 
kết đơn chỉ có thể duyệt 1 chiều. 
 Cần nhiều bộ nhớ hơn để lưu trữ 
con trỏ tham chiếu 
 Thêm/xóa phần tử cuối: O(1) 
 Thêm/xóa phần tử giữa: O(1) 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
29 
 Là cấu trúc dữ liệu chính cho ngôn ngữ lập trình 
LISP (LIst Processing Language) – ngôn ngữ 
lập trình hàm. 
 Giúp nâng cao hiệu quả của một số thuật toán 
sắp xếp: Quick Sort, Radix Sort 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
30 
 Cho một DSLK đơn, mỗi node trong DSLK lưu 
thông tin là 1 số nguyên và con trỏ đến node kế. 
Tạo 2 DSLK đơn mới (không phá huỷ DSLK đã 
cho). 
Một danh sách chứa các số lẻ của danh sách đã 
cho. 
Một danh sách chứa các số chẵn của danh sách đã 
cho. 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
31 
 In ra các đường chạy tự nhiên từ DSLK đã cho: 
VÍ DỤ: DSLK ban đầu biểu diễn các số: 1 5 6 4 8 3 
7 
 In ra các dãy số: 1 5 6 
 4 8 
 3 7 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
32 
 Cho danh sách liên kết đơn L, lập giải thuật 
thực hiện các phép sau đây: 
 Tính số lượng các nút của danh sách. 
 Tìm tới nút thứ k trong danh sách, nếu có nút thứ k thì 
cho biết địa chỉ của nút đó, ngược lại trả về null. 
 Bổ sung một nút vào sau nút k. 
 Loại bỏ nút đứng trước nút k. 
Đảo ngược danh sách đã cho. 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
33 
 Hàm MoveToFront có tác dụng di chuyển 1 
node trong xâu lên đầu xâu, như hình sau: 
 Chọn kiểu khai báo hàm phù hợp và viết cài đặt 
Head 
CurNode 
12 99 37 21 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
34 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
35 
 Giới thiệu 
 Các thao tác cơ bản 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
36 
 Một số hình ảnh thông dụng: 
Một chồng sách vở ở trên bàn 
Một chồng đĩa 
 Cơ cấu của một hộp chứa đạn súng trường. 
Nhận xét gì từ các ví dụ trên? 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
37 
 Định nghĩa: 
Ngăn xếp là vật chứa các đối tượng 
làm việc theo cơ chế “vào sau ra 
trước” (Last In First Out) 
Đối tượng có thể được thêm vào 
bất kì lúc nào, nhưng chỉ có đối 
tượng vào sau cùng mới được 
phép lấy ra khỏi ngăn xếp. 
6 
5 
4 
3 
2 
Đỉnh 
Đáy 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
38 
 Lưu trữ ngăn xếp 
 Kiểm tra ngăn xếp rỗng 
 Thêm 1 phần tử vào ngăn xếp 
 Lấy 1 phần tử ra khỏi ngăn xếp 
 Lấy thông tin của phần tử đầu ngăn xếp 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
39 
 Lưu trữ bằng mảng 
Khai báo mảng 1 chiều với kích thước tối đa N. 
 t là địa chỉ của phần tử đỉnh của ngăn xếp → t sẽ thay 
đổi khi ngăn xếp hoạt động. 
 Ngăn xếp rỗng thì giá trị của t là 0 
 Tạo ngăn xếp S và quản lý ngăn xếp bằng biến t: 
 Data S[N]; 
 int t; 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
40 
 Lưu trữ bằng DSLK: 
Dùng con trỏ Head lưu địa chỉ của đỉnh ngăn xếp 
Ngăn xếp rỗng khi Head = null 
Head 
12 99 37 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
41 
 Input: 
 Output: 
 TRUE nếu ngăn xếp rỗng 
 FALSE nếu ngăn xếp không rỗng 
 Ngăn xếp rỗng: 
Mảng: số lượng phần tử mảng là 0 
DSLK: Head = null 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
42 
 Input: 
 Output: 
 TRUE nếu ngăn xếp đầy 
 FALSE nếu ngăn xếp còn chỗ trống 
 Ngăn xếp đầy: 
Mảng: đã lưu hết các phần tử mảng 
DSLK: không cấp phát được vùng nhớ mới cho ngăn 
xếp 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
43 
 Input: phần tử cần thêm 
 Output: 
 Giải thuật: 
Kiểm tra ngăn xếp có đầy không? 
Nếu không 
 Bổ sung phần tử mới vào 
 Cập nhật địa chỉ của con trỏ đến đỉnh ngăn xếp 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
44 
 Ví dụ: 
4 
3 
2 
5 
4 
3 
2 
Đỉnh = 3 
Ngăn xếp ban đầu Ngăn xếp sau khi thêm push(5) 
Đỉnh = 4 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
45 
 Input: 
 Output: giá trị của đối tượng đầu ngăn xếp 
 Thuật toán: 
Kiểm tra ngăn xếp rỗng hay không? 
Nếu không: 
 Cập nhật địa chỉ của con trỏ đến đỉnh ngăn xếp 
 Xóa phần tử ở đỉnh khỏi ngăn xếp 
 Trả về giá trị của phần tử ở đỉnh 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
46 
 Ví dụ: 
3 
2 
4 
3 
2 
Ngăn xếp ban đầu Ngăn xếp sau khi pop() 
return 4; 
Đỉnh = 3 
Đỉnh = 2 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
47 
 Chỉ lấy giá trị của phần tử đầu mà không hủy nó 
khỏi ngăn xếp. 
 Input: 
 Output: giá trị tại đỉnh ngăn xếp 
 Giải thuật: 
 Kiểm tra xem ngăn xếp có rỗng không? 
 Trả về giá trị của phần tử ở đỉnh ngăn xếp 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
48 
 Ví dụ 
4 
3 
2 
4 
3 
2 
Ngăn xếp ban đầu Ngăn xếp sau khi gettop() 
return 4; 
Đỉnh = 3 Đỉnh = 3 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
49 
 Cho dãy thao tác: 
 EAS*Y**QUE***ST***I*ON 
 Một chữ cái tượng trưng cho thao tác thêm chữ 
cái đó vào stack 
 Dấu * tượng trưng cho thao tác lấy nội dung 
một phần tử trong stack in lên màn hình. 
 Cho biết kết quả xuất ra màn hình sau khi hoàn 
tất chuỗi trên? 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
50 
 Cho biết nội dung của stack và giá trị của các biến 
sau khi thực hiện các thao tác sau: A= 5, B = 3, 
 C= 7 
 a. Tạo stack 
 b. push A 
 c. push C*C 
 d. pop và lưu trữ vào B 
 e. push B+A 
 f. pop và lưu trữ vào A 
 g. pop và lưu trữ vào B 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
51 
 Dùng biến đổi cơ số 
 Lượng giá biểu thức hậu tố 
 Trong trình biên dịch, ngăn xếp được sử dụng 
để lưu môi trường các thủ tục. 
 Dùng trong một số bài toán của lý thuyết đồ thị. 
 Khử đệ qui đuôi. 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
52 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
53 
 Giới thiệu 
 Các thao tác cơ bản 
 Ứng dụng 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
54 
 Giới thiệu: 
 Là vật chứ các đối tượng làm việc theo qui tắc vào 
trước ra trước (FIFO). 
 Các đối tượng có thể được thêm vào hàng đợi bất kì 
lúc nào nhưng chỉ có đối tượng thêm vào đầu tiên mới 
được lấy ra khỏi hàng đợi 
Việc thêm vào diễn ra ở cuối, việc lấy ra diễn ra ở đầu 
1 3 6 5 2 
Đầu Cuối 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
55 
 Lưu trữ hàng đợi 
 Kiểm tra hàng đợi rỗng 
 Kiểm tra hàng đợi đầy 
 Thêm 1 đối tượng vào cuối hàng đợi 
 Lấy đối tượng ở đầu ra khỏi hàng đợi 
 Lấy thông tin của đối tượng ở đầu hàng đợi 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
56 
 Lưu trữ bằng mảng: 
Khai báo mảng 1 chiều với kích thước tối đa N. 
 f là địa chỉ của phần tử nằm ở đầu, r là địa chỉ của phần 
tử nằm ở cuối 
1 3 6 5 2 
0 1 2 3 4 5 6 7 8 
f = 2 r = 6 
Hàng đợi 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
57 
 Lưu trữ bằng mảng: 
 Các phần tử của hàng đợi sẽ di chuyển khắp các ô nhớ 
 coi không gian dành cho hàng đợi theo dạng xoay 
vòng. 
Hàng đợi khi xoay vòng: 
1 3 6 5 2 
0 1 2 3 4 5 6 7 8 
r = 2 f = 6 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
58 
 Lưu trữ hàng đợi bằng danh sách liên kết đơn 
 Phần tử đầu DSLK sẽ là phần tử đầu hàng đợi. 
 Phần tử cuối DSLK sẽ là phần tử cuối hàng đợi 
Tail 
(cuối) 
Head (đầu) 
12 99 37 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
59 
 Input: 
 Output: 
 TRUE nếu hàng đợi rỗng 
 FALSE nếu hàng đợi không rỗng 
 Hàng đợi rỗng: 
Mảng: ô nhớ đầu tiên không chứa dữ liệu 
DSLK: Head = null 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
60 
 Input: 
 Output: 
 TRUE nếu hàng đợi đầy 
 FALSE nếu hàng đợi không đầy 
 Hàng đợi đầy: 
Mảng: ô nhớ cuối hàng đợi đã chứa dữ liệu 
DSLK: không cấp phát được vùng nhớ cho phần tử 
mới 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
61 
 Input: giá trị cần thêm 
 Output: 
 Giải thuật thêm phần tử (EnQueue) 
Kiểm tra hàng đợi đã đầy chưa? 
 Trong trường hợp lưu trữ bằng mảng: kiểm tra điều 
kiện xoay vòng. 
 Thêm phần tử vào cuối hàng đợi 
 Cập nhật địa chỉ phần tử cuối hàng đợi 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
62 
 Ví dụ: 
1 3 6 5 2 
0 1 2 3 4 5 6 7 8 
f = 2 r = 6 
1 3 6 5 2 9 
f = 2 r = 7 
Hàng đợi ban đầu 
EnQueue(9) 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
63 
 Input: 
 Output: giá trị của phần tử đầu hàng đợi 
 Giải thuật lấy phần tử ở đầu (DeQueue) 
Kiểm tra hàng đợi có rỗng không? 
Xóa phần tử đầu ra khỏi hàng đợi 
 Cập nhật địa chỉ phần tử đầu hàng đợi 
 Trong trường hợp lưu trữ bằng mảng: kiểm tra điều 
kiện xoay vòng 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
64 
 Ví dụ: 
1 3 6 5 2 
0 1 2 3 4 5 6 7 8 
f = 2 r = 6 
3 6 5 2 
f = 3 r = 6 
Hàng đợi ban đầu 
DeQueue() = 1 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
65 
 Chỉ lấy thông tin của đối tượng đầu hàng đợi 
mà không hủy đối tượng khỏi hàng đợi. 
 Input: hàng đợi 
 Output: giá trị của đối tượng đầu hàng đợi 
 Giải thuật: 
Kiểm tra hàng đợi rỗng? 
 Trả về giá trị của phần tử đầu hàng đợi 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
66 
 Ví dụ: 
1 3 6 5 2 
0 1 2 3 4 5 6 7 8 
f = 2 r = 6 
Hàng đợi ban đầu 
1 3 6 5 2 
f = 2 r = 6 
GetFront() = 1 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
67 
 Bộ đệm bàn phím của máy tính 
 Xử lý các lệnh trong máy tính: hàng đợi thông 
điệp trong Windows, hàng đợi tiến trình  
 Thường dùng trong các hệ mô phỏng. 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
68 
Cho hàng đợi ban đầu như sau: (hàng đợi có tối đa 6 phần tử) 
Vẽ tình trạng của hàng đợi, cho biết giá trị f, r tương ứng với mỗi lần 
thực hiện thao tác sau: 
a. Bổ sung E vào hàng đợi 
b. Loại 2 phần tử khỏi hàng đợi 
c. Bổ sung I, J, K vào hàng đợi 
d. Loại 2 phần tử khỏi hàng đợi 
e. Bổ sung O vào hàng đợi 
f. Loại 2 phần tử khỏi hàng đợi 
0 1 2 3 4 5 
A B C 
f = 1 r = 3 
69 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
Ký pháp Ba Lan 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
71 
 Biểu thức dạng trung tố: dấu của các phép toán 
hai ngôi luôn được đặt giữa 2 toán hạng 
Ví dụ: A + B * C A + B * C - D 
 (A+B) * C (A + B )* (C – D) 
 Qui định thứ tự ưu tiên của các phép toán 
 Dùng dấu ngoặc để phân biệt thứ tự thực hiện. 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
72 
 Biểu thức dạng tiền tố: 
 Biểu thức dạng hậu tố: 
Không cần 
thiết phải 
dùng dấu 
ngoặc 
Trung tố Tiền tố 
A + B + A B 
(A+B)*C *+ A B C 
(A + B )* (C – D) * + A B – C D 
Trung tố Hậu tố 
A + B A B + 
(A+B)*C A B + C * 
(A + B )* (C – D) A B + C D - * 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
73 
 Mã giả: P là biểu thức trung tố ban đầu, Q là 
biểu thức kết quả dạng hậu tố 
0.1 push(‘(‘); 
0.2 Thêm ‘)’ vào P 
while (chưa hết biểu thức P) 
{ 
 1. đọc 1 kí tự x trong P (từ trái qua phải) 
 2. if (x là toán hạng) 
 Thêm x vào Q 
 3. if (x là dấu ngoặc mở) 
 push(x); 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
74 
 Mã giả: 
 4. if (x là toán tử) 
 4.1 while( thứ tự ưu tiên tại đỉnh >= x) 
 4.1.1 w = pop(); 
 4.1.2 Thêm w vào Q 
 4.2 push(x); 
 5. if (x là dấu ngoặc đóng) 
 5.1 while( chưa gặp ngoặc mở) 
 4.1.1 w = pop(); 
 4.1.2 Thêm w vào Q 
 5.2 pop();//đẩy ngoặc mở ra khỏi ngăn xếp 
} 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
75 
 Ví dụ 1: P = ( A + B ) * ( C - ( D + A ) ) 
( A + B ) * ( C - ( D + A ) ) 
( 
( 
Kí tự đọc 
được 
Trạng 
thái của 
ngăn xếp 
( 
( 
+ 
( 
( 
+ 
( 
( ( 
* 
( 
( 
* 
( 
( 
* 
( 
- 
( 
* 
( 
( 
- 
( 
* 
( 
( 
- 
( 
* 
( 
+ 
( 
- 
( 
* 
( 
+ 
( 
- 
( 
* 
( 
- 
( 
* 
( 
* 
( 
Q = A B + C D A + - * 
Cấu trúc dữ liệu và giải thuật – HCMUS 2013 
76 
 Ví dụ 2: đổi biểu thức trung tố 
 P = A + (B * C – (D / E ^ F) * G) * H 
 sang biểu thức dạng hậu tố