Giao trinh CAU RUC DU LIEU VA GIAI THUAT

Stack & Queue
Giới thiệu
LIFO: Last In First Out
Thao tác Pop, Push chỉ diễn ra ở 1 đầu
Hiện thực stack
Mảng 1 chiều
Danh sách LK
Kích thước stack khi quá thiếu, lúc quá thừa
Cấp phát động!
Push / Pop hơi phức tạp
Push/Pop khá dễ dàng
Khai báo
Tạo cấu trúc Node cho stack
typedef struct node
{
DataType info;
struct node * next;
}NODE;
typedef NODE * NodePtr;

NodePtr pTop;
pTop = NULL;
pTop quản lý stack
Khởi tạo stack
Thao tác
Các thao tác trên stack
InitStack
IsEmpty
Pop
Push
Top
pTop
Push
Pop
Đầu
danh sách
GetSize
Pop
Pop:
Lấy ra phần tử đầu danh sách
Trả về nội dung và giải phóng nút
5
2
9
pTop
Pop
2
9
pTop
Pop
int Pop(NodePtr &pTop) {
NodePtr p;
int value;
if (pTop == NULL) {
printf(“Stack is empty!”);
return -1;
}
p = pTop;
pTop = pTop->next;
value = p->info;
FreeNode(p);
return value;
}
Push
Push
Tạo Node mới
Đưa vào đầu stack
2
9
pTop
Push
8
2
9
pTop
new
Push
void Push(NodePtr &pTop, int x)
{
NodePtr node;
node = NewNode();
node->info = x;
node->next = pTop;
pTop = node;
}
Top
Top:
Xem nội dung của phần tử đầu stack
5
2
9
pTop
Top
5
2
9
pTop
Top
int Top(NodePtr pTop)
{
int value;
if (pTop == NULL)
{
printf(“Stack is empty!”);
return -1;
}
value = pTop->info;
return value;
}
ứ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
Tháp Hanoi
Tháp Hanoi
Move( số đĩa, cọc nguồn, cọc đích, cọc tạm)
Move(n-1, 1, 3, 2);

Move(1, 1, 2, 3);

Move(n-1, 3, 2, 1);
1
2
3
1
2
3
1
2
3
Kết quả
Tháp Hanoi
Stack khử đệ quy
{n, src, des}
Các cọc đánh số 1, 2, 3
Cọc temp = 6 – (src+des)
Push  stack : {n, 1, 2}
Pop: Stack  {n, src, des)
Nếu n =1: move src  des
Ngược lại:
temp = 6 – (src+des)
Push  stack : {n-1, temp, des}
Push  stack : {1,src, des}
Push  stack : {n-1,src, temp}

Stack lưu trữ thứ tự ngược
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

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
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

Postfix
Chuyển biểu thức trung tố sang hậu tố

(6 / 2 + 3) * (7 - 4)
6 2 / 3 + 7 4 - *
Trung tố
Hậu tố

Biểu thức hậu tố dễ tính toán hơn trong máy tính
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)
Postfix
(2 * 3 + 7 / 8) * (5 – 1)
Postfix
Postfix
Tính giá trị biểu thức postfix
34*5+
Jan Lukasiewicz
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
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ả!
Giới thiệu
FIFO
Thêm vào cuối và lấy ra ở đầu
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

Mô tả
Tạo cấu trúc Node cho Queue
typedef struct node
{
DataType info;
struct node * next;
}NODE;
typedef NODE * NodePtr;
struct Queue
{
NodePtr pFront;
NodePtr pRear;
}
Thao tác
Các thao tác trên Queue
Init
Insert
Remove
QueueFront
QueueRear
QueueSize
Clear
Insert
Insert
5
2
9
pFront
pRear
x
new
5
2
9
pFront
pRear
x
new
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;
}
}
Remove
Remove
5
2
9
pFront
pRear
2
9
pRear
pFront
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;
}
ứ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…