ng
ki u d ả ể ữ ừ ượ
Mô t li u tr u t ệ stack
Nội dung
Mô tả kiểu dữ liệu trừu tượng: stack Cài đặt Các ứng dụng minh họa
Phân tích cú pháp: XHTML, C++ Lời gọi hàm Cú pháp nghịch đảo Balan
Stack là một cấu trúc dữ liệu hoạt động theo cơ
Mô tả chế lastin—firstout (LIFO): Mỗi lần chỉ được đưa vào hoặc lấy ra khỏi stack một
Đối tượng được lấy ra khỏi stack là đối tượng được
đối tượng
Các thao tác chèn và lấy ra được gọi là push và pop
chèn vào stack mới nhất
Mô tả
A
B
C
D
... M
N
top
Có hai lỗi liên quan với kiểu dữ liệu trừu tượng này:
pop một stack rỗng hoặc Chưa định nghĩa vị trí top của một stack rỗng
Hiện thực
Chỉ có thể chèn vào hoặc lấy ra trong
thời gian O(1) tại cuối dãy
Vì vậy, có thể hiện thực stack bằng
việc push và pop ở cuối dãy:
0
1
2
3
4
6
8
11 15 17 18 22
top
Nếu mảng bị đầy, ta có các tùy chọn:
Errors 1. Tăng kích thước mảng, 2. Thông báo lỗi, 3. Bỏ qua phần tử đang push vào Stack, 4. Cho tiến trình ngưng lại chờ đến khi gặp thao tác
pop ra từ Stack
Stack, sử dụng mảng Giả sử Stack chứa các phần tử kiểu nguyên Khai báo cấu trúc Stack
Typedef struct Stack {
int *arrStack; // mảng chứa các phần tử int max; // số phần tử tối đa // vị trí đỉnh Stack int top;
}
Thao tác khởi tạo Stack rỗng
Stack, sử dụng mảng
int Init(Stack &s, int maxItems) {
s.arrStack = new int(maxItems); if (s.arrStack == NULL)
return 0; // không cấp phát được bộ nhớ
s.max = maxItems; s.top = -1; // chưa có phần tử nào trong Stack return 1; // khởi tạo thành công
}
Stack, sử dụng mảng
Thao tác kiểm tra Stack rỗng
int IsEmpty(const Stack &s) {
Stack rỗng
if (s.top == -1) return 1; //
return 0; //
Stack không rỗng }
Stack, sử dụng mảng
Thao tác kiểm tra Stack đầy
int IsFull(const Stack &s) {
if (s.top == s.max -1)
return 1; // Stack đầy return 0; // Stack chưa
đầy }
Thao tác Push: thêm 1 phần tử vào đỉnh Stack
Stack, sử dụng mảng int Push(Stack &s, int newItem) {
if (IsFull(s))
return 0; // Stack đầy, không thêm vào được
s.top++; s.arrStack[s.top] = newItem; return 1; // thêm thành công
}
Thao tác Pop: lấy ra 1 phần tử từ đỉnh Stack
Stack, sử dụng mảng
int Pop(Stack &s, int &outItem) {
if (IsEmpty(s))
return 0; // Stack rỗng, không lấy ra được
outItem = s.arrStack[s.top]; s.top--; return 1; // lấy ra thành công
}
khai báo cấu trúc 1 phần tử trong stack
Stack, sử dụng danh sách liên kết Typedef struct tagSTACK_NODE {
int Data; tagSTACK_NODE *next;
} S_Node;
khai báo cấu trúc stack
Typedef S_Node *SList;
Stack, sử dụng danh sách liên kết
Thao tác khởi tạo Stack rỗng
void InitStack(SList s) {
s = NULL;
}
Stack, sử dụng danh sách liên kết
Thao tác kiểm tra Stack rỗng
int IsEmpty(SList s) {
if(s == NULL)
return 1; // Stack rỗng
return 0; // Stack không rỗng
}
Stack, sử dụng danh sách liên kết Thao tác Push: thêm 1 phần tử vào đỉnh Stack
int Push(SList s, int newItem) {
SList pNew = new S_Node; pNew fi Data = newItem; pNew fi next = s; s = pNew; return 1; // thêm thành công
}
Stack, sử dụng danh sách liên kết Thao tác Pop: lấy ra 1 phần tử từ đỉnh Stack
int Pop(SList s, int &outItem) {
if (IsEmpty(s))
return 0; // Stack rỗng, không lấy ra được
outItemp = s fi Data; SList temp = s; s = s fi next; delete temp; return 1; // lấy ra thành công
}
Applications phân tích cú pháp (parsing code): Kiểm tra các dấu ngoặc đơn XML (e.g., XHTML)
Trong trình biên dịch (thông dịch), khi thực hiện các
thủ tục, Stack được sử dụng để lưu môi trường của các thủ tục Khử đệ qui Tổ chức lưu vết các quá trình tìm kiếm theo chiều sâu
Xử lý các thao tác undo/redo Cú pháp nghịch đảo Balan
và quay lui.
Applications Cách giải quyết vấn đề: Giải quyết một vấn đề có thể dẫn đến nhiều bài toán
Một bài toán có thể là kết quả của những bài toán nhỏ
khác nhau
Khi các bài toán nhỏ hơn đã được giải quyết, điều ta
hơn.
quan tâm là trở về bài toán ban đầu
Parsing
Hầu hết việc phân tích cú pháp đều dùng Stack Những ví dụ gồm có:
Đối sánh các tag trong XHTML Đối sánh các dấu ngoặc ( ... ) [ ... ] { ... }
đơn vuông, và kép trong C++
Phân tích cú pháp trong XHTML
XHTML sử dụng các tag lồng nhau
Tags mở,ví dụ ,
Ví dụ
This appears in the browswer.
Nesting chỉ ra rằng bất kỳ tag đóng nào cũng
Phân tích cú pháp trong XHTML phải đối sánh với tag mở gần nhất Chiến lược phân tích trong XHTML: Đọc trang tài liệu một cách tuyến tính. Đặt tag mở vào stack Khi gặp một tag đóng, kiểm tra nó có đối sánh với tag
đang ở đỉnh stack ?
Phân tích cú pháp trong XHTML
Hello
This appears in the browswer.
Phân tích cú pháp trong XHTML
Hello
This appears in the browswer.
Phân tích cú pháp trong XHTML
This appears in the browswer.
Phân tích cú pháp trong XHTML
This appears in the browswer.
Phân tích cú pháp trong XHTML
Hello
This appears in the browswer.
Phân tích cú pháp trong XHTML
Hello
This appears in the browswer.
Phân tích cú pháp trong XHTML
Hello
This appears in the browswer.
Phân tích cú pháp trong XHTML
Hello
This appears in the browswer.
Phân tích cú pháp trong XHTML
Hello
This appears in the browswer.
Phân tích cú pháp trong XHTML
Hello
This appears in the browswer.
Phân tích cú pháp trong XHTML
Hello
This appears in the browswer.
Phân tích cú pháp trong XHTML
Hello
This appears in the browswer.
Ta đã kết thúc việc phân tích cú pháp, và stack
Phân tích cú pháp trong XHTML đã rỗng
Những lỗi có thể xảy ra:
Tag đóng không phù hợp với tag mở trên đỉnh stack Còn tag đóng khi stack rỗng stack không rỗng khi đã ở cuối tài liệu
Phân tích cú pháp trong C++
Giống như tag mở và tag đóng, các dấu ngoặc trong C++ cũng được lồng nhau một cách tương tự:
int initialize( int * array, int
n )
{ for ( int i = 0; i < n; ++i ) { array[i] = 0; } }
Lời gọi hàm
Hãy xem đoạn chương trình sau:
#include
return 0; }
Lời gọi hàm cũng tương tự như giải quyết vấn đề
Lời gọi hàm đã trình bày trước đây: Ta viết một hàm để giải quyết bài toán Hàm này cần phải giải những bài toán con nhỏ hơn, vì
Một khi hàm con đã thực hiện xong, nó trở về nơi đã
vậy nó phải gọi hàm khác
gọi nó
Thông thường, biểu thức toán được biểu diễn dưới
Cú pháp nghịch đảo Balan
dạng sau:
(3 + 4) × 5 – 6
Toán tử được đặt giữa các toán hạng Yếu điểm: cần các dấu ngoặc ( parentheses)
= 29 = 17 = –1 = –7
(3 + 4) × 5 – 6 3 + 4 × 5 – 6 3 + 4 × (5 – 6) (3 + 4) × (5 – 6)
Thay vào đó, ta có thể đặt các toán hạng đứng
Cú pháp nghịch đảo Balan trước các toán tử:
(3 + 4) × 5 – 6 3 4 + 5 × 6 –
Đọc từ trái sang, thực hiện thao tác trên hai toán
hạng sau cùng nhất:
3 4 + 5 × 6 – 7 5 × 6 – 35 6 – 29
Cú pháp nghịch đảo Balan
Ví dụ:
3 4 5 × + 6 – 3 20 + 6 – 23 6 – 17 3 4 5 6 – × + 3 4 –1 × + 3 –4 + –1
Ưu điểm:
Cú pháp nghịch đảo Balan Không có sự tối nghĩa, và cũng không cần các dấu ngoặc Tương tự với tiến trình tính toán trên máy tính:
Các toán hạng được load vào thanh ghi trước khi thực hiện
phép toán
Cú pháp nghịch đảo Balan Cú pháp nghịch đảo Balan, được xử lý bằng cách dùng Stack:
Các toán hạng được đặt vào stack. Khi gặp toán tử:
pop hai phần tử trên đỉnh stack, Thực hiện thao tác, và push kết quả vào lại stack
Cú pháp nghịch đảo Balan
Đánh giá cú pháp nghịch đảo ba lan
khi sử dụng stack:
1 2 3 + 4 5 6 × – 7 × + – 8 9
× +
Cú pháp nghịch đảo Balan
Push 1 lên stack
× +
1
1 2 3 + 4 5 6 × – 7 × + – 8 9
Cú pháp nghịch đảo Balan
Push 2 vào stack
× +
2 1
1 2 3 + 4 5 6 × – 7 × + – 8 9
Cú pháp nghịch đảo Balan
Push 3
× +
3 2 1
1 2 3 + 4 5 6 × – 7 × + – 8 9
Cú pháp nghịch đảo Balan
Pop 3 và 2, tiếp theo push 2 + 3 = 5
× +
5 1
1 2 3 + 4 5 6 × – 7 × + – 8 9
Cú pháp nghịch đảo Balan
Push 4
× +
4 5 1
1 2 3 + 4 5 6 × – 7 × + – 8 9
Cú pháp nghịch đảo Balan
Push 5
× +
5 4 5 1
1 2 3 + 4 5 6 × – 7 × + – 8 9
Cú pháp nghịch đảo Balan
Push 6
× +
6 5 4 5 1
1 2 3 + 4 5 6 × – 7 × + – 8 9
Cú pháp nghịch đảo Balan
Pop 6 và 5 sau đó push 5 × 6 = 30
× +
30 4 5 1
1 2 3 + 4 5 6 × – 7 × + – 8 9
Pop 30 và 4 tiếp tục push 4 – 30 = –26
Cú pháp nghịch đảo Balan
–26 5 1
1 2 3 + 4 5 6 × – 7 × + – 8 9 × +
Cú pháp nghịch đảo Balan
Push 7
× +
7 –26 5 1
1 2 3 + 4 5 6 × – 7 × + – 8 9
Cú pháp nghịch đảo Balan
Pop 7 và –26 ; push –26 × 7 = –182
× +
–182 5 1
1 2 3 + 4 5 6 × – 7 × + – 8 9
Cú pháp nghịch đảo Balan
Pop –182 và 5 ; push –182 + 5 = –177
× +
–177 1
1 2 3 + 4 5 6 × – 7 × + – 8 9
Cú pháp nghịch đảo Balan
Pop –177 và 1 ; push 1 – (–177) = 178
× +
178
1 2 3 + 4 5 6 × – 7 × + – 8 9
Cú pháp nghịch đảo Balan
Push 8
× +
8 178
1 2 3 + 4 5 6 × – 7 × + – 8 9
Cú pháp nghịch đảo Balan
Push 9
× +
9 8 178
1 2 3 + 4 5 6 × – 7 × + – 8 9
Cú pháp nghịch đảo Balan
Pop 9 và 8 ; push 8 × 9 = 72
× +
72 178
1 2 3 + 4 5 6 × – 7 × + – 8 9
Cú pháp nghịch đảo Balan
Pop 72 và 178 ; push 178 + 72 = 250
× +
250
1 2 3 + 4 5 6 × – 7 × + – 8 9
Vì vậy
Cú pháp nghịch đảo Balan
1 2 3 + 4 5 6 × – 7 × + – 8 9 × +
có kết quả là giá trị tại đỉnh stack: 250
Cú pháp tương đương như sau:
((1 – ((2 + 3) + ((4 – (5 × 6)) × 7))) + (8 × 9))
Nếu sử dụng trật tự ưu tiên của toán tử:
1 – (2 + 3 + (4 – 5 × 6) × 7) + 8 × 9
