tailieunhanh - Ngăn xếp

Phép toán 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. | NGĂN XẾP STACK CẤU TRÚC NGĂN XẾP Khái niệm, đặc điểm Lưu trữ kế tiếp của ngăn xếp Ngăn xếp móc nối Ứng dụng của ngăn xếp /36 Khái niệm, đặc điểm ngăn xếp Khái niệm Là một danh sách tuyến tính Phép toán 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 A B C D Đỉnh Đáy Hình ảnh ngăn xếp /36 Khái niệm, đặc điểm ngăn xếp Phần tử đưa vào ngăn xếp sau sẽ được lấy ra xử lí trước, phần tử đưa vào ngăn xếp trước sẽ được lấy ra xử lí sau. Được gọi là danh sách LIFO (Last - In - First - Out) /36 Lưu trữ kế tiếp của ngăn xếp Định nghĩa và khai báo cấu trúc dữ liệu Định nghĩa các phép toán và chương trình thực hiện các phép toán cơ bản /36 Định nghĩa và khai báo cấu trúc dữ liệu Ngăn xếp mảng là một bản ghi gồm có hai trường Trường 1 : là một số nguyên biểu diễn số phần tử có trong ngăn xếp Trường 2 : Là mảng một chiều có kích thước đủ lớn để lưu các phần tử của ngăn xếp /36 Định nghĩa và . | NGĂN XẾP STACK CẤU TRÚC NGĂN XẾP Khái niệm, đặc điểm Lưu trữ kế tiếp của ngăn xếp Ngăn xếp móc nối Ứng dụng của ngăn xếp /36 Khái niệm, đặc điểm ngăn xếp Khái niệm Là một danh sách tuyến tính Phép toán 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 A B C D Đỉnh Đáy Hình ảnh ngăn xếp /36 Khái niệm, đặc điểm ngăn xếp Phần tử đưa vào ngăn xếp sau sẽ được lấy ra xử lí trước, phần tử đưa vào ngăn xếp trước sẽ được lấy ra xử lí sau. Được gọi là danh sách LIFO (Last - In - First - Out) /36 Lưu trữ kế tiếp của ngăn xếp Định nghĩa và khai báo cấu trúc dữ liệu Định nghĩa các phép toán và chương trình thực hiện các phép toán cơ bản /36 Định nghĩa và khai báo cấu trúc dữ liệu Ngăn xếp mảng là một bản ghi gồm có hai trường Trường 1 : là một số nguyên biểu diễn số phần tử có trong ngăn xếp Trường 2 : Là mảng một chiều có kích thước đủ lớn để lưu các phần tử của ngăn xếp /36 Định nghĩa và khai báo cấu trúc dữ liệu Khai báo cấu trúc : const max= ; struct stack { int top ; ptu[max] ; } s ; /36 Định nghĩa và khai báo cấu trúc dữ liệu D C B A 0 1 2 3 max -1 Ngăn xếp Chưa có phần tử Mảng lưu trữ ngăn xếp s /36 Các phép toán cơ bản Khởi tạo danh sách rỗng : creat(s) Kiểm tra danh sách rỗng : empty(s) Kiểm tra danh sách đầy : full(s) Chèn phần tử x vào đỉnh của ngăn xếp : push(x,s) Loại phần tử đỉnh của ngăn xếp gán cho x : pop(s,x) /36 Các phép toán cơ bản Khởi tạo ngăn xếp rỗng void creat(stack &s) { = 0; } Kiểm tra ngăn xếp rỗng int empty(stack s) { return == 0 ; } 0 1 2 3 max -1 4 Ngăn xếp rỗng top = 0 /36 Các phép toán cơ bản Kiểm tra ngăn xếp đầy int full(stack s) { return == max ; } 0 1 2 3 max -1 s G F D C B A Ngăn xếp đầy top = max /36 Các phép toán cơ bản Bổ sung phần tử x vào đỉnh ngăn xếp s 0 1 2 6 s D C B A 4 5 top =4 0 1 2 3 6 s D C B A 5 top = 4 X top = 5 0 1 2 3 6 s X D C B A 5 max=7 3 4