6.1 Định nghĩa và thuộc tính của stack
Stack là một cấu trúc dữ liệu trừu tượng hoạt động theo nguyên tắc "vào sau ra trước" (Last In, First Out, LIFO). Nó giống như một chồng sách: cuốn sách vừa được thêm vào nằm ở trên cùng và sẽ được lấy ra đầu tiên.
Thuộc tính của stack:
- LIFO (Last In, First Out): Phần tử vừa được thêm vào sẽ được lấy ra đầu tiên.
- Hạn chế thao tác: Stack chỉ hỗ trợ thêm (push), xoá (pop) và xem (peek) phần tử trên đỉnh.
- Truy cập đơn hướng: Chỉ có thể truy cập phần tử ở đỉnh stack.
- Dễ dàng triển khai: Stack có thể dễ dàng triển khai bằng mảng hoặc danh sách liên kết.
- Quản lý bộ nhớ: Dữ liệu tạm thời hoặc trạng thái có thể được lưu trữ và truy xuất ngược lại thứ tự đã thêm.
Nguyên tắc hoạt động của LIFO:
- Thêm phần tử (push): Một phần tử mới được thêm vào đỉnh stack.
- Xoá phần tử (pop): Phần tử vừa được thêm sẽ bị xoá từ đỉnh stack.
- Xem đỉnh (peek): Cho phép xem phần tử trên đỉnh stack mà không xoá nó.
Các phần tử của stack được thêm và xoá từ cùng một phía, gọi là đỉnh (top). Vì vậy, phần tử vừa được thêm luôn ở trên đỉnh và sẽ bị xoá đầu tiên.
6.2 Các thao tác chính
Các thao tác chính: push, pop, peek
Thao tác push: Thêm phần tử mới vào đỉnh stack.
Độ phức tạp thời gian: O(1).
Ví dụ mô phỏng stack trong Python dùng class list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
print(stack) # Output: [10, 20]
Thao tác pop: Xoá và trả về phần tử trên đỉnh stack.
Độ phức tạp thời gian: O(1).
Ví dụ mô phỏng stack trong Python dùng class list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
top_element = stack.pop() # pop
print(top_element) # Output: 20
print(stack) # Output: [10]
Thao tác peek: Trả về phần tử trên đỉnh stack mà không xoá nó.
Độ phức tạp thời gian: O(1).
Ví dụ triển khai:
stack = []
stack.append(10) # push 10
top_element = stack[-1] # peek
print(top_element) # Output: 10
6.3 Ví dụ sử dụng stack
Cùng xem vài ví dụ về việc sử dụng stack:
Quản lý gọi hàm
Trong Python, stack được sử dụng để theo dõi các hàm trong quá trình thực thi chương trình. Mỗi lần một hàm được gọi, địa chỉ quay lại và các biến cục bộ của nó được đặt vào stack. Khi hàm kết thúc thực thi, điều khiển quay lại hàm đã gọi nó và dữ liệu được lấy ra khỏi stack.
Ví dụ sử dụng stack trong gọi hàm:
Trong ví dụ này, các lời gọi hàm đệ quy factorial sử dụng stack gọi để lưu trữ trạng thái của từng lời gọi cho đến khi điều kiện cơ sở (n == 1) được đáp ứng.
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # Output: 120
Hoàn tác tác vụ (Undo)
Stack được sử dụng để thực hiện chức năng hoàn tác hành động trong các trình soạn thảo văn bản và các ứng dụng khác. Khi người dùng thực hiện một hành động, nó được lưu vào stack. Khi thực hiện thao tác Undo, hành động cuối cùng sẽ được lấy ra và hoàn tác từ stack.
Ví dụ sử dụng stack cho hoàn tác tác vụ:
class TextEditor:
def __init__(self):
self.text = ""
self.history = []
def type(self, text):
self.history.append(self.text)
self.text += text
def undo(self):
if self.history:
self.text = self.history.pop()
# Ví dụ sử dụng:
editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text) # Output: "Hello World"
editor.undo()
print(editor.text) # Output: "Hello"
editor.undo()
print(editor.text) # Output: ""
GO TO FULL VERSION