Bài giảng Ngăn xếp

Bài 5: Ngăn xếp 1. Định nghĩa một dạng hạn chế của danh sách: phép toán xen một phần tử mới vào danh sách và loại bỏ một phần tử khỏi danh sách, chỉ được phép thực hiện ở một đầu của danh sách -> gọi là đỉnh của stack. stack như một chồng đĩa, chỉ có thể đặt thêm đĩa mới lên trên đĩa trên cùng, hoặc lấy đĩa trên cùng ra khỏi chồng -> đĩa đặt vào chồng sau cùng, khi lấy ra sẽ được lấy ra đầu tiên -> danh sách LIFO (viết tắt của Last In First Out, nghĩa là, cái vào sau cùng ra đầu tiên). với một mô hình dữ liệu lớp các phép toán có thể thực hiện trên mô hình rất đa dạng và phong phú. Trong các ứng dụng chỉ có một số nhóm phép toán được sử dụng thường xuyên. Khi xét một mô hình dữ liệu với một tập hợp xác định các phép toán được phép thực hiện, ta có một kiểu dữ liệu trừu tượng (abstract data type). stack là một kiểu dữ liệu trừu tượng dựa trên mô hình dữ liệu danh sách, với các phép toán sau đây. 2. Các phép toán Giả sử S là stack các phần tử của nó có kiểu Item và x là một phần tử cùng kiểu với các phần tử của stack. 1. Khởi tạo stack rỗng (stack không chứa phần tử nào) void Initialize (stack *S) 2. Kiểm tra stack rỗng bool Empty (stack *S) Empty nhận giá trị true nếu S rỗng và false nếu S không rỗng. 3. Kiểm tra stack đầy bool Full (stack *S) Full nhận giá trị true nếu S đầy và false nếu không. 4. Thêm một phần tử mới x vào đỉnh của stack Void Push (Item x, stack *S) 5. Loại phần tử ở đỉnh của stack và gán giá trị của phần tử này cho x. Void Pop (stack S, Item *x) 3. Cài đặt stack bởi mảng sử dụng cài đặt danh sách để cài đặt stack độ dài tối đa của stack là max, các phần tử của stack có kiểu dữ liệu là Item, đỉnh của stack được chỉ bởi biến top. -> stack S=(a1,a2,...,an) có dạng: a1 a2 an 3. Cài đặt stack… #define max N struct STACK { int front, rear; Item element[max]; } typedef struct STACK; Với cách cài đặt này, S là Stack rỗng, nếu S->top = 0, và nó sẽ đầy nếu S->top = max. void Initialize (STACK S) { S.top = 0; } bool Empty (STACK S) { Empty = (S.top == 0) } Bool Full (STACK S) { Full = (S.top == max) } void Push (Item x, STACK *S, bool *OK) { if Full(S) OK = false; else { S.top = S.top + 1 S.element [top] = x ; OK = true } } void Pop (STACK S, Item *x, bool *OK) { if Empty (S) OK = false; else { x = S.element [top] ; S.top = S.top - 1 ; OK = true } } 4. Cài đặt stack bởi danh sách liên kết Tương tự như đối với danh sách: Đỉnh của stack là đầu của danh sách liên kết. Sử dung con trỏ S trỏ đến đỉnh stack. khai báo cấu trúc dữ liệu danh sách liên kết biểu diễn stack như sau : struct NODE { Item info; struct NODE *next; } typedef struct NODE; typedef NODE *STACK; Void Initialize (STACK S) { S = null; } bool Empty (STACK S) { if S == null return true else return false } bool Full (STACK S) { Full = false; } Void Push (Item x, STACK S, bool *OK) { NODE P; P = (STACK)malloc(sizeof(NODE)); P->infor = x ; P->next = S ; S = P ; OK = true } void Pop(STACK S, Item x; bool *OK) { if S == null OK = false else { P = S ; x = S->infor ; S = S->next ; OK = true ; free(P) ; } } 5. Ứng dụng của ngăn xếp Bài toán kí pháp nghịch đảo Ba Lan: xác định giá trị của một biểu thức. Trong các chương trình ta thường viết các lệnh gán X = biểu thức: số học hoặc logic. Khi thực hiện chương trình, phải xác định giá trị của biểu thức -> gán kết quả cho biến X. ? làm thế nào xd thuật toán xác định giá trị của biểu thức. xét các biểu thức số học: là một dãy các toán hạng (hằng, biến hoặc hàm) nối với nhau bởi các phép toán số học, có thể chứa các dấu ngoặc tròn. Để đơn giản chỉ xét các biểu thức số học chứa các phép toán hai toán hạng +, -, * và /. Khi tính giá trị của biểu thức, các phép toán trong ngoặc được thực hiện trước, rồi đến các phép toán * và / ,sau đó đến các phép toán + và - . Nếu cùng mức ưu tiên, các phép toán được thực hiện từ trái sang phải. 5. Ứng dụng… 5 + 8 / ( 3 + 1) * 3 Giá trị của biểu thức này được tính như sau 5 + 8/(3+1)*3 = 5+8/4 * 3 = 5+2 * 3 = 5+6 = 11 5. Ứng dụng… thuật toán xác định giá trị của một biểu thức số học. Thuật toán này gồm hai giai đoạn. 1. Chuyển biểu thức số học thông thường (dạng infix) sang biểu thức số học Ba lan postfix. 2. Tính giá trị của biểu thức số học Balan postfix -> bài toán kí pháp nghịch đảo Ba Lan 5. Ứng dụng… xác định biểu thức số học Balan postfix. thông thường, phép toán được đặt giữa hai toán hạng (a + b, a * b). Với cách viết Balan, phép toán được đặt sau các toán hạng. a + b, a * b trong cách viết Balan được viết là ab +, ab *. Ví dụ Biểu thức thông thường Biểu thức Balan a * b/ c ab * c / a * (b + c) - d/e abc + * de / - lưu ý: biểu thức số học Balan không chứa các dấu ngoặc, nó chỉ gồm các toán hạng và các dấu phép toán. 5. Ứng dụng… thuật toán xác định giá trị của biểu thức số học Balan 1. Đọc lần lượt các thành phần của biểu thức Balan từ trái sang phải. Nếu gặp toán hạng thì đẩy nó vào stack. Nếu gặp phép toán, thì rút hai toán hạng ở đỉnh stack ra và thực hiện phép toán này. Kết quả nhận được lại đẩy vào stack. 2. Lặp lại quá trình trên cho tới khi toàn bộ biểu thức được đọc qua. Lúc đó đỉnh của stack chứa giá trị các biểu thức. 5. Ứng dụng… void Eval (Exp E) { Read (E,z) ;// đọc một thành phần của biểu thức rồi gán cho z while (z != #) { if z là toán hạng Push (z, S) else { Pop (S,y) ; // Rút các toán hạng ở đỉnh stack Pop (S,x) ; w = x z y; //Thực hiện phép toán z với các toán hạng x và y } Push (w,s); } Read (E,z); } } thuật toán chuyển biểu thức số học thông thường sang biểu thức số học Balan. sử dụng stack S để lưu các dấu mở ngoặc (và các dấu phép toán + , -, * và /. Ta đưa vào ký hiệu $ để đánh dấu đáy của stack. Khi đỉnh stack chứa $, có nghĩa là stack rỗng. hàm Pri (hàm ưu tiên) như sau: Pri ($) thêm vào bên phải biểu thức E ký hiệu # để đánh dấu hết biểu thức. 1. Đọc một thành phần của biểu thức E (Đọc lần lượt từ trái sang phải) Giả sử thành phần được đọc là x. 1.1. Nếu x là toán hạng thì viết nó vào bên phải biểu thức E1. 1.2. Nếu x là dấu mở ngoặc (thì đẩy nó vào stack) 1.3. Nếu x là một trong các dấu phép toan + , -, *, / thì a. Xét phần tử y ở đỉnh stack b. Nếu Fri (y)  Fri(x) thì loại y khỏi stack, viết y vào bên phải E1 và quay lại bước a) c. Nếu Fri (y) = Pri(x)) { Pop (S,y) ; Write (y, E1) } Push (x,S) } Read (E,x) } // hết lệnh while x # write (#, E1); } 5. Ứng dụng… Ví dụ. Xét biểu thức : E = a * (b + ) - d # 5. Ứng dụng… Ví dụ làm ngay tại lớp:tính giá trị biểu thức: 7 * 8 - ( 5 + 6) Bài tập về nhà Viết thêm trong trường hợp có cả phép toán mod và div