CÂU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - NGĂN XẾP

Là một danh sách tuyến tính Bổ sung một phần tử vào ngăn xếp hoặc lấy một phần tử ra khỏi ngăn xếp chỉ thực hiện ở một đầu gọi là đỉnh ngăn xếp N là độ dài của ngăn xếp Item là kiểu dữ liệu của các phần tử Ngăn xếp là một cấu trúc gồm 2 thành phần Biến top lưu chỉ số của phần tử mảng lưu phần tử ở đỉnh ngăn xếp Mảng E lưu các phần tử của ngăn xếp
Nội dung trích xuất từ tài liệu:
CÂU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - NGĂN XẾP NGĂN XẾP STACK KHÁI NIỆM NGĂN XẾP Là một danh sách tuyến tính  Bổ sung một phần tử vào ngăn  Đỉnh D xếp hoặc lấy một phần tử ra C khỏi ngăn xếp chỉ thực hiện ở B một đầu gọi là đỉnh ngăn xếp Item A Đáy Hình ảnh ngăn xếp BIỂU DIỄN CẤU TRÚC DỮ LIỆU #define Max N //Định nghĩa kiểu Item struct Stack{ Item E[Max] ; int top ; }; Stack S ; //Khai báo ngăn xếp S N là độ dài của ngăn xếp  Item là kiểu dữ liệu của các phần tử  Ngăn xếp là một cấu trúc gồm 2 thành phần  Biến top lưu chỉ số của phần tử mảng lưu phần tử ở  đỉnh ngăn xếp Mảng E lưu các phần tử của ngăn xếp  BIỂU DIỄN CẤU TRÚC DỮ LIỆU Max=7 6 Chưa có D top=3 C 2 Ngăn xếp B 1 A 0 E Mảng lưu trữ ngăn xếp BIỂU DIỄN CẤU TRÚC DỮ LIỆU Const Max = N ; Type Stack = Record E : Array[1..Max] Of Item ; top : 0..Max ; End ; Var S : Stack ; {Khai báo ngăn xếp S} N là độ dài của ngăn xếp  Item là kiểu dữ liệu của các phần tử  Ngăn xếp là một bản ghi gồm hai trường  Biến top lưu chỉ số của phần tử mảng lưu phần tử ở  đỉnh ngăn xếp Mảng E lưu các phần tử của ngăn xếp  BIỂU DIỄN CẤU TRÚC DỮ LIỆU Ví dụ: Ngăn xếp chứa thông tin học sinh #define Max 100 struct Hoc_sinh{ char ho_ten[25]; int tuoi; float dtb; }; struct Stack{ Hoc_sinh E[Max]; int top; }; Stack S; CÁC PHÉP TOÁN TRÊN NX Max=7 Khởi tạo ngăn xếp rỗng  6 5 void Initialize (Stack &S) { 4 S.top = -1; } 3 2 Kiểm tra ngăn xếp rỗng  1 0 int Empty (Stack S) { E top = -1 return (S.top == -1); } Ngăn xếp rỗng CÁC PHÉP TOÁN TRÊN NX Max=7 G 6 top = Max-1 F 5 E Kiểm tra ngăn xếp đầy 4  3 D int Full (Stack S) { C 2 return (S.top == Max-1); B } 1 A 0 E Ngăn xếp đầy CÁC PHÉP TOÁN TRÊN NX Bổ sung một phần tử X vào đỉnh ngăn xếp S  Max=7 Max=7 Max=7 6 6 6 5 5 5 X 4 X top = 4 top = 4 D 3 3 D D top 3 C 2 C C 2 2 B B B 1 1 1 A A A 0 0 0 E E E CÁC PHÉP TOÁN TRÊN NX Bổ sung một phần tử vào đỉnh ngăn xếp S  int PUSH (Stack &S, Item X) { if ( Full(S)) return 0; else { S.top++; S.E[S.top] = X; return 1; } } CÁC PHÉP TOÁN TRÊN NX Lấy một phần tử ở đỉnh ngăn xếp S  Max=7 Max=7 6 6 5 5 D 4 4 D 3 top = 3 C 2 C top = 2 B B 1 1 A A 0 0 E E CÁC PHÉP TOÁN TRÊN NX Lấy một phần tử ở đỉnh ngăn xếp S  Int POP (Stack &S, Item &Y) { ...