Cho dãy A gồm 10 số nguyên lẻ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19. Bạn Thái sẽ thực hiện một cách tuỳ ý các thao tác thêm vào và lấy ra trên ngăn xếp S ban đầu đang không có phần tử nào...

a) Hướng dẫn:

Giả sử chúng ta bắt đầu với một ngăn xếp rỗng SSS và dãy số nguyên lẻ A=[1,3,5,7,9,11,13,15,17,19]A = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]A=[1,3,5,7,9,11,13,15,17,19].

Thái thực hiện hai thao tác thêm vào liên tiếp và một thao tác lấy ra:

1. Thêm vào 1:

   • Ngăn xếp SSS: 111

2. Thêm vào 3:

   • Ngăn xếp SSS: 1,31, 31,3

3. Lấy ra:

   • Lấy ra 3 từ ngăn xếp SSS: 111

Vậy, sau khi thực hiện hai thao tác thêm vào liên tiếp và một thao tác lấy ra, ngăn xếp SSS sẽ là [1][1][1].

b) Cho biết Thái cần thực hiện những thao tác thêm vào và lấy ra theo thứ tự như thế nào để có thể thu được ngăn xếp S như hình 3

Để thu được ngăn xếp SSS có các phần tử theo thứ tự từ đỉnh đến đáy là 17,11,9,5,117, 11, 9, 5, 117,11,9,5,1, ta cần chú ý rằng ngăn xếp hoạt động theo nguyên tắc LIFO (Last In, First Out). Điều này có nghĩa là chúng ta phải thêm các phần tử theo thứ tự ngược lại.

Dãy số ban đầu A=[1,3,5,7,9,11,13,15,17,19]A = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]A=[1,3,5,7,9,11,13,15,17,19].

Các thao tác cần thực hiện là:

1. Thêm vào 1: [1][1][1]

2. Thêm vào 3: [1,3][1, 3][1,3]

3. Lấy ra: [1][1][1]

4. Thêm vào 5: [1,5][1, 5][1,5]

5. Thêm vào 7: [1,5,7][1, 5, 7][1,5,7]

6. Lấy ra: [1,5][1, 5][1,5]

7. Thêm vào 9: [1,5,9][1, 5, 9][1,5,9]

8. Thêm vào 11: [1,5,9,11][1, 5, 9, 11][1,5,9,11]

9. Thêm vào 13: [1,5,9,11,13][1, 5, 9, 11, 13][1,5,9,11,13]

10. Lấy ra: [1,5,9,11][1, 5, 9, 11][1,5,9,11]

11. Thêm vào 15: [1,5,9,11,15][1, 5, 9, 11, 15][1,5,9,11,15]

12. Lấy ra: [1,5,9,11][1, 5, 9, 11][1,5,9,11]

13. Thêm vào 17: [1,5,9,11,17][1, 5, 9, 11, 17][1,5,9,11,17]

14. Thêm vào 19: [1,5,9,11,17,19][1, 5, 9, 11, 17, 19][1,5,9,11,17,19]

15. Lấy ra: [1,5,9,11,17][1, 5, 9, 11, 17][1,5,9,11,17]

Cuối cùng, ngăn xếp SSS sẽ có thứ tự là [17,11,9,5,1][17, 11, 9, 5, 1][17,11,9,5,1] từ đỉnh đến đáy.