Ngăn xếp (stack) là một cấu trúc dữ liệu quan trọng trong tổ chức máy tính, hoạt động theo nguyên tắc “vào sau ra trước” (LIFO – Last-In, First-Out). Bài viết này sẽ giải thích chi tiết về ngăn xếp thanh ghi (register stack) và ngăn xếp bộ nhớ (memory stack) với các sơ đồ minh họa rõ ràng, giúp bạn hiểu rõ hơn về cách chúng hoạt động và vai trò của chúng trong hệ thống máy tính.
Một phần bộ nhớ được phân bổ cho hoạt động của ngăn xếp trong CPU. Thanh ghi của bộ xử lý được sử dụng làm Con trỏ Ngăn xếp (Stack Pointer – SP). Hình trên minh họa phần bộ nhớ máy tính được chia thành ba phân đoạn: Hướng dẫn Chương trình, Dữ liệu và Ngăn xếp.
- Bộ đếm Chương trình (Program Counter – PC): Là một thanh ghi trỏ đến địa chỉ của lệnh tiếp theo sẽ được thực thi trong chương trình.
- Thanh ghi Địa chỉ (Address Register – AR): Thanh ghi này trỏ đến tập hợp dữ liệu và được sử dụng trong giai đoạn thực thi để đọc toán hạng.
- Con trỏ Ngăn xếp (Stack Pointer – SP): Trỏ đến đỉnh của ngăn xếp và được sử dụng để đẩy (push) hoặc lấy (pop) các mục dữ liệu vào hoặc ra khỏi ngăn xếp.
Ba thanh ghi này được kết nối với một bus địa chỉ chung và bất kỳ thanh ghi nào trong số chúng đều có thể cung cấp địa chỉ cho bộ nhớ.
Con trỏ Ngăn xếp ban đầu sẽ trỏ đến địa chỉ 3001, và sau đó ngăn xếp sẽ phát triển theo chiều giảm dần của địa chỉ. Điều này có nghĩa là mục đầu tiên sẽ được lưu trữ tại địa chỉ 3001, mục thứ hai tại địa chỉ 3000, và các mục có thể tiếp tục được lưu trữ trong ngăn xếp cho đến khi nó đạt đến địa chỉ cuối cùng là 2000, nơi mục cuối cùng sẽ được lưu giữ.
Dữ liệu được chèn vào Ngăn xếp được lấy từ Thanh ghi Dữ liệu và dữ liệu được lấy ra từ Ngăn xếp cũng được đọc bởi Thanh ghi Dữ liệu.
Hoạt động Đẩy (PUSH) và Lấy (POP)
PUSH
Hoạt động này được sử dụng để chèn một mục dữ liệu mới vào đỉnh của Ngăn xếp. Mục mới có thể được chèn như sau:
SP ← SP – 1
M[SP] ← DR
Trong bước đầu tiên, Con trỏ Ngăn xếp được giảm để trỏ đến địa chỉ nơi mục dữ liệu sẽ được lưu trữ.
Sau đó, bằng cách sử dụng thao tác ghi bộ nhớ, mục dữ liệu từ Thanh ghi Dữ liệu được chèn vào đỉnh của ngăn xếp (tại địa chỉ mà Con trỏ Ngăn xếp đang trỏ).
POP
Hoạt động này được sử dụng để xóa một mục dữ liệu khỏi đỉnh của Ngăn xếp. Mục dữ liệu có thể được xóa như sau:
DR ← M[SP]
SP ← SP + 1
Trong bước đầu tiên, mục dữ liệu trên cùng được đọc từ Ngăn xếp vào Thanh ghi Dữ liệu. Sau đó, Con trỏ Ngăn xếp được tăng để trỏ đến mục dữ liệu tiếp theo trong ngăn xếp. Hoạt động Đẩy hoặc Lấy có thể được thực hiện với sự trợ giúp của các vi thao tác sau:
- Truy cập bộ nhớ với sự trợ giúp của Con trỏ Ngăn xếp (SP), và
- Cập nhật ngăn xếp.
Việc Con trỏ Ngăn xếp (SP) được cập nhật bằng cách tăng hoặc giảm giá trị địa chỉ hoàn toàn phụ thuộc vào cách tổ chức của ngăn xếp. Trong trường hợp này, Con trỏ Ngăn xếp phát triển bằng cách giảm địa chỉ bộ nhớ. Ngăn xếp cũng có thể được tạo theo cách mà Con trỏ Ngăn xếp phát triển bằng cách tăng địa chỉ bộ nhớ.
Vì địa chỉ luôn có sẵn và được tự động cập nhật trong Con trỏ Ngăn xếp, CPU có thể tham chiếu đến Ngăn xếp Bộ nhớ mà không cần phải chỉ định địa chỉ. Ngăn xếp thanh ghi hoạt động tương tự, nhưng sử dụng các thanh ghi bên trong CPU thay vì bộ nhớ chính, cho phép truy cập nhanh hơn.
