Ngăn xếp DSA
ngăn xếp
Ngăn xếp là một cấu trúc dữ liệu có thể chứa nhiều phần tử.
{{ resultText }}: {{currVal }}
Hãy tưởng tượng một chồng giống như một đống bánh kếp.
Trong một đống bánh xèo, những chiếc bánh xèo vừa được thêm vào vừa được lấy ra từ trên xuống. Vì vậy, khi lấy một chiếc bánh pancake ra, nó sẽ luôn là chiếc bánh cuối cùng bạn thêm vào. Cách tổ chức các phần tử này được gọi là LIFO: Last In First Out.
Các thao tác cơ bản chúng ta có thể thực hiện trên ngăn xếp là:
- Push: Thêm phần tử mới vào ngăn xếp.
- Pop: Loại bỏ và trả về phần tử trên cùng của ngăn xếp.
- Peek: Trả về phần tử trên cùng của ngăn xếp.
- isEmpty: Kiểm tra xem ngăn xếp có trống không.
- Kích thước: Tìm số phần tử trong ngăn xếp.
Hãy thử nghiệm các thao tác cơ bản này trong hoạt ảnh ngăn xếp ở trên.
Ngăn xếp có thể được thực hiện bằng cách sử dụng mảng hoặc danh sách liên kết.
Ngăn xếp có thể được sử dụng để triển khai cơ chế hoàn tác, hoàn nguyên về trạng thái trước đó, tạo thuật toán tìm kiếm theo chiều sâu trong biểu đồ hoặc để quay lui.
Ngăn xếp thường được đề cập cùng với Hàng đợi, đây là cấu trúc dữ liệu tương tự được mô tả ở trang tiếp theo.
Triển khai ngăn xếp bằng cách sử dụng mảng
Để hiểu rõ hơn về lợi ích của việc sử dụng mảng hoặc danh sách liên kết để triển khai ngăn xếp, bạn nên xem trang này để giải thích cách lưu trữ mảng và danh sách liên kết trong bộ nhớ.
Đây là giao diện khi chúng ta sử dụng mảng làm ngăn xếp:
{{ resultText }}: {{currVal }}
Lý do nên triển khai ngăn xếp bằng mảng:
- Bộ nhớ hiệu quả: Các phần tử mảng không giữ địa chỉ các phần tử tiếp theo giống như các nút danh sách liên kết.
- Dễ triển khai và hiểu hơn: Việc sử dụng mảng để triển khai ngăn xếp yêu cầu ít mã hơn so với sử dụng danh sách liên kết và vì lý do này, việc sử dụng mảng thường dễ hiểu hơn.
Lý do không sử dụng mảng để triển khai ngăn xếp:
- Kích thước cố định: Một mảng chiếm một phần cố định của bộ nhớ. Điều này có nghĩa là nó có thể chiếm nhiều bộ nhớ hơn mức cần thiết hoặc nếu mảng đầy, nó không thể chứa nhiều phần tử hơn.
Lưu ý: Khi sử dụng mảng trong Python cho hướng dẫn này, chúng tôi thực sự đang sử dụng kiểu dữ liệu 'danh sách' Python, nhưng trong phạm vi của hướng dẫn này, kiểu dữ liệu 'danh sách' có thể được sử dụng giống như một mảng. Tìm hiểu thêm về danh sách Python tại đây .
Vì danh sách Python hỗ trợ tốt cho chức năng cần thiết để triển khai ngăn xếp nên chúng tôi bắt đầu bằng việc tạo ngăn xếp và thực hiện các thao tác ngăn xếp chỉ với một vài dòng như thế này:
Ví dụ
Trăn:
stack = []
# Push
stack.append('A')
stack.append('B')
stack.append('C')
print("Stack: ", stack)
# Pop
element = stack.pop()
print("Pop: ", element)
# Peek
topElement = stack[-1]
print("Peek: ", topElement)
# isEmpty
isEmpty = not bool(stack)
print("isEmpty: ", isEmpty)
# Size
print("Size: ",len(stack)) Chạy Ví dụ »Nhưng để tạo một cấu trúc dữ liệu cho ngăn xếp một cách rõ ràng, với các thao tác cơ bản, thay vào đó chúng ta nên tạo một lớp ngăn xếp. Cách tạo ngăn xếp này trong Python cũng giống với cách tạo ngăn xếp bằng các ngôn ngữ lập trình khác như C và Java.
Ví dụ
Trăn:
class Stack:
def __init__(self):
self.stack = []
def push(self, element):
self.stack.append(element)
def pop(self):
if self.isEmpty():
return "Stack is empty"
return self.stack.pop()
def peek(self):
if self.isEmpty():
return "Stack is empty"
return self.stack[-1]
def isEmpty(self):
return len(self.stack) == 0
def size(self):
return len(self.stack)
# Create a stack
myStack = Stack()
myStack.push('A')
myStack.push('B')
myStack.push('C')
print("Stack: ", myStack.stack)
print("Pop: ", myStack.pop())
print("Peek: ", myStack.peek())
print("isEmpty: ", myStack.isEmpty())
print("Size: ", myStack.size()) Chạy Ví dụ »Triển khai ngăn xếp bằng danh sách liên kết
Lý do sử dụng danh sách liên kết để triển khai ngăn xếp:
- Kích thước động: Ngăn xếp có thể tăng và giảm linh hoạt, không giống như mảng.
Lý do không sử dụng danh sách liên kết để triển khai ngăn xếp:
- Bộ nhớ bổ sung: Mỗi phần tử ngăn xếp phải chứa địa chỉ của phần tử tiếp theo (nút danh sách liên kết tiếp theo).
- Khả năng đọc: Mã có thể khó đọc và viết hơn đối với một số người vì nó dài hơn và phức tạp hơn.
Đây là cách có thể triển khai ngăn xếp bằng danh sách liên kết.
Ví dụ
Trăn:
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Stack:
def __init__(self):
self.head = None
self.size = 0
def push(self, value):
new_node = Node(value)
if self.head:
new_node.next = self.head
self.head = new_node
self.size += 1
def pop(self):
if self.isEmpty():
return "Stack is empty"
popped_node = self.head
self.head = self.head.next
self.size -= 1
return popped_node.value
def peek(self):
if self.isEmpty():
return "Stack is empty"
return self.head.value
def isEmpty(self):
return self.size == 0
def stackSize(self):
return self.size
myStack = Stack()
myStack.push('A')
myStack.push('B')
myStack.push('C')
print("Pop: ", myStack.pop())
print("Peek: ", myStack.peek())
print("isEmpty: ", myStack.isEmpty())
print("Size: ", myStack.stackSize()) Chạy Ví dụ »