Xin chào, bạn có thể đã đến đây để tìm kiếm Stack trong Python, chúng tôi đã sắp xếp nó cho bạn. Trong blog này, chúng tôi sẽ tiến hành phân tích chuyên sâu về CÁCH, TẠI SAO và Ở ĐÂU để sử dụng Stack trong Python.
Blog bao gồm các chủ đề sau
Stack trong cấu trúc dữ liệu là gì?
Cấu trúc dữ liệu là chìa khóa để tổ chức lưu trữ trong máy tính để chúng ta có thể truy cập và chỉnh sửa dữ liệu một cách hiệu quả. Ngăn xếp là một trong những cấu trúc dữ liệu sớm nhất được xác định trong khoa học máy tính. Nói một cách đơn giản, Stack là một tập hợp tuyến tính các mục. Nó là một tập hợp các đối tượng hỗ trợ ngữ nghĩa vào sau, ra trước [LIFO] nhanh để chèn và xóa. Nó là một cấu trúc danh sách hoặc mảng của các lệnh gọi hàm và tham số được sử dụng trong cấu trúc CPU và lập trình máy tính hiện đại. Tương tự như một chồng đĩa tại một nhà hàng, các thành phần trong một ngăn xếp được thêm hoặc xóa khỏi đầu ngăn xếp theo thứ tự "vào sau, ra trước". Không giống như danh sách hoặc mảng, không được phép truy cập ngẫu nhiên đối với các đối tượng chứa trong ngăn xếp
Có hai loại hoạt động trong Stack-
- Đẩy– Để thêm dữ liệu vào ngăn xếp
- Pop– Để xóa dữ liệu khỏi ngăn xếp
Ngăn xếp rất dễ học và dễ thực hiện, chúng được tích hợp rộng rãi trong nhiều phần mềm để thực hiện các tác vụ khác nhau. Chúng có thể được triển khai bằng Mảng hoặc Danh sách được liên kết. Chúng tôi sẽ dựa vào cấu trúc dữ liệu Danh sách ở đây
Tại sao và khi nào chúng ta sử dụng Stack?
Ngăn xếp là cấu trúc dữ liệu đơn giản cho phép chúng ta lưu trữ và truy xuất dữ liệu một cách tuần tự
Nói về hiệu suất, việc triển khai ngăn xếp phù hợp dự kiến sẽ mất thời gian O[1] cho thao tác chèn và xóa
Để hiểu Stack ở cấp độ cơ bản, hãy nghĩ về một chồng sách. Bạn thêm một cuốn sách vào đầu ngăn xếp, vì vậy cuốn đầu tiên được chọn sẽ là cuốn cuối cùng được thêm vào ngăn xếp
Có nhiều trường hợp sử dụng ngăn xếp trong thế giới thực, việc hiểu chúng cho phép chúng tôi giải quyết nhiều vấn đề về lưu trữ dữ liệu một cách dễ dàng và hiệu quả
Hãy tưởng tượng bạn là một nhà phát triển và bạn đang làm việc trên một trình xử lý văn bản hoàn toàn mới. Bạn cần tạo một tính năng hoàn tác – cho phép người dùng quay lại hành động của họ cho đến khi bắt đầu phiên. Một ngăn xếp là một sự phù hợp lý tưởng cho kịch bản này. Chúng tôi có thể ghi lại mọi hành động của người dùng bằng cách đẩy nó vào ngăn xếp. Khi người dùng muốn hoàn tác một hành động, họ có thể bật tương ứng từ ngăn xếp
Làm cách nào chúng ta có thể triển khai ngăn xếp trong Python?
Trong Python, chúng ta có thể triển khai ngăn xếp python bằng cách
- Sử dụng cấu trúc dữ liệu Danh sách tích hợp. Cấu trúc dữ liệu Danh sách tích hợp của Python đi kèm với các phương thức để mô phỏng cả hoạt động của ngăn xếp và hàng đợi
- Sử dụng thư viện deque cung cấp hiệu quả các thao tác ngăn xếp và hàng đợi trong một đối tượng.
- Sử dụng hàng đợi. Cuộc sốngLớp xếp hàng
Như đã đề cập trước đó, chúng ta có thể thêm các mục vào ngăn xếp bằng thao tác “PUSH” và xóa các mục bằng thao tác “POP”.
Hoạt động PUSH
Đẩy – thêm phần tử vào đầu ngăn xếp. Tham khảo hình ảnh bên dưới để hiểu rõ hơn
Hoạt động POP
Pop – loại bỏ một phần tử từ đỉnh ngăn xếp.
Đây là một chương trình đơn giản để minh họa Stack trong Python-
class Stack def_init_[self]: self.items=[] def is_empty[self]: return self.items==[] def push[self, data]: self.items.append[data] def pop[self]: return self.items.pop[] s= Stack[] while True: print[‘push’] print[‘pop’] print[‘quit’] do= input[‘What would you like to do?’].split[] operation= do[0].strip[].lower[] if operation== ‘push’: s.push[int[do[1]]] elif operation== ‘pop’: if s.is_empty[]: print[‘Stack is empty’] else: print[‘Popped value:’, s.pop[]] elif operation==’quit’: break
Tìm hiểu thêm về Cách sử dụng ngăn xếp trong Python và các chương trình liên quan
Ngăn xếp cung cấp nhiều cách sử dụng trong thuật toán, chẳng hạn như trong phân tích cú pháp ngôn ngữ và quản lý bộ nhớ thời gian chạy [“ngăn xếp cuộc gọi”]. Một thuật toán ngắn và hữu ích sử dụng ngăn xếp là tìm kiếm theo chiều sâu [DFS] trên cấu trúc dữ liệu dạng cây hoặc biểu đồ. Python chơi với một số cách triển khai ngăn xếp và mỗi cách có các đặc điểm hơi khác nhau. Hãy xem qua chúng
Danh sách Tích hợp sẵn
Loại danh sách tích hợp sẵn của Python tạo nên một cấu trúc dữ liệu ngăn xếp phù hợp vì nó hỗ trợ các thao tác đẩy và bật trong thời gian O[1] được phân bổ
Các danh sách của Python được triển khai dưới dạng các mảng động bên trong, điều đó có nghĩa là đôi khi chúng cần thay đổi kích thước không gian lưu trữ cho các phần tử được lưu trữ trong chúng bất cứ khi nào chúng được thêm hoặc xóa. Dung lượng bộ nhớ được phân bổ nhiều hơn yêu cầu, do đó không phải mọi thao tác đẩy hoặc bật đều yêu cầu thay đổi kích thước và bạn sẽ nhận được độ phức tạp về thời gian O[1] được phân bổ cho các thao tác này
Mặc dù điều này làm cho hiệu suất của chúng kém nhất quán hơn so với tính năng chèn và xóa O[1] ổn định do triển khai dựa trên danh sách được liên kết cung cấp. Mặt khác, danh sách cung cấp quyền truy cập ngẫu nhiên thời gian O[1] nhanh vào các phần tử trên ngăn xếp, đây có thể là một lợi ích bổ sung
Đây là cảnh báo hiệu suất quan trọng khi sử dụng danh sách làm ngăn xếp
Để có được hiệu suất O[1] phân bổ cho việc chèn và xóa, mới được thêm vào cuối danh sách bằng phương thức append[] và được xóa khỏi phần cuối bằng cách sử dụng pop[]. Ngăn xếp dựa trên danh sách Python mở rộng sang phải và thu nhỏ sang trái
Việc thêm và xóa từ phía trước mất nhiều thời gian hơn [O[n] thời gian], vì các phần tử hiện có phải được di chuyển xung quanh để có chỗ cho phần tử mới được thêm vào
# Sử dụng danh sách Python làm ngăn xếp [LIFO]
s = [] s.append['eat'] s.append['sleep'] s.append['code'] >>> s ['eat', 'sleep', 'code'] >>> s.pop[] 'code' >>> s.pop[] 'sleep' >>> s.pop[] 'eat' >>> s.pop[] IndexError: "pop from empty list"
Bộ sưu tập. deque Lớp
Lớp deque triển khai hàng đợi hai đầu hỗ trợ thêm và xóa các phần tử từ một trong hai đầu trong thời gian O[1] [không phân bổ]
Bởi vì deques hỗ trợ thêm và xóa các phần tử từ cả hai đầu tốt như nhau, nên chúng có thể phục vụ cả dưới dạng hàng đợi và dưới dạng ngăn xếp
Các đối tượng deque của Python được triển khai dưới dạng danh sách liên kết kép giúp chúng có hiệu suất chèn và xóa các phần tử phù hợp và nhất quán, nhưng hiệu suất O[n] kém khi chúng truy cập ngẫu nhiên các phần tử ở giữa ngăn xếp
bộ sưu tập. deque là một lựa chọn thuận lợi nếu bạn đang tìm cấu trúc dữ liệu ngăn xếp trong thư viện chuẩn của Python với các đặc điểm hiệu suất của việc triển khai danh sách liên kết
# Sử dụng bộ sưu tập. deque dưới dạng ngăn xếp [LIFO]
from collections import deque q = deque[] q.append['eat'] q.append['sleep'] q.append['code'] >>> q deque[['eat', 'sleep', 'code']] >>> q.pop[] 'code' >>> q.pop[] 'sleep' >>> q.pop[] 'eat' >>> q.pop[] IndexError: "pop from an empty deque"
Hàng đợi. Lớp LifoQueue
Việc triển khai ngăn xếp này trong thư viện chuẩn Python được đồng bộ hóa và cung cấp ngữ nghĩa khóa để hỗ trợ nhiều nhà sản xuất và người tiêu dùng đồng thời
Mô-đun hàng đợi chứa một số lớp khác triển khai hàng đợi nhiều nhà sản xuất, nhiều người tiêu dùng hữu ích cho tính toán song song
Tùy thuộc vào trường hợp sử dụng của bạn, ngữ nghĩa khóa có thể hữu ích hoặc chỉ phát sinh chi phí không cần thiết. Trong trường hợp này, bạn nên sử dụng danh sách hoặc deque làm ngăn xếp cho mục đích chung sẽ tốt hơn
# Sử dụng hàng đợi. LifoQueue dưới dạng ngăn xếp
from queue import LifoQueue s = LifoQueue[] s.put['eat'] s.put['sleep'] s.put['code'] >>> s >>> s.get[] 'code' >>> s.get[] 'sleep' >>> s.get[] 'eat' >>> s.get_nowait[] queue.Empty >>> s.get[] # Blocks / waits forever...
Nếu bạn đã tiếp tục đến đây, thì bây giờ bạn đã có thể sử dụng ngăn xếp trong Python, tôi hy vọng blog này đã giúp bạn tìm hiểu các phương pháp triển khai khác nhau của ngăn xếp trong Python.
Vì vậy, điều này kết thúc bài viết "ngăn xếp trong python" của chúng tôi. Tôi hy vọng bạn thích đọc blog này và thấy nó có nhiều thông tin. Đến bây giờ, bạn hẳn đã hiểu rõ về ngăn xếp python là gì và nó được sử dụng như thế nào. Bây giờ hãy tiếp tục và thực hành tất cả các ví dụ
Để có kiến thức chuyên sâu về ngôn ngữ Lập trình Python cùng với các ứng dụng khác nhau của ngôn ngữ này, bạn có thể đăng ký ngay để tham gia khóa đào tạo Python trực tiếp với sự hỗ trợ 24/7 và quyền truy cập trọn đời
Có một câu hỏi cho chúng tôi?