Ngăn xếp không là gì ngoài cấu trúc dữ liệu tuyến tính, nơi việc chèn và xóa chỉ diễn ra ở một đầu. Thao tác chèn có tên đặc biệt là PUSH và thao tác xóa cũng có tên đặc biệt là POP. PUSH và POP là hai hoạt động cơ bản chỉ có thể được thực hiện trong một ngăn xếp cụ thể. Nó là một nhóm các vị trí bộ nhớ và các vị trí bộ nhớ liên quan đến bộ nhớ đọc hoặc bộ nhớ ghi. Điều này được sử dụng để lưu trữ thông tin nhị phân trong quá trình thực thi chương trình, khi chúng ta đang thực hiện bất kỳ chương trình nào thì nội dung của chương trình đó sẽ được lưu trữ trong ngăn xếp. Nó theo sau Lần xuất trước (LIFO) và nó chỉ được sử dụng để lưu trữ và truy xuất dữ liệu nhưng không được sử dụng để lưu trữ dữ liệu. Giải thích ngắn gọn về con trỏ ngăn xếp / ngăn xếp được thảo luận dưới đây.
Stack / Stack Pointer là gì?
Định nghĩa: Ngăn xếp là một thiết bị lưu trữ, được sử dụng để lưu trữ thông tin hoặc dữ liệu theo cách thức LIFO (Last In First Out). Bất cứ khi nào chúng ta nhập dữ liệu ở dạng LIFO, phần tử phải xóa đầu tiên là phần tử chèn cuối cùng, vì vậy phần tử được chèn cuối cùng sẽ được lấy ra trước. Nó là đơn vị bộ nhớ trong một thanh ghi địa chỉ được gọi là con trỏ ngăn xếp (SP). Con trỏ ngăn xếp luôn chỉ ra phần tử trên cùng trong ngăn xếp có nghĩa là dữ liệu phải được chèn vào vị trí nào.
Các loại ngăn xếp
Có hai loại ngăn xếp là ngăn xếp thanh ghi và ngăn xếp bộ nhớ.
Đăng ký ngăn xếp
Ngăn xếp thanh ghi cũng là một vùng nhớ có trong đơn vị bộ nhớ, nhưng nó chỉ xử lý một lượng nhỏ dữ liệu. Độ sâu ngăn xếp luôn bị giới hạn trong ngăn xếp thanh ghi vì kích thước của ngăn xếp thanh ghi rất nhỏ so với bộ nhớ.
Đẩy hoạt động trong ngăn xếp đăng ký
Bước 1: Con trỏ ngăn xếp tăng lên 1.
SP ← SP + 1
Bước 2: Nhập dữ liệu vào ngăn xếp.
1000 [SP] ← CT
Trong đó DR là Đăng ký Dữ liệu
Bước 3: Kiểm tra xem ngăn xếp đã đầy hay chưa
if (sp = 0) then (full ← 1)
Bước 4: Đánh dấu không trống
trống ← 0
Thao tác Pop trong Ngăn xếp Đăng ký
Bước 1: Đọc dữ liệu từ ngăn xếp.
DR ← M [SP]
Bước 2: Điểm ngăn xếp giảm dần.
SP ← SP-1
Bước 3: Kiểm tra xem ngăn xếp có trống hay không
nếu sp = 0 thì trống ← 1
Tổ chức ngăn xếp của ngăn xếp thanh ghi 64 bit được thể hiện trong hình dưới đây.
Đăng ký tổ chức ngăn xếp
Ngăn xếp bộ nhớ
Trong ngăn xếp bộ nhớ, độ sâu ngăn xếp linh hoạt. Nó chiếm một lượng lớn dữ liệu bộ nhớ, trong khi trong ngăn xếp thanh ghi chỉ có một số lượng từ bộ nhớ hữu hạn sẽ được lưu trữ.
Thao tác đẩy trong ngăn xếp bộ nhớ
Bước 1: SP ← SP-1
Bước 2: 1000 [SP] ← CT
Thao tác bật trong Ngăn xếp bộ nhớ
Bước 1: DR ← M [SP]
Bước 2: SP ← SP-1
So sánh với đơn vị thanh ghi, đơn vị bộ nhớ lưu trữ một lượng lớn dữ liệu. Hình ngăn xếp bộ nhớ được hiển thị trong hình dưới đây.
Ngăn xếp bộ nhớ
Tổng đơn vị bộ nhớ được chia thành ba phần, đơn vị bộ nhớ đầu tiên có chương trình (không có gì ngoài lệnh), phần thứ hai là dữ liệu (toán hạng) và phần thứ ba là ngăn xếp. Các lệnh chương trình luôn lưu trữ trong bộ đếm chương trình (PC), các thanh ghi dữ liệu được xác định bởi thanh ghi địa chỉ (AR). Địa chỉ 3000 đến 4001 được sử dụng cho ngăn xếp và mục hoặc phần tử đầu tiên được lưu trữ ở 4001.
Stack / Stack Pointer trong Bộ vi xử lý 8085
Chế độ xem lập trình viên của 8085 bộ vi xử lý chứa các thanh ghi mục đích chung và sổ đăng ký mục đích đặc biệt . Các thanh ghi cho mục đích chung là A, B, C, D, E, H, L, và các thanh ghi cho mục đích đặc biệt là SP (Stack Pointer) và PC (Program Counter). Chế độ xem lập trình viên của bộ vi xử lý 8085 được hiển thị trong hình dưới đây.
Chế độ xem lập trình của 8085
Con trỏ ngăn xếp là một thanh ghi 16-bit chứa địa chỉ bộ nhớ, giả sử nội dung của con trỏ ngăn xếp (SP) là FC78H, thì bộ vi xử lý 8085 sẽ thông dịch nó. Vị trí bộ nhớ có thông tin hữu ích từ FC78H đến FFFH và từ FC77H đến 0000H vị trí bộ nhớ không có thông tin hữu ích. Cách diễn giải của con trỏ ngăn xếp được hiển thị trong hình bên dưới.
Giải thích về con trỏ ngăn xếp
Các hoạt động cơ bản của Stack / Stack Pointer
Có hai hoạt động của ngăn xếp đó là: hoạt động PUSH và hoạt động POP.
Hoạt động PUSH
PUSH có nghĩa là đẩy hoặc chèn một phần tử vào ngăn xếp. Thao tác PUSH luôn làm tăng con trỏ ngăn xếp và thao tác POP luôn giảm con trỏ ngăn xếp. Trong trường hợp hoạt động đẩy, chúng ta phải kiểm tra xem có dung lượng trống còn trống hay không. Nếu dung lượng trống còn trống, chúng ta có thể vào thao tác đẩy, nếu không còn dung lượng trống thì xảy ra thông báo lỗi là tràn. Sự tràn phải được kiểm tra trong trường hợp hoạt động đẩy tương ứng. Hoạt động cơ bản của push và pop được thể hiện trong hình bên dưới.
Hoạt động cơ bản của PUSH và POP
Hình (a) là ngăn xếp. Nếu bạn muốn đẩy phần tử đang chèn phần tử vào ngăn xếp, bạn phải đẩy (s, a), trong đó ‘s’ không là gì ngoài một ngăn xếp. Trong ngăn xếp, chúng tôi đang đặt phần tử ‘a’ và hoạt động này được thể hiện trong hình (b). Xem hình (3), giả sử ngăn xếp chứa ba phần tử a, b, c và ngăn xếp được lấp đầy bởi một phần tử.
Nếu bạn muốn chèn phần tử thứ tư-‘d ’bằng cách sử dụng push (s, d), nhưng không còn chỗ trống để chèn phần tử thì điều đó cho thấy ngăn xếp bị tràn. Thuật ngữ tràn được sử dụng khi ngăn xếp đầy và thuật toán hoạt động đẩy được hiển thị bên dưới.
push (stack [], top, max stack, item)
if (top == maxstack-1)
{
in 'tràn'
}
khác
{
top = top + 1
stack [top] = item
}
kết thúc
Hoạt động POP
POP có nghĩa là xóa phần tử ở trên cùng của ngăn xếp. Trong trường hợp hoạt động pop, chúng ta phải kiểm tra xem ban đầu ngăn xếp có trống hay không. Nếu ban đầu ngăn xếp trống thì sẽ xảy ra tình trạng tràn. Giả sử ngăn xếp vẫn trống, bạn muốn bật các phần tử trong ngăn xếp nhưng không có phần tử nào trong ngăn xếp thì nó dẫn đến dòng chảy dưới ngăn xếp.
Quy trình dưới đây sẽ được kiểm tra trong trường hợp hoạt động pop tương ứng. Trong thao tác bật, bất kỳ phần tử trên cùng nào hiện diện trong ngăn xếp sẽ được bật hoặc xóa, vì vậy không cần đề cập đến phần tử nào sẽ được bật lên, theo mặc định, phần tử trên cùng sẽ được bật lên. Thuật toán của hoạt động pop được hiển thị bên dưới.
pop (ngăn xếp [], trên cùng, mục)
if (top == - 1)
{
in 'dòng dưới'
}
khác
{
item = stack [top]
top = top-1
}
Thí dụ
Các phần tử được chèn theo thứ tự là A, B, C, D, E, nó đại diện cho chồng năm phần tử. Trong hình (a), chúng ta muốn đẩy phần tử 'A' lên ngăn xếp thì đỉnh trở thành 0 (top = 0), tương tự đỉnh = 1 khi phần tử 'B' được đẩy, top = 2 khi phần tử 'C' được đẩy, top = 3 khi phần tử 'D' được đẩy và top = 4 khi phần tử 'E' được đẩy.
Vì vậy, bất kỳ phần tử nào tôi đã lấy được đặt trong ngăn xếp, bây giờ ngăn xếp đã đầy. Nếu bạn muốn đẩy một phần tử khác thì không có chỗ trong ngăn xếp, vì vậy nó chỉ ra sự tràn. Bây giờ ngăn xếp đã đầy nếu bạn muốn bật phần tử ‘E’ phần tử phải được xóa trước. Hoạt động đẩy được hiển thị trong hình dưới đây.
Hoạt động đẩy
Chúng ta phải sử dụng thao tác pop để xóa các phần tử trong ngăn xếp. Vì vậy, chỉ cần đề cập đến pop (), không viết các đối số trong cửa sổ bật lên vì theo mặc định, nó sẽ xóa phần tử trên cùng. Phần tử ‘E’ đầu tiên bị xóa phần tử ‘D’ tiếp theo… .. ’A’. Khi các phần tử hàng đầu đang xóa thì giá trị hàng đầu sẽ giảm. Khi top = -1 ngăn xếp chỉ ra dòng dưới. Hoạt động pop được hiển thị trong hình dưới đây.
Hoạt động POP
Vì vậy, đây là lời giải thích về cách các phần tử được chèn và xóa trong ngăn xếp bằng cách sử dụng thao tác đẩy và bật.
Các ứng dụng
Các ứng dụng của con trỏ ngăn xếp / ngăn xếp là
- Đảo ngược chuỗi
- Dấu ngoặc cân đối
- UNDO / FINGER
- Ngăn xếp hệ thống cho hồ sơ kích hoạt
- Infix, prefix, postfix, expression
Câu hỏi thường gặp
1). Con trỏ ngăn xếp trong cánh tay là gì?
Thanh ghi con trỏ ngăn xếp (R13) được sử dụng như một con trỏ tới ngăn xếp hoạt động trong ARM.
2). Tại sao con trỏ ngăn xếp là 16 bit?
Con trỏ ngăn xếp (SP) và bộ đếm chương trình (PC) được sử dụng để lưu trữ vị trí trước đó và địa chỉ vị trí bộ nhớ là 16 bit, vì vậy con trỏ ngăn xếp (SP) cũng là 16 bit.
3). Vai trò của con trỏ ngăn xếp là gì?
Vai trò của con trỏ ngăn xếp (SP) là chỉ ra đỉnh của phần tử trong ngăn xếp.
4). Ngăn xếp nào được sử dụng trong 8085?
Ngăn xếp được sử dụng trong 8085 là Last In First Out (LIFO).
5). Con trỏ ngăn xếp có phải là thanh ghi không?
Đúng vậy, con trỏ ngăn xếp (SP) là một thanh ghi địa chỉ luôn chỉ ra đỉnh của phần tử trong ngăn xếp.
