12. k'n stack, p2 luu tru stack...
12.Khái niệm cấu trúc dữ liệu Stack ? Phương pháp lưu trữ Stack ? Các phép toán với Stack ?
Stack ( ngăn xếp) là 1 kiểu cấu trúc dữ liệu đặc biệt trong đó việc bổ sung hay loại bỏ 1 phần tử chỉ được thực hiền ở 1 đầu của ngăn xếp và được gọi là đỉnh. Vì lý do đó mà ngăn xếp được gọi là danh sách không đầy đủ so với danh sách đặc vì đvs danh sách đặc ta có thể bổ sung hay loại bỏ phần tử ở mọi vị trí.
Ta có 1 stack như sau :
….
Tuy là danh sách không đầy đủ nhưng kiểu cấu trúc dữ liệu stack lại có rất nhiều ứng dụng trong cấu trúc dữ liệu và giải thuật nhất là trong việc thiết kế các phần mềm hệ thống mà cấu trúc dữ liệu khác không thể thay thế được
Do đặc điểm bổ sung hoặc loại bỏ chỉ ở 1 đầu nên ngăn xếp được gọi là danh sách kiểu LIFO ( last in first output)
Vd: xét bài toán thiết lập 1 chương trình hệ thống để đổi số từ hệ 10 sang hệ 2. đây là chương trình bắt buộc phải có mặt trong chương trình dịch vì số liệu đưa vào là hệ 10 nhưng cơ sở tính toán trong máy là hệ 2. ta viết giải thuật đổi số này lầ lấy số hệ10 chia liên tiếp cho 2, thương sô cuối cùng và số dư lấy theo chiều ngược lại chính là số hệ 2 cần tìm. Do đặc điểm chữ số xuất hiện cưới cùng lại có mặt đầu tiên trong dãy nhị phân và cso đầu tiên xuất hiện trong phép chia lại là cso cuối cùng của dãy nhị phân nên cấu trúc dữ liệu kiểu stack là loại duy nhất được dùng trong thiết kế giải thuật này.
-Lưu trữ stack
Vì stack không phải là 1 kiểu cấu trúc dữ liệu tiền định tức là không được thiết kế sẵn trong lập trình nên để lưu trữ ta phải sử dụng 1 cấu trúc dữ liệu thông dụng khác đó là mảng 1 chiều. ta sd mảng 1 chiều Q[n] để lưu trữ lần lượt các tp của ngăn xếp
….
- các phép toán với stack
Bổ sung : top= top+1
Loại bỏ : top= top-1
Đvs ngăn xếp việc bổ sung hay loại bỏ chỉ tác động đến phần tử ở đỉnh chứ không liên quan đến các phần tử khác. Về bản chất là chỉnh con trỏ tăng lên hoặc giảm đi
Bạn đang đọc truyện trên: AzTruyen.Top