Để cài đặt ngăn xếp với hai thao tác thêm vào (push) và lấy ra (pop)
Để cài đặt ngăn xếp với hai thao tác thêm vào (push) và lấy ra (pop), ta có thể dùng mảng một chiều. Khi đó, các phần tử trong mảng sẽ là các phần tử đang có trong ngăn xếp.
Giải Chuyên đề Tin 12 Bài 2: Kiểu dữ liệu ngăn xếp - Cánh diều
Hoạt động 2 trang 14 Chuyên đề Tin học 12: Để cài đặt ngăn xếp với hai thao tác thêm vào (push) và lấy ra (pop), ta có thể dùng mảng một chiều. Khi đó, các phần tử trong mảng sẽ là các phần tử đang có trong ngăn xếp.
Ví dụ: Ngăn xếp S ở Hình 4a có thể được biểu diễn bởi một mảng một chiều mô phỏng như ở Hình 4b. Các phần tử trong mảng theo thứ tự từ đầu đến cuối sẽ tương ứng với các phần tử trong ngăn xếp theo thứ tự từ đáy lên đỉnh. Em hãy vẽ ngăn xếp S và xác định các giá trị tương ứng trong mảng mỗi khi thực hiện xong một thao tác của dãy lần lượt ba thao tác sau:
- Thêm vào ngăn xếp S một phần tử có giá trị 13.
- Thêm vào ngăn xếp S một phần tử có giá trị 15.
- Lấy ra một phần tử khỏi ngăn xếp S.
Lời giải:
Để cài đặt ngăn xếp với hai thao tác thêm vào (push) và lấy ra (pop), ta có thể dùng mảng một chiều. Khi đó, các phần tử trong mảng sẽ là các phần tử đang có trong ngăn xếp. Ngăn xếp S ở Hình 4a có thể được biểu diễn bởi một mảng một chiều mô phỏng như ở Hình 4b. Các phần tử trong mảng theo thứ tự từ đầu đến cuối sẽ tương ứng với các phần tử trong ngăn xếp theo thứ tự từ đáy lên đỉnh.
1. Thêm vào 13: Ngăn xếp SSS và mảng:
Ngăn xếp: [13,11,9,5,1] [13, 11, 9, 5, 1] [13,11,9,5,1]
Mảng:
|
Chỉ số |
0 |
1 |
2 |
3 |
4 |
|
Giá trị |
1 |
5 |
9 |
11 |
13 |
2. Thêm vào 15: Ngăn xếp SSS và mảng:
Ngăn xếp: [15,13,11,9,5,1] [15, 13, 11, 9, 5, 1] [15,13,11,9,5,1]
Mảng:
|
Chỉ số |
0 |
1 |
2 |
3 |
4 |
5 |
|
Giá trị |
1 |
5 |
9 |
11 |
13 |
15 |
3. Lấy ra 15: Ngăn xếp SSS và mảng:
Ngăn xếp: [13,11,9,5,1] [13, 11, 9, 5, 1] [13,11,9,5,1]
Mảng:
|
Chỉ số |
0 |
1 |
2 |
3 |
4 |
|
Giá trị |
1 |
5 |
9 |
11 |
13 |
Lời giải bài tập Chuyên đề Tin 12 Bài 2: Kiểu dữ liệu ngăn xếp hay, chi tiết khác: