Chuyên đề Tin 12 CTST Bài 1.2. Ngăn xếp

Quan sát Hình 1, ta thấy cách thêm đĩa mới vào và lấy ra một đĩa từ chồng đĩa như sau:

- Thêm đĩa mới vào: Đặt đĩa mới lên trên đĩa lớn nhất hiện có trên cùng của cọc.

- Lấy ra đĩa: Lấy đĩa nhỏ nhất ra từ đỉnh của bất kỳ cọc nào nhưng không làm xáo trộn thứ tự của các đĩa khác.

Hình 4 biểu diễn một ngăn xếp, ta có:

a) Phần tử ở đỉnh của ngăn xếp là dấu ngoặc đơn phải “)”. 

b) Sau khi lấy ra một phần tử (dấu ngoặc đơn phải), ngăn xếp còn lại gồm các phần tử: “2”, “+”, và “1”. 

c) Sau khi thêm phần tử “X” vào, phần tử “X” sẽ ở đỉnh của ngăn xếp.

Để biểu diễn ngăn xếp bằng mảng một chiều, em cần sử dụng những thông tin sau:

- Cần mảng một chiều để lưu trữ các phần tử của ngăn xếp.

- Kích thước của mảng 1 chiều: chính là kích thước của các phần tử trong ngăn xếp.

- Chỉ số Top: Trả về giá trị của của phần tử ở đỉnh của ngăn xếp bằng cách trả về giá trị của phần tử cuối mảng.

Có thể dùng danh sách (kiểu list của Python) để biểu diễn ngăn xếp vì: danh sách cung cấp các phương thức append(), pop() và tính năng phù hợp để thực hiện các thao tác cần thiết của một ngăn xếp một cách dễ dàng và hiệu quả.                        

Trong Python, khi sử dụng kiểu list để biểu diễn ngăn xếp.

a) Chỉ số của phần tử đỉnh.

b) Chỉ số của phần tử đáy.

Vẽ lại Hình 5, cập nhật giá trị top khi thực hiện tuần tự các thao tác sau đây: push(0), pop(), pop(), push(100).

- push(0): Thêm giá trị ‘0’ vào vị trí top hiện tại (index 8), sau đó cập nhật giá trị top thành 8.

- pop(): Loại bỏ giá trị ‘0’ khỏi vị trí top (index 8), sau đó cập nhật giá trị top thành 7.

- pop(): Loại bỏ giá trị ‘80’ khỏi vị trí top (index 7), sau đó cập nhật giá trị top thành 6.

- push(100): Thêm giá trị ‘100’ vào vị trí top hiện tại (index 6), sau đó cập nhật giá trị top thành 6.

Kết quả: Đây là cách cập nhật biểu diễn ngăn xếp sau các thao tác chỉnh sửa dữ liệu theo nguyên tắc LIFO (Last In First Out).

- Hình 5a có ‘70’ ở đỉnh ngăn xếp.

- Hình 5b sẽ có ‘100’ ở index 6 các index từ 0 đến 5 không có giá trị, index 7 và 8 trống, và index 9 không thay đổi.