Stack & Queue
ThS. Nguyễn Hà Giang Hutech - IT
Nguyen Ha Giang 2009
2
Giới thiệu
• LIFO: Last In First Out • Thao tác Pop, Push chỉ diễn ra ở 1 đầu
Nguyen Ha Giang 2009
3
Hiện thực stack
Mảng 1 chiều
Danh sách LK
Cấp phát động!
Kích thước stack khi quá thiếu, lúc quá thừa
Push/Pop khá dễ dàng
Push / Pop hơi phức tạp
Nguyen Ha Giang 2009
4
Khai báo
• Tạo cấu trúc Node cho stack
typedef struct node {
info; DataType struct node * next;
}NODE; typedef NODE * NodePtr;
pTop quản lý stack
pTop;
NodePtr pTop = NULL;
Khởi tạo stack
Nguyen Ha Giang 2009
5
Thao tác
• Các thao tác trên stack
Pop
InitStack
Push
IsEmpty
GetSize
Top
pTop
Đầu danh sách
Nguyen Ha Giang 2009
6
Pop
• Pop:
– Lấy ra phần tử đầu danh sách – Trả về nội dung và giải phóng nút
pTop
pTop
Pop
5
2
9
2
9
Nguyen Ha Giang 2009
7
Pop
int Pop(NodePtr &pTop) { NodePtr p; value; int if (pTop == NULL) {
printf(“Stack is empty!”); return -1;
} p = pTop; pTop = pTop->next; value = p->info; FreeNode(p); return value;
}
Nguyen Ha Giang 2009
8
Push
• Push
– Tạo Node mới – Đưa vào đầu stack
pTop
pTop
Push
new
2
9
8
2
9
Nguyen Ha Giang 2009
9
Push
void Push(NodePtr &pTop, int x) {
NodePtr node; node = NewNode(); node->info = x; node->next = pTop; pTop = node;
}
Nguyen Ha Giang 2009
10
Top
• Top:
– Xem nội dung của phần tử đầu stack
pTop
Top
5
2
9
pTop
5
2
9
Nguyen Ha Giang 2009
11
Top
int Top(NodePtr pTop) {
int value; if (pTop == NULL) {
printf(“Stack is empty!”); return -1;
} value = pTop->info; return value;
}
Nguyen Ha Giang 2009
12
ứng dụng
• Ứng dụng stack – Khử đệ quy:
• Tháp Hanoi, QuickSort…
– Áp dụng cho các bài toán dùng mô hình LIFO
Nguyen Ha Giang 2009
13
Tháp Hanoi
Move( số đĩa, cọc nguồn, cọc đích, cọc tạm)
• Tháp Hanoi
1
2
3
1
2
3
1
2
3
Move(n-1, 1, 3, 2);
Kết quả
Move(1, 1, 2, 3);
Move(n-1, 3, 2, 1);
1
2
3
1
2
3
Nguyen Ha Giang 2009
14
Tháp Hanoi
• Stack khử đệ quy
{n, src, des}
Stack lưu trữ thứ tự ngược
• • Các cọc đánh số 1, 2, 3 • Cọc temp = 6 – (src+des) 1. Push stack : {n, 1, 2} 2. Pop: Stack {n, src, des) • Nếu n =1: move src des • Ngược lại:
Nguyen Ha Giang 2009
15
– temp = 6 – (src+des) – Push stack : {n-1, temp, des} – Push stack : {1,src, des} – Push stack : {n-1,src, temp}
Tháp Hanoi
• Bài tập: Chương trình tháp Hanoi – Không đệ quy, dùng stack khử – Sử dụng dslk cho stack
Nguyen Ha Giang 2009
16
QuickSort
• Ý tưởng QuickSort ko đệ quy
– Dùng stack khử đệ quy – Stack lưu giữ {biên trái, biên phải} của đoạn – Khi phân đến [left, right] ta được • [left, i] các phần tử nhỏ hơn x • [i+1,j-1] các phần tử bằng x • [j, right] các phần tử lớn hơn x – Đưa vào stack đoạn bên phải – Nếu đoạn bên trái nhiều hơn 1 phần tử, cập nhật right
= i, lập lại với đoạn left, right mới tương tự. – Khi đoạn bên trái hết thì ta sẽ lấy trong stack ra – Quá trình lặp lại cho đến khi stack rỗng
Nguyen Ha Giang 2009
17
QuickSort
• Bài tập: cài đặt thuật giải Quicksort không
dùng đệ quy. – Dùng DSLK, mỗi nút chứa thông tin biên trái
và biên phải của đoạn chưa được sắp
– Áp dụng ý tưởng của slide trước để cài đặt
Nguyen Ha Giang 2009
18
Postfix
• Chuyển biểu thức trung tố sang hậu tố
Trung tố
Hậu tố
(6 / 2 + 3) * (7 - 4)
6 2 / 3 + 7 4 - *
Biểu thức hậu tố dễ tính toán hơn trong máy tính
Nguyen Ha Giang 2009
19
Postfix
• Duyệt qua từng phần tử trong infix C
– Nếu C là “(“ thì push stack. – Nếu C là “)” thì lấy tất cả phần tử trong stack cho đến khi gặp “(“. Xuất ra các phần tử này – Nếu C là toán tử: lấy trong stack ra tất cả toán tử có độ ưu tiên cao hơn C, xuất những phần tử này ra ngoài, và đưa C vào stack
– Ngược lại xuất C ra ngoài (trường hợp toán
hạng)
Nguyen Ha Giang 2009
20
Postfix
(2 * 3 + 7 / 8) * (5 – 1)
Đọc Xử lý Stack Output
( ( Đẩy vào stack
2 ( 2 Xuất
Do ‘*’ ưu tiên hơn ‘(‘ ở đỉnh stack * ( * 2 nên đưa ‘*’ vào stack
3 ( * 2 3 Xuất
Do ‘+’ ưu tiên thấp hơn ‘*’ ở đỉnh
stack nên ta lấy ‘*’ ra. + ( + 2 3 *
Tiếp tục so sánh ‘+’ với ‘(‘ thì ‘+’ ưu tiên cao hơn nên đưa vào stack
7 ( + 2 3 * 7 Xuất
/ ( + / 2 3 * 7 Do ‘/’ có độ ưu tiên cao hơn ‘+’ trên đỉnh stack nên đưa ‘/’ vào stack.
Nguyen Ha Giang 2009
21
8 ( + / 2 3 * 7 8 Xuất
Postfix
(2 * 3 + 7 / 8) * (5 – 1)
Đọc Stack Output Xử lý
) 2 3 * 7 8 / + Lấy trong stack ra cho đến khi gặp ngoặc (.
* 2 3 * 7 8 / + * Đưa vào stack
* ( 2 3 * 7 8 / + ( Đưa vào stack
* ( 2 3 * 7 8 / + 5 5 Xuất
- * ( - 2 3 * 7 8 / + 5 Độ ưu tiên của ‘-‘ cao hơn ‘(‘ trong đỉnh stack nên đưa ‘-‘ vào stack
* ( - 2 3 * 7 8 / + 5 1 1 Xuất
) * 2 3 * 7 8 / + 5 1 - Lấy trong stack ra cho đến khi gặp ngoặc đóng
trong
Nguyen Ha Giang 2009
22
2 3 * 7 8 / + 5 1 - * Lấy những phần tử còn lại stack và hiển thị
Postfix
• Tính giá trị biểu thức postfix
Postfix không cần có dấu ngoặc vẫn có thể tính đúng bằng cách đọc lần lượt biểu thức từ trái qua phải và dùng một stack để lưu trữ kết quả trung gian
34*5+
Nguyen Ha Giang 2009
23
Jan Lukasiewicz
Postfix
Ý tưởng • Khởi tạo stack = {Ø} • Đọc lần lượt các phần tử từ trái, kiểm tra
– Nếu toán hạng: Push stack – Nếu toán tử: lấy hai toán hạng, thực hiện
phép toán, kết quả Push vào stack • Sau khi đọc xong, trong stack còn duy
nhất một phần tử kết quả!
Nguyen Ha Giang 2009
24
Nguyen Ha Giang 2009
25
Giới thiệu
• FIFO • Thêm vào cuối và lấy ra ở đầu
Nguyen Ha Giang 2009
26
Mô tả
• Queue dùng DSLK
– Con trỏ pFront trỏ đầu danh sách – Con trỏ pRear trỏ đến cuối danh sách – Thao tác Remove diễn ra ở pFront – Tháo tác Insert diễn ra ở pRear – Thao tác thêm xoá dễ dàng ở hai đầu
Nguyen Ha Giang 2009
27
Mô tả
• Tạo cấu trúc Node cho Queue
typedef struct node {
info; DataType struct node * next;
}NODE; typedef NODE * NodePtr; struct Queue {
NodePtr NodePtr
pFront; pRear;
}
Nguyen Ha Giang 2009
28
Thao tác
• Các thao tác trên Queue
– Init – Insert – Remove – QueueFront – QueueRear – QueueSize – Clear
Nguyen Ha Giang 2009
29
Insert
• Insert
pFront
pRear
new
5
2
9
x
pFront
pRear
new
5
2
9
x
Nguyen Ha Giang 2009
30
Insert
void Insert(Queue &queue, int x) {
NodePtr node; node = NewNode(); node->info = x; node->next = NULL; if ( queue.pRear == NULL) { queue.pRear = node; queue.pFront = node;
} else {
queue.pRear->next = node; queue.pRear = node;
}
}
Nguyen Ha Giang 2009
31
Remove
• Remove
pFront
pRear
5
2
9
pFront
pRear
2
9
Nguyen Ha Giang 2009
32
Remove
int Remove(Queue & queue) {
NodePtr p; int value; if (queue.pFront == NULL) {
printf(“Queue is empty!”); return -1;
} if (queue.pFront == queue.pRear) { p = queue.pFront; queue.pFront = queue.pRear = NULL;
} else {
p =queue.pFront; queue.pFront = p->next;
} value = p->info; FreeNode(p); return value;
Nguyen Ha Giang 2009
33
}
ứng dụng
• Ứng dụng Queue
– Trong bài toán hàng đợi “Vào trước ra trước”
FIFO: • Hệ thống print server • Cơ chế thông điệp, bộ đệm, hàng đợi xử lý sự
kiện…
• Các ứng dụng đặt vé tàu lửa, máy bay… • Các hệ thống rút tiền…
Nguyen Ha Giang 2009
34
