Ngăn xếp

Trong khoa học máy tính, một ngăn xếp (còn gọi là bộ xếp chồng, tiếng Anh: stack) là một cấu trúc dữ liệu trừu tượng hoạt động theo nguyên lý "vào sau ra trước" (Last In First Out (LIFO).

Lược đồ một ngăn xếp

Ngăn xếp còn được triển khai với mô hình vô cùng nổi tiếng đó chính là danh sách liên kết đơn.

Thuật ngữ

Thông thường, các thuật ngữ được sử dụng trong một mô hình ngăn xếp như sau:

• Stack: Một ngăn xếp.
• Push: Thêm một dữ liệu vào ngăn xếp.
• Pop: Bỏ ra một dữ liệu khỏi ngăn xếp, không xóa hoàn toàn.

Kiểu dữ liệu trừu tượng ngăn xếp

Một ngăn xếp là một cấu trúc dữ liệu dạng thùng chứa (container) của các phần tử (thường gọi là các nút (node)) và có hai phép toán cơ bản: push and pop. Push bổ sung một phần tử vào đỉnh (top) của ngăn xếp, nghĩa là sau các phần tử đã có trong ngăn xếp. Pop giải phóng và trả về phần tử đang đứng ở đỉnh của ngăn xếp.

Trong stack, các đối tượng có thể được thêm vào stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi stack.

Ngoài ra, stack cũng hỗ trợ một số thao tác khác như:

• isEmpty(): Kiểm tra xem stack có rỗng không.
• Top(): Trả về giá trị của phần tử nằm ở đầu stack mà không hủy nó khỏi stack. Nếu stack rỗng thì lỗi sẽ xảy ra.

Các phép toán

Trong ngôn ngữ máy tính hiện nay, một ngăn xếp thường được dùng với các phép toán "push" và "pop". Độ dài (số phần tử) của ngăn xếp cũng là một tham số cần thiết của nó. Đôi khi cần tới một phép toán chỉ cần lấy giá trị của phần từ trên đỉnh ngăn xếp mà không xóa nó khỏi ngăn xếp (peak).

Sau đây là đoạn mã giả để bổ sung, loại bỏ, tính độ dài, và lấy giá trị phần tử ở đỉnh của ngăn xếp.

record Node {
  data // Dữ liệu được lưu trữ trong một nút
  next // Tham chiếu đến nút tiếp theo, ở nút cuối cùng nó là null (rỗng).
}

record Stack {
  Node stackPointer  // trỏ đến nút đầu tiên, trả về giá trị null khi ngăn xếp rỗng.
}

function push(Stack stack, Node newNode) { // thêm dữ liệu vào ngăn xếp
  newNode.next:= Stack.stackPointer
  stack.stackPointer:= newNode
}

function pop(Stack stack) { // increase the stack pointer and return 'top' node
  // You could check if stack.stackPointer is null here.
  // If so, you may wish to error, citing the stack underflow.
  node:= stack.stackPointer
  stack.stackPointer:= stack.stackPointer.next
  return node
}

function peak(Stack stack) { // return 'top' node
  return stack.stackPointer
}

function length(Stack stack) { // return the amount of nodes in the stack
  length:= 0
  node:= stack.stackPointer
  while node not null {
    length:= length + 1
    node:= node.next
  }
  return length
}

Ứng dụng

Ngăn xếp có nhiều ứng dụng trong khoa học máy tính.

Tính các biểu thức đại số

Ví dụ: Tính biểu thức

((1 + 2) * 4) + 3

Trước hết viết biểu thức theo hậu thứ tự:

1 2 + 4 * 3 +

Khi tính một biểu thức ta dùng một ngăn xếp để cất dữ liệu trung gian như sau: Đọc từ trái sang phải mỗi lần một phần tử:

• nếu gặp một toán hạng (biến hoặc hằng), đặt (push) toán hạng đó vào ngăn xếp;
• nếu gặp một toán tử, lấy (pop) hai phần tử trên đỉnh ngăn xếp ra, thực hiện phép toán và đặt (push) lại kết quả vào ngăn xếp.

Input	Phép toán	Ngăn xếp
1	Push(1)	1
2	Push(2)	1, 2
+	Pop(2), Pop(1), 1+2=3; Push(3)	3
4	Push(4)	3, 4
*	Pop(4), Pop(3), 3*4=12; Push(12)	12
3	Push(3)	12, 3
+	Pop(3), Pop(12), 12+3=15; Push(15)	15

Kết quả 15 đặt ở đỉnh của ngăn xếp khi tính xong.

Xem thêm

• Hàng đợi
• Ký pháp Ba Lan

Tham khảo

• Donald Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.1: Stacks and queues, pp. 200–204.

Liên kết ngoài

• Stack program in c++ Lưu trữ 2012-07-15 tại Wayback Machine
• StackAnalyzer
• Stack Machines - the new wave
• Bounding stack depth
• Libsafe - Protecting Critical Elements of Stacks Lưu trữ 2006-02-06 tại Wayback Machine
• Stack Checker Tool Lưu trữ 2006-10-09 tại Wayback Machine
• Stack Size Analysis for Interrupt-driven Programs (322 KB)
• Stack Implementation (Graphical & Text Mode) C Language implementation of Stack
• Pointers to stack visualizations Lưu trữ 2007-01-28 tại Wayback Machine