Bạn đã nghe nói về ngăn xếp và tự hỏi chúng là gì?
Trong hướng dẫn này, bạn sẽ học
- Cách nhận biết khi nào ngăn xếp là lựa chọn tốt cho cấu trúc dữ liệu
- Cách quyết định triển khai nào là tốt nhất cho chương trình của bạn
- Những cân nhắc bổ sung cần thực hiện về ngăn xếp trong môi trường luồng hoặc đa xử lý
Hướng dẫn này dành cho các Pythonistas, những người cảm thấy thoải mái khi chạy tập lệnh, biết list là gì và cách sử dụng nó cũng như đang tự hỏi cách triển khai ngăn xếp Python
Tiền thưởng miễn phí. Nhấp vào đây để nhận Bảng cheat Python và tìm hiểu kiến thức cơ bản về Python 3, như làm việc với các kiểu dữ liệu, từ điển, danh sách và hàm Python
Ngăn xếp là gì?
A là cấu trúc dữ liệu lưu trữ các mục theo cách Nhập sau/Xuất trước. Điều này thường được gọi là LIFO. Điều này trái ngược với , lưu trữ các mục theo cách Nhập trước/Xuất trước (FIFO)
Có lẽ dễ hiểu nhất về ngăn xếp nếu bạn nghĩ về trường hợp sử dụng mà bạn có thể quen thuộc. tính năng Hoàn tác trong trình chỉnh sửa của bạn
Hãy tưởng tượng bạn đang chỉnh sửa tệp Python để chúng tôi có thể xem xét một số thao tác bạn thực hiện. Đầu tiên, bạn thêm một chức năng mới. Điều này thêm một mục mới vào ngăn xếp hoàn tác
Bạn có thể thấy rằng ngăn xếp hiện có thao tác Thêm chức năng trên đó. Sau khi thêm chức năng, bạn xóa một từ trong một bình luận. Điều này cũng được thêm vào ngăn xếp hoàn tác
Lưu ý cách mục Xóa từ được đặt trên đầu ngăn xếp. Cuối cùng, bạn thụt lề một bình luận để nó được xếp hàng đúng cách
Bạn có thể thấy rằng mỗi lệnh này được lưu trữ trong một ngăn xếp hoàn tác, với mỗi lệnh mới được đặt ở trên cùng. Khi bạn đang làm việc với các ngăn xếp, việc thêm các mục mới như thế này được gọi là push
Bây giờ bạn đã quyết định hoàn tác cả ba thay đổi đó, vì vậy bạn nhấn lệnh hoàn tác. Nó lấy mục ở đầu ngăn xếp đang thụt vào nhận xét và xóa mục đó khỏi ngăn xếp
Trình chỉnh sửa của bạn hoàn tác thụt lề và ngăn xếp hoàn tác hiện có hai mục. Thao tác này ngược lại với push và thường được gọi là pop
Khi bạn nhấn hoàn tác lần nữa, mục tiếp theo sẽ bật ra khỏi ngăn xếp
Điều này loại bỏ mục Xóa từ, chỉ để lại một thao tác trên ngăn xếp
Cuối cùng, nếu bạn nhấn Hoàn tác lần thứ ba, thì mục cuối cùng sẽ được bật ra khỏi ngăn xếp
Ngăn xếp hoàn tác hiện trống. Nhấn Hoàn tác lại sau đó sẽ không có tác dụng vì ngăn xếp hoàn tác của bạn trống, ít nhất là trong hầu hết các trình chỉnh sửa. Bạn sẽ thấy điều gì xảy ra khi bạn gọi .pop() trên một ngăn xếp trống trong phần mô tả triển khai bên dưới
Loại bỏ các quảng cáoTriển khai ngăn xếp Python
Có một số tùy chọn khi bạn triển khai ngăn xếp Python. Bài viết này sẽ không bao gồm tất cả chúng, chỉ là những cái cơ bản sẽ đáp ứng hầu hết các nhu cầu của bạn. Bạn sẽ tập trung vào việc sử dụng các cấu trúc dữ liệu là một phần của thư viện Python, thay vì viết các gói của riêng bạn hoặc sử dụng các gói của bên thứ ba
Bạn sẽ xem các triển khai ngăn xếp Python sau đây
- list
- collections.deque
- >>> from collections import deque >>> myStack = deque() >>> myStack.append('a') >>> myStack.append('b') >>> myStack.append('c') >>> myStack deque(['a', 'b', 'c']) >>> myStack.pop() 'c' >>> myStack.pop() 'b' >>> myStack.pop() 'a' >>> myStack.pop() Traceback (most recent call last): File "<console>", line 1, in <module> IndexError: pop from an empty deque 0
Sử dụng list để tạo ngăn xếp Python
Cấu trúc list tích hợp sẵn mà bạn có thể sử dụng thường xuyên trong các chương trình của mình có thể được sử dụng làm ngăn xếp. Thay vì >>> from collections import deque >>> myStack = deque() >>> myStack.append('a') >>> myStack.append('b') >>> myStack.append('c') >>> myStack deque(['a', 'b', 'c']) >>> myStack.pop() 'c' >>> myStack.pop() 'b' >>> myStack.pop() 'a' >>> myStack.pop() Traceback (most recent call last): File "<console>", line 1, in <module> IndexError: pop from an empty deque 3, bạn có thể sử dụng >>> from collections import deque >>> myStack = deque() >>> myStack.append('a') >>> myStack.append('b') >>> myStack.append('c') >>> myStack deque(['a', 'b', 'c']) >>> myStack.pop() 'c' >>> myStack.pop() 'b' >>> myStack.pop() 'a' >>> myStack.pop() Traceback (most recent call last): File "<console>", line 1, in <module> IndexError: pop from an empty deque 4 để thêm các phần tử mới vào đầu ngăn xếp của mình, trong khi .pop() xóa các phần tử theo thứ tự LIFO
>>> >>> myStack = [] >>> myStack.append('a') >>> myStack.append('b') >>> myStack.append('c') >>> myStack ['a', 'b', 'c'] >>> myStack.pop() 'c' >>> myStack.pop() 'b' >>> myStack.pop() 'a' >>> myStack.pop() Traceback (most recent call last): File "<console>", line 1, in <module> IndexError: pop from empty list
Bạn có thể thấy trong lệnh cuối cùng rằng một list sẽ tăng một >>> from collections import deque >>> myStack = deque() >>> myStack.append('a') >>> myStack.append('b') >>> myStack.append('c') >>> myStack deque(['a', 'b', 'c']) >>> myStack.pop() 'c' >>> myStack.pop() 'b' >>> myStack.pop() 'a' >>> myStack.pop() Traceback (most recent call last): File "<console>", line 1, in <module> IndexError: pop from an empty deque 7 nếu bạn gọi .pop() trên một ngăn xếp trống
list có lợi thế là quen thuộc. Bạn biết nó hoạt động như thế nào và có thể đã sử dụng nó trong các chương trình của bạn rồi
Thật không may, list có một vài thiếu sót so với các cấu trúc dữ liệu khác mà bạn sẽ xem xét. Vấn đề lớn nhất là nó có thể gặp vấn đề về tốc độ khi nó phát triển. Các mục trong list được lưu trữ với mục đích cung cấp quyền truy cập nhanh vào các yếu tố ngẫu nhiên trong list. Ở cấp độ cao, điều này có nghĩa là các mục được lưu trữ cạnh nhau trong bộ nhớ
Nếu ngăn xếp của bạn lớn hơn khối bộ nhớ hiện đang chứa nó, thì Python cần thực hiện một số phân bổ bộ nhớ. Điều này có thể dẫn đến một số cuộc gọi >>> from collections import deque >>> myStack = deque() >>> myStack.append('a') >>> myStack.append('b') >>> myStack.append('c') >>> myStack deque(['a', 'b', 'c']) >>> myStack.pop() 'c' >>> myStack.pop() 'b' >>> myStack.pop() 'a' >>> myStack.pop() Traceback (most recent call last): File "<console>", line 1, in <module> IndexError: pop from an empty deque 4 mất nhiều thời gian hơn những cuộc gọi khác
Có một vấn đề ít nghiêm trọng hơn. Nếu bạn sử dụng >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 4 để thêm một phần tử vào ngăn xếp của mình ở vị trí khác với vị trí cuối, thì có thể mất nhiều thời gian hơn. Tuy nhiên, đây không phải là điều bạn thường làm với ngăn xếp
Cấu trúc dữ liệu tiếp theo sẽ giúp bạn giải quyết vấn đề phân bổ lại mà bạn đã thấy với list
Sử dụng collections.deque để tạo ngăn xếp Python
Mô-đun >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 7 chứa , rất hữu ích để tạo ngăn xếp Python. >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 được phát âm là “boong” và là viết tắt của “. ”
Bạn có thể sử dụng các phương pháp tương tự trên >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 như bạn đã thấy ở trên cho list, >>> from collections import deque >>> myStack = deque() >>> myStack.append('a') >>> myStack.append('b') >>> myStack.append('c') >>> myStack deque(['a', 'b', 'c']) >>> myStack.pop() 'c' >>> myStack.pop() 'b' >>> myStack.pop() 'a' >>> myStack.pop() Traceback (most recent call last): File "<console>", line 1, in <module> IndexError: pop from an empty deque 4 và .pop()
>>> >>> from collections import deque >>> myStack = deque() >>> myStack.append('a') >>> myStack.append('b') >>> myStack.append('c') >>> myStack deque(['a', 'b', 'c']) >>> myStack.pop() 'c' >>> myStack.pop() 'b' >>> myStack.pop() 'a' >>> myStack.pop() Traceback (most recent call last): File "<console>", line 1, in <module> IndexError: pop from an empty deque
Điều này trông gần giống với ví dụ list ở trên. Tại thời điểm này, bạn có thể thắc mắc tại sao các nhà phát triển cốt lõi của Python lại tạo ra hai cấu trúc dữ liệu trông giống nhau
Tại sao lại có >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 và list?
Như bạn đã thấy trong cuộc thảo luận về list ở trên, nó được xây dựng dựa trên các khối bộ nhớ liền kề nhau, nghĩa là các mục trong danh sách được lưu trữ ngay cạnh nhau
Điều này hoạt động tốt cho một số hoạt động, như lập chỉ mục vào list. Nhận list9 rất nhanh, vì Python biết chính xác nơi cần tìm trong bộ nhớ để tìm nó. Bố cục bộ nhớ này cũng cho phép các lát hoạt động tốt trên danh sách
Bố cục bộ nhớ liền kề là lý do khiến list có thể cần nhiều thời gian hơn để >>> from collections import deque >>> myStack = deque() >>> myStack.append('a') >>> myStack.append('b') >>> myStack.append('c') >>> myStack deque(['a', 'b', 'c']) >>> myStack.pop() 'c' >>> myStack.pop() 'b' >>> myStack.pop() 'a' >>> myStack.pop() Traceback (most recent call last): File "<console>", line 1, in <module> IndexError: pop from an empty deque 4 một số đối tượng hơn những đối tượng khác. Nếu khối bộ nhớ liền kề đầy, thì nó sẽ cần lấy một khối khác, có thể mất nhiều thời gian hơn so với >>> from collections import deque >>> myStack = deque() >>> myStack.append('a') >>> myStack.append('b') >>> myStack.append('c') >>> myStack deque(['a', 'b', 'c']) >>> myStack.pop() 'c' >>> myStack.pop() 'b' >>> myStack.pop() 'a' >>> myStack.pop() Traceback (most recent call last): File "<console>", line 1, in <module> IndexError: pop from an empty deque 4 bình thường
Mặt khác, >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 được xây dựng dựa trên danh sách liên kết kép. Trong cấu trúc danh sách được liên kết, mỗi mục được lưu trữ trong khối bộ nhớ riêng của nó và có tham chiếu đến mục tiếp theo trong danh sách
Danh sách liên kết đôi cũng giống như vậy, ngoại trừ mỗi mục có tham chiếu đến cả mục trước đó và mục tiếp theo trong danh sách. Điều này cho phép bạn dễ dàng thêm các nút vào cuối danh sách
Việc thêm một mục mới vào cấu trúc danh sách được liên kết chỉ yêu cầu đặt tham chiếu của mục mới để trỏ tới đỉnh hiện tại của ngăn xếp và sau đó trỏ đỉnh ngăn xếp tới mục mới
Tuy nhiên, việc bổ sung và loại bỏ các mục vào ngăn xếp theo thời gian liên tục này đi kèm với sự đánh đổi. Bắt push4 chậm hơn so với danh sách, vì Python cần đi qua từng nút của danh sách để đến phần tử thứ ba
May mắn thay, bạn hiếm khi muốn lập chỉ mục hoặc cắt ngẫu nhiên trên ngăn xếp. Hầu hết các hoạt động trên ngăn xếp là push hoặc pop
Thời gian không đổi Các hoạt động >>> from collections import deque >>> myStack = deque() >>> myStack.append('a') >>> myStack.append('b') >>> myStack.append('c') >>> myStack deque(['a', 'b', 'c']) >>> myStack.pop() 'c' >>> myStack.pop() 'b' >>> myStack.pop() 'a' >>> myStack.pop() Traceback (most recent call last): File "<console>", line 1, in <module> IndexError: pop from an empty deque 4 và .pop() làm cho >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 trở thành một lựa chọn tuyệt vời để triển khai ngăn xếp Python nếu mã của bạn không sử dụng phân luồng
Loại bỏ các quảng cáoNgăn xếp Python và phân luồng
Ngăn xếp Python cũng có thể hữu ích trong các chương trình đa luồng, nhưng nếu bạn không quan tâm đến luồng, thì bạn có thể bỏ qua phần này một cách an toàn và chuyển đến phần tóm tắt
Hai tùy chọn mà bạn đã thấy cho đến nay, list và >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8, hoạt động khác nếu chương trình của bạn có chủ đề
Để bắt đầu với cái đơn giản hơn, bạn không bao giờ nên sử dụng list cho bất kỳ cấu trúc dữ liệu nào có thể được truy cập bởi nhiều luồng. list không an toàn cho luồng
Ghi chú. Nếu bạn cần xem lại các điều kiện chạy đua và an toàn luồng, hãy xem phần Giới thiệu về luồng trong Python
Tuy nhiên, >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 phức tạp hơn một chút. Nếu bạn đọc tài liệu về >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8, nó nói rõ rằng cả hai hoạt động của >>> from collections import deque >>> myStack = deque() >>> myStack.append('a') >>> myStack.append('b') >>> myStack.append('c') >>> myStack deque(['a', 'b', 'c']) >>> myStack.pop() 'c' >>> myStack.pop() 'b' >>> myStack.pop() 'a' >>> myStack.pop() Traceback (most recent call last): File "<console>", line 1, in <module> IndexError: pop from an empty deque 4 và .pop() đều là nguyên tử, nghĩa là chúng sẽ không bị gián đoạn bởi một luồng khác
Vì vậy, nếu bạn hạn chế chỉ sử dụng >>> from collections import deque >>> myStack = deque() >>> myStack.append('a') >>> myStack.append('b') >>> myStack.append('c') >>> myStack deque(['a', 'b', 'c']) >>> myStack.pop() 'c' >>> myStack.pop() 'b' >>> myStack.pop() 'a' >>> myStack.pop() Traceback (most recent call last): File "<console>", line 1, in <module> IndexError: pop from an empty deque 4 và .pop(), thì bạn sẽ an toàn về chủ đề
Mối quan tâm với việc sử dụng >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 trong môi trường luồng là có các phương thức khác trong lớp đó và chúng không được thiết kế đặc biệt để trở thành nguyên tử, cũng như không an toàn cho luồng
Vì vậy, mặc dù có thể xây dựng ngăn xếp Python an toàn cho luồng bằng cách sử dụng >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8, nhưng làm như vậy sẽ khiến bạn bị ai đó lạm dụng nó trong tương lai và gây ra các điều kiện chủng tộc
Được rồi, nếu bạn đang phân luồng, bạn không thể sử dụng list cho ngăn xếp và có thể bạn không muốn sử dụng >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 cho ngăn xếp, vậy làm cách nào bạn có thể tạo ngăn xếp Python cho chương trình phân luồng?
Câu trả lời nằm trong mô-đun pop4, >>> from collections import deque >>> myStack = deque() >>> myStack.append('a') >>> myStack.append('b') >>> myStack.append('c') >>> myStack deque(['a', 'b', 'c']) >>> myStack.pop() 'c' >>> myStack.pop() 'b' >>> myStack.pop() 'a' >>> myStack.pop() Traceback (most recent call last): File "<console>", line 1, in <module> IndexError: pop from an empty deque 0. Hãy nhớ cách bạn học được rằng các ngăn xếp hoạt động theo nguyên tắc Nhập sau/Xuất trước?
Mặc dù giao diện của list và >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 tương tự nhau, nhưng pop6 sử dụng .pop()0 và .pop()1 để thêm và xóa dữ liệu khỏi ngăn xếp
>>> >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty
Không giống như >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8, pop6 được thiết kế để hoàn toàn an toàn cho luồng. Tất cả các phương thức của nó đều an toàn để sử dụng trong môi trường luồng. Nó cũng thêm thời gian chờ tùy chọn vào các hoạt động của nó, đây thường là tính năng bắt buộc phải có trong các chương trình theo luồng
Tuy nhiên, sự an toàn toàn bộ luồng này phải trả giá. Để đạt được sự an toàn cho luồng này, pop6 phải thực hiện thêm một chút công việc trên mỗi thao tác, nghĩa là sẽ mất nhiều thời gian hơn một chút
Thông thường, sự chậm lại một chút này sẽ không ảnh hưởng đến tốc độ chương trình tổng thể của bạn, nhưng nếu bạn đã đo hiệu suất của mình và phát hiện ra rằng các hoạt động ngăn xếp của bạn là nút cổ chai, thì việc chuyển đổi cẩn thận sang >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 có thể đáng làm
Tôi muốn nhấn mạnh lại rằng việc chuyển từ pop6 sang >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 vì nó nhanh hơn mà không có các phép đo cho thấy hoạt động ngăn xếp của bạn là một nút cổ chai là một ví dụ về. Đừng làm thế
Ngăn xếp Python. Bạn nên sử dụng triển khai nào?
Nói chung, bạn nên sử dụng >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 nếu bạn không sử dụng luồng. Nếu bạn đang sử dụng luồng, thì bạn nên sử dụng pop6 trừ khi bạn đã đo lường hiệu suất của mình và thấy rằng tốc độ đẩy và bật tăng lên một chút sẽ tạo ra sự khác biệt đủ để đảm bảo rủi ro bảo trì
list có thể quen thuộc, nhưng nên tránh vì nó có thể có vấn đề về phân bổ lại bộ nhớ. Các giao diện cho >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 và list giống hệt nhau và >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 không có những vấn đề này, điều này làm cho >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 trở thành lựa chọn tốt nhất cho ngăn xếp Python không theo luồng của bạn
Loại bỏ các quảng cáoPhần kết luận
Bây giờ bạn đã biết ngăn xếp là gì và đã thấy các tình huống mà chúng có thể được sử dụng trong các chương trình thực tế. Bạn đã đánh giá ba tùy chọn khác nhau để triển khai ngăn xếp và thấy rằng >>> from queue import LifoQueue >>> myStack = LifoQueue() >>> myStack.put('a') >>> myStack.put('b') >>> myStack.put('c') >>> myStack <queue.LifoQueue object at 0x7f408885e2b0> >>> myStack.get() 'c' >>> myStack.get() 'b' >>> myStack.get() 'a' >>> # myStack.get() <--- waits forever >>> myStack.get_nowait() Traceback (most recent call last): File "<console>", line 1, in <module> File "/usr/lib/python3.7/queue.py", line 198, in get_nowait return self.get(block=False) File "/usr/lib/python3.7/queue.py", line 167, in get raise Empty _queue.Empty 8 là một lựa chọn tuyệt vời cho các chương trình không theo luồng. Nếu bạn đang triển khai ngăn xếp trong môi trường phân luồng, thì có thể bạn nên sử dụng pop6
Bây giờ bạn có thể
- Nhận biết khi nào một ngăn xếp sẽ là một cấu trúc dữ liệu tốt
- Chọn triển khai nào phù hợp với vấn đề của bạn
Nếu bạn vẫn còn thắc mắc, vui lòng liên hệ trong phần bình luận bên dưới. Bây giờ, hãy viết một số mã vì bạn đã có một công cụ khác để giúp bạn giải quyết các vấn đề lập trình của mình
Đánh dấu là đã hoàn thành
Xem ngay Hướng dẫn này có một khóa học video liên quan do nhóm Real Python tạo. Xem nó cùng với hướng dẫn bằng văn bản để hiểu sâu hơn. Cách triển khai ngăn xếp Python
🐍 Thủ thuật Python 💌
Nhận một Thủ thuật Python ngắn và hấp dẫn được gửi đến hộp thư đến của bạn vài ngày một lần. Không có thư rác bao giờ. Hủy đăng ký bất cứ lúc nào. Được quản lý bởi nhóm Real Python
Gửi cho tôi thủ thuật Python »
Về Jim Anderson
Jim đã lập trình trong một thời gian dài bằng nhiều ngôn ngữ. Anh ấy đã làm việc trên các hệ thống nhúng, xây dựng các hệ thống xây dựng phân tán, quản lý nhà cung cấp nước ngoài và tham gia rất nhiều cuộc họp
» Thông tin thêm về JimMỗi hướng dẫn tại Real Python được tạo bởi một nhóm các nhà phát triển để nó đáp ứng các tiêu chuẩn chất lượng cao của chúng tôi. Các thành viên trong nhóm đã làm việc trong hướng dẫn này là
Aldren
Joanna
Mike
Bậc thầy Kỹ năng Python trong thế giới thực Với quyền truy cập không giới hạn vào Python thực
Tham gia với chúng tôi và có quyền truy cập vào hàng nghìn hướng dẫn, khóa học video thực hành và cộng đồng các Pythonistas chuyên gia
Nâng cao kỹ năng Python của bạn »
Chuyên gia Kỹ năng Python trong thế giới thực
Với quyền truy cập không giới hạn vào Python thực
Tham gia với chúng tôi và có quyền truy cập vào hàng ngàn hướng dẫn, khóa học video thực hành và cộng đồng Pythonistas chuyên gia
Nâng cao kỹ năng Python của bạn »
Bạn nghĩ sao?
Đánh giá bài viết này
Tweet Chia sẻ Chia sẻ EmailBài học số 1 hoặc điều yêu thích mà bạn đã học được là gì?
Mẹo bình luận. Những nhận xét hữu ích nhất là những nhận xét được viết với mục đích học hỏi hoặc giúp đỡ các sinh viên khác. và nhận câu trả lời cho các câu hỏi phổ biến trong cổng thông tin hỗ trợ của chúng tôi