Cấu trúc Dữ liệu Stack trong Python
Stack là một cấu trúc dữ liệu quan trọng trong lập trình, tuân theo nguyên tắc LIFO (Last In, First Out), nghĩa là các phần tử được thêm vào cuối cùng sẽ được lấy ra đầu tiên. Để hình dung, hãy xem chồng sách: nếu bạn muốn lấy cuốn sách nằm ở dưới cùng, bạn phải lấy hết các cuốn sách ở trên ra trước.
Các Thao Tác Cơ Bản Trên Stack
- Push: Thêm một phần tử vào đỉnh (top) của stack.
- Pop: Xóa và lấy ra phần tử ở đỉnh stack.
- Peek: Trả về phần tử ở đỉnh mà không xóa nó.
- isEmpty: Kiểm tra xem stack có rỗng hay không.
- isFull: Kiểm tra xem stack có đầy hay không (trong trường hợp stack có giới hạn kích thước).
Cài đặt Stack trong Python
Chúng ta sẽ tạo một lớp Stack với các chức năng cơ bản:
python
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
return "Stack is empty, cannot pop."
def peek(self):
if not self.is_empty():
return self.stack[-1]
return "Stack is empty, no top element to peek."
def is_empty(self):
return len(self.stack) == 0
def size(self):
return len(self.stack)
def __str__(self):
return str(self.stack)Sử dụng lớp Stack
python
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack) # Output: [10, 20, 30]
print(stack.pop()) # Output: 30Kiểm Tra Cân Bằng Dấu Ngoặc
Một ứng dụng thú vị của stack là kiểm tra tính cân bằng của dấu ngoặc trong chuỗi. Với các ký tự (), {}, [], hàm sẽ kiểm tra xem chuỗi có hợp lệ hay không. Ví dụ:
python
def is_paren_balanced(paren_string):
s = Stack()
for paren in paren_string:
if paren in "([{":
s.push(paren)
else:
if s.is_empty() or not is_match(s.pop(), paren):
return False
return s.is_empty()Đảo Ngược Chuỗi Với Stack
Stack cũng có thể được sử dụng để đảo ngược một chuỗi. Bằng cách đẩy tất cả các ký tự vào stack và sau đó pop ra theo thứ tự ngược, chúng ta có thể nhận được chuỗi đã được đảo ngược:
python
def reverse_string(stack, input_str):
for char in input_str:
stack.push(char)
rev_str = ""
while not stack.is_empty():
rev_str += stack.pop()
return rev_strChuyển Đổi Số Nguyên Thành Nhị Phân
Cuối cùng, stack còn có thể thực hiện chuyển đổi số nguyên sang dạng nhị phân:
python
def convert_int_to_bin(dec_num):
s = Stack()
while dec_num > 0:
s.push(dec_num % 2)
dec_num //= 2
bin_num = ""
while not s.is_empty():
bin_num += str(s.pop())
return bin_numKết Luận
Bài viết này trình bày khái niệm, các thao tác cơ bản và một số ứng dụng thực tiễn của stack trong Python. Việc hiểu cấu trúc dữ liệu này sẽ giúp bạn phát triển kỹ năng lập trình hiệu quả hơn. Hãy áp dụng cách thức này để giải quyết các bài toán khác nhau trong lập trình!
source: viblo
