Công nghệ phần mềm - Cấu trúc ngăn xếp (stack)

CẤU TRÚC NGĂN XẾP (STACK) Bộ môn Công nghệ phần mềm Khoa Công nghệ thông tin & Truyền thông Đại học Cần Thơ KHÁI NIỆM NGĂN XẾP
Là một dạng danh sách ñặc biệt mà việc thêm vào hay xóa phần tử chỉ thực hiện tại một ñầu, gọi là ñỉnh của ngăn xếp.
Làm việc theo nguyên tắc FILO(First In Last Out) hay LIFO (Last In First Out) PHÉP TOÁN TRÊN NGĂN XẾP
MAKENULL_STACK(S): khởi tạo ngăn xếp rỗng.
EMPTY_STACK(S): kiểm tra ngăn xếp rỗng.
TOP(S): phần tử ñầu tiên trên ñỉnh ngăn xếp.
POP(S): xóa phần tử ở ñỉnh ngăn xếp.
PUSH(X,S): thêm phần tử X vào ñỉnh ngăn xếp S.
FULL_STACK(S): kiểm tra ngăn xếp ñầy. CÀI ĐẶT NGĂN XẾP BẰNG MẢNG
Mô hình lưu trữ:
Khai báo: #define MaxLength typedef ElementType; typedef struct { ElementType Elements[MaxLength]; int top_index; } Stack; Stack S; elements top_index 0 1 . . . maxlength - 1 CÀI ĐẶT NGĂN XẾP BẰNG MẢNG
Khởi tạo ngăn xếp rỗng: void MakeNull_Stack(Stack *S){ S->top_index = MaxLength; } elements top_index 0 1 . . . maxlength - 1 CÀI ĐẶT NGĂN XẾP BẰNG MẢNG
Kiểm tra ngăn xếp rỗng ? int Empty_Stack(stack S){ return S.top_index == MaxLength; }
Kiểm tra ngăn xếp ñầy ? int Full_Stack(Stack S){ return S.top_index == 0; } CÀI ĐẶT NGĂN XẾP BẰNG MẢNG
Nếu ngăn xếp rỗng thì thông báo lỗi
Ngược lại, trả về nội dung phần tử mảng có chỉ số top_index. ElementType Top(stack S){ if (Empty_Stack(S)) printf("Loi! Ngan xep rong"); else return S.Elements[S.top_index]; }  Trả về phần tử ở ñỉnh ngăn xếp CÀI ĐẶT NGĂN XẾP BẰNG MẢNG
Nếu ngăn xếp rỗng thì báo lỗi
Ngược lại: tăng top_index lên 1 ñơn vị void Pop(Stack *S){ if (Empty_Stack(*S)) printf("Loi! Ngan xep rong!"); else S->top_index = S->top_index+1; }  Xóa phần tử ở ñỉnh ngăn xếp CÀI ĐẶT NGĂN XẾP BẰNG MẢNG
Nếu ngăn xếp ñầy thì báo lỗi
Ngược lại: giảm top_index 1 ñơn vị, ñặt X vào phần tử mảng có chỉ số top_index. void Push(ElementType X, Stack *S){ if (Full_Stack(*S)) printf("Loi! Ngan xep day!"); else{ S->top_index = S->top_index-1; S->Elements[S->top_idx] = X; }  Thêm phần tử vào ñỉnh ngăn xếp CÀI ĐẶT NGĂN XẾP BẰNG DSÁCH
Khai báo: typedef List Stack;
Tạo ngăn xếp rỗng: MakeNull_List
Kiểm tra ngăn xếp rỗng: Empty_List
Thêm phần tử: Insert_List tại First
Xóa phần tử: Delete_List tại First