Bài giảng Cấu trúc dữ liệu - Chương 5: Kiểu ngăn xếp, hàng đợi, đệ quy - Thiều Quang Trung

CHƯƠNG 5 
KIỂU NGĂN XẾP, HÀNG ĐỢI, ĐỆ QUY 
GV Th.S. Thiều Quang Trung 
Bộ môn Khoa học cơ bản 
Trường Cao đẳng Kinh tế Đối ngoại 
• Khái niệm ngăn xếp 1 
• Phương pháp xây dựng stack 2 
• Các thao tác cơ bản trên stack 3 
• Kiểu queue - hàng đợi 4 
• Các thao tác cơ bản trên queue 5 
• Đệ qui và các bài toán đệ qui 6 
Nội dung 
2 GV. Thiều Quang Trung 
Ngăn xếp - Định nghĩa 
• Stack là 1 cấu trúc: 
– Gồm nhiều phần tử 
– Hoạt động theo cơ chế “Vào sau – Ra trước” 
(LIFO – Last In, First Out) 
 Đỉnh 
ngăn 
xếp 
3 GV. Thiều Quang Trung 
Thao tác cơ bản trên Stack 
• InitStack: khởi tạo Stack rỗng 
• IsEmpty: kiểm tra Stack rỗng? 
• IsFull: kiểm tra Stack đầy? 
• Push: thêm 1 phần tử vào Stack 
• Pop: lấy ra 1 phần tử khỏi Stack 
Push Pop 
4 GV. Thiều Quang Trung 
Thao tác thêm - Push vào Stack 
Top 
P
U
SH
5 GV. Thiều Quang Trung 
Thao tác lấy - Pop khỏi stack 
Top 
P
O
P
6 GV. Thiều Quang Trung 
Ví dụ thêm và xóa phần tử trong stack 
Cần nhập 4 số vào 
Ban đầu Nhập 1 
1 
Nhập 5 
1 
5 
Nhập 7 
1 
5 
7 
Nhập 3 
1 
5 
7 
3 
Lấy ra => 3 
1 
5 
7 
3 
Lấy ra => 7 
1 
5 
7 
Lấy ra => 5 
1 
5 
Lấy ra => 1 
1 
Stack đã rỗng 
Ngừng 
7 GV. Thiều Quang Trung 
Cách xây dựng Stack 
Mảng 1 chiều Danh sách liên kết 
 Viết chương trình dễ 
dàng, nhanh chóng 
 Bị hạn chế do số lượng 
phần tử cố định 
 Tốn chi phí tái cấp phát 
và sao chép vùng nhớ 
nếu sử dụng mảng 
động 
 Phức tạp khi triển khai 
chương trình 
 Không bị cố định về số 
phần tử, phụ thuộc vào 
bộ nhớ 
8 GV. Thiều Quang Trung 
Stack – Sử dụng mảng 
9 
3 
6 
9 3 6 
0 1 2 3 4 5 6 7 8 9 
Stack 
Top 
9 GV. Thiều Quang Trung 
Stack số nguyên – Sử dụng mảng 
struct ttStack 
{ 
 int* StkArray; // mảng chứa các phần tử 
 int StkMax; // số phần tử tối đa 
 int StkTop; // vị trí đỉnh Stack 
}; 
typedef struct ttStack STACK; 
10 GV. Thiều Quang Trung 
Stack số nguyên – Sử dụng mảng 
bool InitStack(STACK& s, int MaxItems) 
{ 
 s.StkArray = new int[MaxItems]; 
 if (s.StkArray == NULL) 
 return false; 
 s.StkMax = MaxItems; 
 s.StkTop = -1; 
 return true; 
} 
11 GV. Thiều Quang Trung 
Stack số nguyên – Sử dụng mảng 
bool IsEmpty(const STACK &s) 
{ 
 if (s.StkTop==-1) 
 return true; 
 return false; 
} 
12 GV. Thiều Quang Trung 
Stack số nguyên – Sử dụng mảng 
bool IsFull(const STACK &s) 
{ 
 if (s.StkTop==s.StkMax-1) 
 return true; 
 return false; 
} 
13 GV. Thiều Quang Trung 
Stack số nguyên – Sử dụng mảng 
bool Push (STACK &s, int newitem) 
{ 
 if (IsFull(s)) 
 return false; 
 s.StkTop++; 
 s.StkArray[s.StkTop] = newitem; 
 return true; 
} 
14 GV. Thiều Quang Trung 
Stack số nguyên – Sử dụng mảng 
bool Pop(STACK &s, int &outitem) 
{ 
 if (IsEmpty(s)) 
 return false; 
 outitem = s.StkArray[s.StkTop]; 
 s.StkTop--; 
 return true; 
} 
15 GV. Thiều Quang Trung 
Bài tập 
• Viết hàm nhập và xuất Stack số nguyên 
• Khai báo cấu trúc và viết hàm tạo Stack từ 
chuỗi ký tự str (mỗi phần tử Stack là ký tự) 
• Khai báo cấu trúc và viết hàm tạo Stack từ 
chuỗi ký tự str (mỗi phần tử Stack là một từ 
- từ cách nhau bởi khoảng trắng) 
16 GV. Thiều Quang Trung 
Stack – Ví dụ ứng dụng 
• Kiểm tra sự tương ứng của các cặp ngoặc 
đơn trong một biểu thức 
• ( ( A + B ) / C ( A + B ) / C) 
• Đảo ngược một chuỗi ký tự 
• Kinh tế Đối ngoại iạogn iốĐ ết hniK 
? ? 
17 GV. Thiều Quang Trung 
Stack – Sử dụng DSLK 
9 
7 
4 

N 
StkCnt StkTop 
7 
Data Link 
9 
Data Link 

4 
Data Link 
18 GV. Thiều Quang Trung 
Stack – Sử dụng DSLK 
• Cấu tạo đầu stack 
• Cấu tạo một phần tử 
N 
StkCnt StkTop 
Data Link 
stack 
 StkCnt 
 StkTop 
end stack 
node 
 Data 
 Link 
end node 
19 GV. Thiều Quang Trung 
Stack số nguyên – Sử dụng DSLK 
typedef struct tagSTACK_NODE 
{ 
 int Data; 
 tagSTACK_NODE *pNext; 
} STACK_NODE; 
typedef struct STACK 
{ 
 int StkCount; 
 STACK_NODE *StkTop; 
}; 
20 GV. Thiều Quang Trung 
Stack – Sử dụng DSLK 
• VD: Thực hiện một số thao tác trên stack 
STACK s; 
InitStack(s); 
Push(s, 7); 
Push(s, 4); 
Pop(s, x); // x = ? 
N 
StkCnt StkTop 
7 
Data Link 
4
21 GV. Thiều Quang Trung 
Stack số nguyên – Sử dụng DSLK 
void InitStack(STACK &s) 
{ 
 s.StkTop = NULL; 
 s.StkCount = 0; 
} 
22 GV. Thiều Quang Trung 
Stack số nguyên – Sử dụng DSLK 
bool IsEmpty(const STACK &s) 
{ 
 if (s.StkTop == NULL) 
 return true; 
 return false; 
} 
23 GV. Thiều Quang Trung 
Stack số nguyên – Sử dụng DSLK 
bool IsFull (const STACK s) 
{ 
 STACK_NODE* temp = new STACK_NODE; 
 if (temp == NULL) 
 return true; 
 delete temp; 
 return false; 
} 
24 GV. Thiều Quang Trung 
Stack số nguyên – Sử dụng DSLK 
bool Push(STACK &s, int newitem) 
{ 
 if (IsFull(s)) 
 return false; 
 STACK_NODE *pNew = new STACK_NODE; 
 pNew->Data = newitem; 
 pNew->pNext = s.StkTop; 
 s.StkTop = pNew; 
 s.StkCount++; 
 return true; 
} 
N 
StkCnt StkTop 
7 
Data Link 
4
25 GV. Thiều Quang Trung 
Stack số nguyên – Sử dụng DSLK 
bool Pop(STACK &s, int &outitem) 
{ 
 if (IsEmpty(s)) 
 return false; 
 STACK_NODE *temp = s.StkTop; 
 outitem = s.StkTop->Data; 
 s.StkTop = s.StkTop->pNext; 
 delete temp; 
 s.StkCount--; 
 return true; 
} 
N 
StkCnt StkTop 
7 
Data Link 
4 
Data Link 
temp 
outitem = 4 
26 GV. Thiều Quang Trung 
Stack – Ứng dụng 
• Stack có nhiều ứng dụng: 
• Lưu vết trong thuật toán “back-tracking” (theo dõi 
dấu vết) 
• Tính giá trị biểu thức toán học (thuật toán Balan 
ngược) 
• Khử đệ quy 
•  
27 GV. Thiều Quang Trung 
Stack – Quick Sort 
• Để khử đệ quy cho Quick Sort, ta sử dụng một 
stack để lưu lại các partition (phân hoạch) cần 
tiến hành sắp xếp. 
• Ý tưởng: 
– Push phân hoạch đầu tiên (0, n-1) vào stack 
– Trong khi stack chưa rỗng 
• Pop một phân hoạch từ stack 
• Chọn phần tử trục trên phân hoạch này 
• Điều chỉnh phân hoạch tương ứng với trục 
• Push 2 phân hoạch bên trái và phải trục vào stack 
28 GV. Thiều Quang Trung 
Stack – Quick Sort 
• Push phân hoạch đầu tiên (0, n-1) vào 
stack 
• Trong khi stack chưa rỗng 
– Pop một phân hoạch từ stack 
– Chọn phần tử trục trên phân hoạch này 
– Điều chỉnh phân hoạch tương ứng với trục 
– Push 2 phân hoạch bên trái và phải trục vào 
stack 
(0,4) 
1 5 4 7 3 
0 1 2 3 4 
i j 
t 
3 5
1
(3,4) 
5 7
Stack rỗng 
Stop 
29 GV. Thiều Quang Trung 
Hàng đợi Queue 
Phòng vé 
30 GV. Thiều Quang Trung 
Queue – Định nghĩa 
• Hàng đợi là một cấu trúc: 
– Gồm nhiều phần tử có thứ tự 
– Hoạt động theo cơ chế “Vào trước, ra trước” 
(FIFO - First In First Out) 
31 GV. Thiều Quang Trung 
Queue – Định nghĩa 
• Các thao tác cơ bản trên hàng đợi: 
– InitQueue: khởi tạo hàng đợi rỗng 
– IsEmpty: kiểm tra hàng đợi rỗng? 
– IsFull: kiểm tra hàng đợi đầy? 
– EnQueue: thêm 1 phần tử vào cuối hàng 
đợi, có thể làm hàng đợi đầy 
– DeQueue: lấy ra 1 phần tử từ đầu Queue, 
có thể làm Queue rỗng 
32 GV. Thiều Quang Trung 
Queue 
• Minh họa thao tác EnQueue 
• Minh họa thao tác DeQueue 
33 GV. Thiều Quang Trung 
Cách xây dựng Queue 
– Sử dụng mảng một chiều 
– Sử dụng danh sách liên kết đơn 
34 GV. Thiều Quang Trung 
Queue – Sử dụng mảng 
• Dùng 1 mảng (QArray) để chứa các phần tử. 
• Dùng 1 số nguyên (QMax)để lưu số phần tử tối 
đa trong hàng đợi 
• Dùng 2 số nguyên (QFront, QRear) để xác định 
vị trí đầu, cuối hàng đợi 
• Dùng 1 số nguyên (QNumItems) để lưu số phần 
tử hiện có trong hàng đợi 
35 GV. Thiều Quang Trung 
Queue – Sử dụng mảng 
0 1 2 3 4 5 6 
Qarray 37 22 15 3 
QMax = 7 
QNumItems = 4 
QFront = 1 
QRear = 4 
36 GV. Thiều Quang Trung 
Queue số nguyên – Sử dụng mảng 
typedef struct QUEUE 
{ 
 int* QArray; 
 int QMax; 
 int QNumItems; 
 int QFront; 
 int QRear; 
}; 
37 GV. Thiều Quang Trung 
Queue số nguyên – Sử dụng mảng 
• Khi thêm nhiều phần tử sẽ xảy ra hiện tượng “tràn 
giả” 
• Giải pháp? Nối dài mảng (mảng động) hay sử dụng 
một mảng vô cùng lớn? 
0 1 2 3 4 5 6 
Qarray 37 22 15 3 7 9 
QMax = 7 
QNumItems = 6 
QFront = 1 
QRear = 6 
38 GV. Thiều Quang Trung 
Queue số nguyên – Sử dụng mảng 
• Xử lý mảng như một danh sách liên kết vòng 
0 1 2 3 4 5 6 
Qarray 37 22 15 3 7 9 
QMax = 7 
QNumItems = 6 
QFront = 1 
QRear = 6 
39 GV. Thiều Quang Trung 
Chỉ số mảng 0 1 2 3 4 5 6 
QArray 11 7 19 21 81 
QMax 7 
QNumItems 5 
QFront 1 
QRear 5 
VD: Cho queue như sau 
Queue số nguyên – Sử dụng mảng 
40 GV. Thiều Quang Trung 
1. Thêm giá trị 123 vào hàng đợi 
Queue số nguyên – Sử dụng mảng 
Chỉ số mảng 0 1 2 3 4 5 6 
QArray 11 7 19 21 81 123 
QMax 7 
QNumItems 6 
QFront 1 
QRear 6 
41 GV. Thiều Quang Trung 
2. Lấy một phần tử khỏi hàng đợi 
Queue số nguyên – Sử dụng mảng 
Chỉ số mảng 0 1 2 3 4 5 6 
QArray 11 7 19 21 81 123 
QMax 7 
QNumItems 5 
QFront 2 
QRear 6 
42 GV. Thiều Quang Trung 
3. Thêm giá trị 456 vào hàng đợi 
Queue số nguyên – Sử dụng mảng 
Chỉ số mảng 0 1 2 3 4 5 6 
QArray 456 11 7 19 21 81 123 
QMax 7 
QNumItems 6 
QFront 2 
QRear 0 
43 GV. Thiều Quang Trung 
Queue số nguyên – Sử dụng mảng 
bool InitQueue(QUEUE &q, int MaxItem) 
{ 
 q.QArray = new int[MaxItem]; 
 if (q.QArray == NULL) 
 return false; 
 q.QMax = MaxItem; 
 q.QNumItems = 0; 
 q.QFront = q.QRear = -1; 
 return true; 
} 
44 GV. Thiều Quang Trung 
Queue số nguyên – Sử dụng mảng 
bool IsEmpty(QUEUE q) 
{ 
 if (q.QNumItems == 0) 
 return true; 
 return false; 
} 
45 GV. Thiều Quang Trung 
Queue số nguyên – Sử dụng mảng 
bool IsFull(QUEUE q) 
{ 
 if (q.QMax == q.QNumItems) 
 return true; 
 return false; 
} 
46 GV. Thiều Quang Trung 
Queue số nguyên – Sử dụng mảng 
bool EnQueue(QUEUE &q, int newitem) 
{ 
 if (IsFull(q)) 
 return false; 
 q.QRear++; 
 if (q.QRear==q.QMax) 
 q.QRear = 0; 
 q.QArray[q.QRear] = newitem; 
 if (q.QNumItems==0) 
 q.QFront = 0; 
 q.QNumItems++; 
 return true; 
} 
47 GV. Thiều Quang Trung 
Queue số nguyên – Sử dụng mảng 
bool DeQueue(QUEUE &q, int &itemout) 
{ 
 if (IsEmpty(q)) 
 return false; 
 itemout = q.QArray[q.QFront]; 
 q.QFront++; 
 q.QNumItems--; 
 if (q.QFront==q.QMax) 
 q.QFront = 0; 
 if (q.QNumItems==0) 
 q.QFront = q.QRear = -1; 
 return true; 
} 
48 GV. Thiều Quang Trung 
Queue số nguyên – Sử dụng mảng 
bool QueueFront(const QUEUE &q, int &itemout) 
{ 
 if (IsEmpty(q)) 
 return false; 
 itemout = q.QArray[q.QFront]; 
 return true; 
} 
49 GV. Thiều Quang Trung 
Queue số nguyên – Sử dụng mảng 
bool QueueRear(const QUEUE &q, int 
&itemout) 
{ 
 if (IsEmpty(q)) 
 return false; 
 itemout = q.QArray[q.QRear]; 
 return true; 
} 
50 GV. Thiều Quang Trung 
Queue – Ví dụ ứng dụng 
• Quản lý việc thực hiện các tác vụ (task) trong môi 
trường xử lý song song 
• Hàng đợi in ấn các tài liệu 
• Vùng nhớ đệm (buffer) dùng cho bàn phím 
• Quản lý thang máy 
51 GV. Thiều Quang Trung 
Queue – Sử dụng DSLK 
typedef struct tagNODE 
{ 
 int data; 
 tagNODE* pNext; 
} NODE, *PNODE; 
typedef struct tagQUEUE 
{ 
 int NumItems; 
 PNODE pFront, pRear; 
} QUEUE; 
52 GV. Thiều Quang Trung 
Queue – Sử dụng DSLK 
• Các thao tác cơ bản 
bool InitQueue(QUEUE &q); 
bool IsEmpty(const QUEUE &q); 
bool IsFull(const QUEUE &q); 
bool EnQueue(QUEUE &q, int newitem); 
bool DeQueue(QUEUE &q, int& itemout); 
53 GV. Thiều Quang Trung 
Queue – Sử dụng DSLK 
bool InitQueue(QUEUE &q) 
{ 
 q.NumItems = 0; 
 q.pFront = q.pRear = NULL; 
 return true; 
} 
54 GV. Thiều Quang Trung 
Queue – Sử dụng DSLK 
bool IsEmpty(const QUEUE& q) 
{ 
 return (q.NumItems==0); 
} 
55 GV. Thiều Quang Trung 
Queue – Sử dụng DSLK 
bool IsFull(const QUEUE &q) 
{ 
 PNODE tmp = new NODE; 
 if (tmp==NULL) 
 return true; 
 delete tmp; 
 return false; 
} 
56 GV. Thiều Quang Trung 
Queue – Sử dụng DSLK 
bool EnQueue(QUEUE &q, int newitem) 
{ 
 if (IsFull(q)) 
 return false; 
 PNODE p = new NODE; 
 p->data = newitem; 
 p->pNext = NULL; 
 if (q.pFront==NULL && q.pRear==NULL) 
 q.pFront = q.pRear = p; 
 else 
 { 
 q.pRear->pNext = p; 
 q.pRear = p; 
 } 
 q.NumItems++; 
 return true; 
} 57 GV. Thiều Quang Trung 
Queue – Sử dụng DSLK 
bool DeQueue(QUEUE &q, int &itemout) 
{ 
 if (IsEmpty(q)) 
 return false; 
 PNODE p = q.pFront; 
 q.pFront = p->pNext; 
 itemout = p->data; 
 q.NumItems--; 
 delete p; 
 if (q.NumItems==0) 
 InitQueue(q); 
 return true; 
} 
58 GV. Thiều Quang Trung 
Khái niệm đệ qui 
• Khái niệm: đệ qui là hình thức có dùng lại chính 
nó. 
– Ví dụ: giai thừa của n là 1 nếu n là 0 hoặc là n nhân 
cho giai thừa của n-1 nếu n > 0 
• Quá trình đệ qui gồm 2 phần: 
– Trường hợp cơ sở (base case) 
– Trường hợp đệ qui: cố gắng tiến về trường hợp cơ sở 
• Ví dụ trên: 
– Giai thừa của n là 1 nếu n là 0 
– Giai thừa của n là n * (giai thừa của n-1) nếu n>0 
59 GV. Thiều Quang Trung 
Tính giai thừa 
• Định nghĩa không đệ qui: 
– n! = n * (n-1) *  * 1 
• Định nghĩa đệ qui: 
n! = 1 nếu n=0 
 n * (n-1)! nếu n>0 
• Mã C++: 
int factorial(int n) { 
 if (n==0) return 1; 
 else return (n * factorial(n - 1)); 
} 
60 GV. Thiều Quang Trung 
Thi hành hàm tính giai thừa 
n=2 
2*factorial(1) 
factorial (2) 
n=1 
1*factorial(0) 
factorial (1) 
n=0 
 return 1; 
factorial (0) 
1 
1 
6 
2 
n=3 
3*factorial(2) 
factorial (3) 
61 GV. Thiều Quang Trung 
Trạng thái hệ thống khi thi hành hàm 
tính giai thừa 
factorial(3) factorial(3) 
factorial(2) 
factorial(3) 
factorial(2) 
factorial(1) 
factorial(3) 
factorial(2) 
factorial(1) 
factorial(0) 
factorial(3) 
factorial(2) 
factorial(1) 
factorial(3) 
factorial(2) 
factorial(3) 
t 
Gọi hàm 
factorial(3) 
Gọi hàm 
factorial(2) 
Gọi hàm 
factorial(1) 
Gọi hàm 
factorial(0) 
Trả về từ 
hàm 
factorial(0) 
Trả về từ 
hàm 
factorial(1) 
Trả về từ 
hàm 
factorial(2) 
Trả về từ 
hàm 
factorial(3) 
Stack hệ thống 
Thời gian hệ thống 
t 
62 GV. Thiều Quang Trung 
Bài toán Tháp Hà nội 
• Luật: 
– Di chuyển mỗi lần một đĩa 
– Không được đặt đĩa lớn lên trên đĩa nhỏ 
63 GV. Thiều Quang Trung 
Bài toán Tháp Hà nội – Thiết kế hàm 
• Hàm đệ qui: 
– Chuyển (count-1) đĩa trên đỉnh của cột start sang 
cột temp 
– Chuyển 1 đĩa (cuối cùng) của cột start sang cột 
finish 
– Chuyển count-1 đĩa từ cột temp sang cột finish 
magic 
64 GV. Thiều Quang Trung 
Bài toán Tháp Hà nội – Mã C++ 
void move(int count, int start, int finish, int 
temp) { 
 if (count > 0) { 
 move(count − 1, start, temp, finish); 
 cout << "Move disk " << count << " 
from " << start 
 << " to " << finish << "." << endl; 
 move(count − 1, temp, finish, start); 
 } 
} 
65 GV. Thiều Quang Trung 
Bài toán Tháp Hà nội – Thi hành 
66 GV. Thiều Quang Trung 
Bài toán Tháp Hà nội – Cây đệ qui 
67 GV. Thiều Quang Trung 
Thiết kế các giải thuật đệ qui 
• Tìm bước chính yếu (bước đệ qui) 
• Tìm qui tắc ngừng 
• Phác thảo giải thuật 
– Dùng câu lệnh if để lựa chọn trường hợp. 
• Kiểm tra điều kiện ngừng 
– Đảm bảo là giải thuật luôn dừng lại. 
• Vẽ cây đệ qui 
– Chiều cao cây ảnh hưởng lượng bộ nhớ cần thiết. 
– Số nút là số lần bước chính yếu được thi hành. 
68 GV. Thiều Quang Trung 
Đệ qui đuôi (tail recursion) 
• Định nghĩa: câu lệnh thực thi cuối cùng là lời 
gọi đệ qui đến chính nó. 
• Khử: chuyển thành vòng lặp. 
69 GV. Thiều Quang Trung 
Khử đệ qui đuôi hàm giai thừa 
• Giải thuật: 
product=1 
for (int count=1; count < n; count++) 
product *= count; 
70 GV. Thiều Quang Trung 
Dãy số Fibonacci 
• Định nghĩa: 
– F0 = 0 
– F1 = 1 
– Fn = Fn-1 + Fn-2 khi n>2 
• Ví dụ: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,  
• Hàm đệ qui: 
int fibonacci (int n) { 
if (n<=0) return 0; 
if (n==1) return 1; 
else return (fibonacci(n-1) + fibonacci(n-2)); 
} 
71 GV. Thiều Quang Trung 
Dãy số Fibonacci – Cây thi hành 
Đã tính rồi 
72 GV. Thiều Quang Trung 
Dãy số Fibonacci – Khử đệ qui 
• Nguyên tắc: 
– Dùng biến lưu trữ giá trị đã tính của Fn-2 
– Dùng biến lưu trữ giá trị đã tính của Fn-1 
– Tính Fn = Fn-1 + Fn-2 và lưu lại để dùng cho lần sau 
• Giải thuật: 
int Fn2=0, Fn1=1, Fn; 
for (int i = 2; i <= n; i++) { 
 Fn = Fn1 + Fn2; 
 Fn2 = Fn1; Fn1 = Fn; 
} 
73 GV. Thiều Quang Trung 
GV: Thiều Quang Trung 74