Bài giảng Cấu trúc dữ liệu - Chương V: 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
Trường Cao đẳng Kinh tế Đối ngoại
• Khái niệm ngăn xếp1
• Phương pháp xây dựng stack2
• Các thao tác cơ bản trên stack3
• Kiểu queue - hàng đợi4
• Các thao tác cơ bản trên queue5
• Đệ qui và các bài toán đệ qui6
Nội dung
2GV. 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
3GV. 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
4GV. Thiều Quang Trung
Thao tác thêm - Push vào Stack
Top
P
U
SH
5GV. Thiều Quang Trung
Thao tác lấy - Pop khỏi stack
Top
P
O
P
6GV. 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
7GV. 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ớ
8GV. 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
9GV. 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;
10GV. 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; 
}
11GV. 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;
}
12GV. 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;
}
13GV. 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;
}
14GV. 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;
}
15GV. 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)
16GV. 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
? ?
17GV. Thiều Quang Trung
Stack – Sử dụng DSLK
9
7
4

N
StkCnt StkTop
7
Data Link
9
Data Link

4
Data Link
18GV. 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
19GV. 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;
};
20GV. 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
21GV. Thiều Quang Trung
Stack số nguyên – Sử dụng DSLK
void InitStack(STACK &s)
{
s.StkTop = NULL;
s.StkCount = 0;
}
22GV. 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;
}
23GV. 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;
}
24GV. 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
25GV. 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
26GV. 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
• 
27GV. 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
28GV. 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
29GV. Thiều Quang Trung
Hàng đợi Queue
Phòng vé
30GV. 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)
31GV. 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
32GV. Thiều Quang Trung
Queue
• Minh họa thao tác EnQueue
• Minh họa thao tác DeQueue
33GV. 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
34GV. 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
35GV. 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
36GV. 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;
};
37GV. 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
38GV. 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
39GV. 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
40GV. 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
41GV. 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
42GV. 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
43GV. 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;
}
44GV. 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;
}
45GV. 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;
}
46GV. 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;
}
47GV. 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;
}
48GV. 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;
}
49GV. 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;
}
50GV. 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
51GV. 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;
52GV. 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);
53GV. Thiều Quang Trung
Queue – Sử dụng DSLK
bool InitQueue(QUEUE &q)
{
q.NumItems = 0;
q.pFront = q.pRear = NULL;
return true;
}
54GV. Thiều Quang Trung
Queue – Sử dụng DSLK
bool IsEmpty(const QUEUE& q)
{
return (q.NumItems==0);
}
55GV. 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;
}
56GV. 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;
} 57GV. 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;
}
58GV. 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
59GV. 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));
}
60GV. 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)
61GV. 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
62GV. 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ỏ
63GV. 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
64GV. 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);
}
}
65GV. Thiều Quang Trung
Bài toán Tháp Hà nội – Thi hành
66GV. Thiều Quang Trung
Bài toán Tháp Hà nội – Cây đệ qui
67GV. 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.
68GV. 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.
69GV. 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;
70GV. 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));
}
71GV. Thiều Quang Trung
Dãy số Fibonacci – Cây thi hành
Đã tính rồi
72GV. 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;
}
73GV. Thiều Quang Trung
GV: Thiều Quang Trung 74