tailieunhanh - Cấu trúc dữ liệu và giải thuật - chương 2

Một stack là một cấu trúc dữ liệu mà việc thêm vào và loại bỏ được thực hiện tại một đầu (gọi là đỉnh – top của stack). Là một dạng vào sau ra trước với tài liệu này các bạn sinh viên CNTT có thể nắm vững các kiến thức về stack. | CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (501040) Chương 2: Stack Mô tả stack Một stack là một cấu trúc dữ liệu mà việc thêm vào và loại bỏ được thực hiện tại một đầu (gọi là đỉnh – top của stack). Là một dạng vào sau ra trước – LIFO (Last In First Out) Ví dụ về stack Stack rỗng: Đẩy (push) Q vào: Đẩy A vào: Lấy (pop) ra một => được A: Lấy ra một => được Q và stack rỗng: Q Q A Q A Q Ứng dụng: Đảo ngược danh sách Yêu cầu: Đảo ngược một danh sách nhập vào Giải thuật: 1. Lặp lại n lần . Nhập vào một giá trị . Đẩy nó vào stack 2. Lặp khi stack chưa rỗng . Lấy một giá trị từ stack . In ra Đảo ngược danh sách – Ví dụ Cần nhập 4 số vào Ban đầu Nhập 1 1 Nhập 5 1 5 Nhập 7 1 5 7 Nhập 3 1 5 7 3 Lấy ra => 3 1 5 7 3 Lấy ra => 7 1 5 7 Lấy ra => 5 1 5 Lấy ra => 1 1 Stack đã rỗng Ngừng Đảo ngược danh sách – Mã C++ #include using namespace std; int main( ) { int n; double item; stack numbers; cout > n; for (int i = 0; i > item; (item); } while (!( )) { cout =1): bộ thứ tự (Sn-1, t) Sn-1: dãy có chiều dài n-1 thuộc kiểu T t là một giá trị thuộc kiểu T. Stack trừu tượng Một stack kiểu T: Một dãy hữu hạn kiểu T Một số tác vụ: 1. Khởi tạo stack rỗng (create) 2. Kiểm tra rỗng (empty) 3. Đẩy một giá trị vào trên đỉnh của stack (push) 4. Bỏ giá trị đang có trên đỉnh của stack (pop) 5. Lấy giá trị trên đỉnh . | CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (501040) Chương 2: Stack Mô tả stack Một stack là một cấu trúc dữ liệu mà việc thêm vào và loại bỏ được thực hiện tại một đầu (gọi là đỉnh – top của stack). Là một dạng vào sau ra trước – LIFO (Last In First Out) Ví dụ về stack Stack rỗng: Đẩy (push) Q vào: Đẩy A vào: Lấy (pop) ra một => được A: Lấy ra một => được Q và stack rỗng: Q Q A Q A Q Ứng dụng: Đảo ngược danh sách Yêu cầu: Đảo ngược một danh sách nhập vào Giải thuật: 1. Lặp lại n lần . Nhập vào một giá trị . Đẩy nó vào stack 2. Lặp khi stack chưa rỗng . Lấy một giá trị từ stack . In ra Đảo ngược danh sách – Ví dụ Cần nhập 4 số vào Ban đầu Nhập 1 1 Nhập 5 1 5 Nhập 7 1 5 7 Nhập 3 1 5 7 3 Lấy ra => 3 1 5 7 3 Lấy ra => 7 1 5 7 Lấy ra => 5 1 5 Lấy ra => 1 1 Stack đã rỗng Ngừng Đảo ngược danh sách – Mã C++ #include using namespace std; int main( ) { int n; double item; stack numbers; cout > n; for (int i = 0; i > item; .