TAILIEUCHUNG - Cấu trúc dữ liệu Stack

Stack là 1 cấu trúc dữ liệu tuyến tính mà chỉ có thể truy nhập tới phần tử cuối cùng của nó để nhập và xuất dữ liệu. Cấu trúc LIFO(Last in first out – vào sau ra trước). Xem hình minh hoạ ở slide tiếng anh | Chủ đề week 4 Cấu trúc dữ liệu Stack (ngăn xếp). Triển khai ngăn xếp dùng mảng Triển khai ngăn xếp dùng danh sách liên kết Cấu trúc dữ liệu Queue (hàng đợi). Triển khai queue vòng sử dụng mảng Triển khai queue sử dụng danh sách liên kết Bài tập với Stack và Queue. Stack Stack là 1 cấu trúc dữ liệu tuyến tính mà chỉ có thể truy nhập tới phần tử cuối cùng của nó để nhập và xuất dữ liệu. Cấu trúc LIFO(Last in first out – vào sau ra trước). Xem hình minh hoạ ở slide tiếng anh Các phép toán trên Stack Initialize(stack) - khởi tạo Empty(stack) - kiểm tra stack có rỗng không. Full(stack) - kiểm tra stack có đầy không Push(el,stack) – thêm fần tử el vào đỉnh của stack. Pop(stack) - lấy ra phần tử trên đỉnh stack Vậy làm thế nào để triển khai 1 stack? Phân tách khai triển từ đặc tả Interface (giao diện): đặc tả các phép toán được cho phép. Implementation (triển khai): cung cấp code cho các phép toán. Client: các code mà ta sử dụng. Có thể sử dụng mảng hoặc linked list để triển khai stack. Khách có thể làm việc ở mức trừu tượng cao. Khai triển sử dụng mảng Mỗi phần tử của stack được lưu trữ như là 1 phần tử của mảng. Stack rỗng: top=0;// top là chỉ số của phần tử đỉnh stack Stack đầy: top=max_element(chỉ số phần tử cuối của mảng). Đặc tả Stach () #define Max 50//số fần tử tối đa typedef int Eltype;//kiểu phần tử mảng là int typedef Eltype StackType[Max];//định nghĩa kiểu StackType là mảng Max phần tử có kiểu Eltype. int top; void Initialize(StackType stack); int empty(StackType stack); int full(StackType stack); void push(Eltype el, StackType stack); Eltype pop(StackType stack); Khai triển mảng của Stack () Initialize(StackType stack) { top=0; } empty(StackType stack) { return top == 0; } full(StackType stack) { return top == Max; } push(Eltype el, StackType stack) { if (full(stack)) printf(“stack tràn”); else stack[top++] = el; } Eltype pop(StackType stack) { if (empty(stack)) printf(“stack không còn để lấy ra”); else return stack[--top]; } Khai triển stack sử

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.