Hướng dẫn cấu trúc dữ liệu ngăn xếp Python

Triển khai ngăn xếp LIFO trong Python. Chạy ví dụ về mã ngăn xếp tương tác của chúng tôi để làm chủ các giới hạn đẩy, bật, nhìn trộm và dung lượng.

Thử trong Trình chỉnh sửa

Tổng quan

Ngăn xếp là một cấu trúc dữ liệu tuyến tính tuân theo nguyên tắc Vào sau, ra trước (LIFO). Điều này có nghĩa là phần tử cuối cùng được thêm vào ngăn xếp sẽ là phần tử đầu tiên bị xóa, tương tự như một chồng đĩa.

Ngăn xếp hỗ trợ hai thao tác chính: đẩy (thêm một mục vào đầu) và bật (xóa mục được thêm gần đây nhất). Ngoài ra, thao tác nhìn trộm hoặc trên cùng cho phép kiểm tra phần tử trên cùng mà không cần xóa nó.

Trong Python, có thể dễ dàng xây dựng các ngăn xếp bằng cách sử dụng danh sách có các phương thức `.append()` và `.pop()` hoặc bằng cách sử dụng đối tượng `collections.deque` cung cấp các hoạt động hàng đợi hai đầu được tối ưu hóa trong thời gian O(1).

Đầu ra mã & thực thi

Triển khai Ngăn xếp tùy chỉnh bằng cách sử dụng cấu trúc danh sách của Python để mô phỏng các hàm đẩy, bật và xem nhanh.

class Stack:
    def __init__(self):
        self.items = []
        
    def is_empty(self):
        return len(self.items) == 0
        
    def push(self, item):
        self.items.append(item)
        print(f"Pushed: {item}")
        
    def pop(self):
        if self.is_empty():
            return "Underflow: Stack is empty"
        popped = self.items.pop()
        print(f"Popped: {popped}")
        return popped
        
    def peek(self):
        if self.is_empty():
            return "Stack is empty"
        return self.items[-1]
        
    def size(self):
        return len(self.items)

# Initialize stack
stack = Stack()
stack.push("Apples")
stack.push("Bananas")
stack.push("Cherries")

print(f"Current Stack Size: {stack.size()}")
print(f"Top Element (Peek): {stack.peek()}")

stack.pop()
print(f"Stack after Pop: {stack.items}")
Đầu ra thiết bị đầu cuối
Pushed: Apples
Pushed: Bananas
Pushed: Cherries
Current Stack Size: 3
Top Element (Peek): Cherries
Popped: Cherries
Stack after Pop: ['Apples', 'Bananas']

Triển khai từng bước

  • Quản lý chức năng undo trong hệ thống phần mềm
  • Phân tích cú pháp và kiểm tra dấu ngoặc đơn trong trình biên dịch
  • Theo dõi ngăn xếp cuộc gọi thực thi trong quá trình đệ quy trong động cơ

Câu hỏi thường gặp

Tại sao bộ sưu tập.deque được ưu tiên hơn danh sách thông thường cho Ngăn xếp?

Mặc dù danh sách rất tiện lợi nhưng chúng lại là các mảng động. Khi họ thay đổi kích thước, việc phân bổ lại bộ nhớ có thể mất O(n) thời gian. Đối tượng deque sử dụng kiến ​​trúc danh sách liên kết đôi, đảm bảo O(1) đẩy và bật.

Ngăn xếp có thể tràn trong Python không?

Một lớp ngăn xếp tiêu chuẩn trong Python sử dụng mảng danh sách sẽ phát triển cho đến khi nó tiêu thụ hết bộ nhớ hệ thống có sẵn. Tuy nhiên, ngăn xếp đệ quy trong Python có giới hạn mặc định (thường là 1000) để ngăn các vòng lặp vô hạn làm hỏng trình thông dịch.

Chủ đề liên quan