Bài giảng Cấu trúc ngăn xếp (Stack)

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ạimột đầu, gọi là đỉnh của ngăn xếp. Nhằm giúp các bạn hiểu hơn về vấn đề này, mời các bạn cùng tham khảo nội dung bài giảng "Cấu trúc ngăn xếp - Stack" dưới đây. Hy vọng nội dung bài giảng là tài liệu tham khảo hữu ích cho các bạn.
Nội dung trích xuất từ tài liệu:
Bài giảng 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: 0 #define … MaxLength 1 typedef … ElementType; . typedef struct { . ElementType Elements[MaxLength]; top_index . int top_index; } Stack; Stack S; maxlength - 1 elementsCÀI ĐẶT NGĂN XẾP BẰNG MẢNG Khởi tạo ngăn xếp rỗng: elements 0 void MakeNull_Stack(Stack *S){ 1 S->top_index = MaxLength; . } . . maxlength - 1 top_indexCÀ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 Trả về phần tử ở ñỉnh ngăn xếp 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]; }CÀI ĐẶT NGĂN XẾP BẰNG MẢNG Xóa phần tử ở ñỉnh ngăn xếp 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;}CÀI ĐẶT NGĂN XẾP BẰNG MẢNG Thêm phần tử vào ñỉnh ngăn xếp 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;}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