Hướng dẫn what python data type is used for stack? - kiểu dữ liệu python nào được sử dụng cho ngăn xếp?

Một ngăn xếp là một tập hợp các đối tượng hỗ trợ ngữ nghĩa nhanh, lần đầu tiên (LIFO) để chèn và xóa. Không giống như danh sách hoặc mảng, các ngăn xếp thường không cho phép truy cập ngẫu nhiên vào các đối tượng mà chúng chứa. Các hoạt động chèn và xóa cũng thường được gọi là đẩy và pop.

Một sự tương tự trong thế giới thực hữu ích cho cấu trúc dữ liệu ngăn xếp là một ngăn xếp các tấm:

Các tấm mới được thêm vào đỉnh của ngăn xếp. Và bởi vì các tấm là quý giá và nặng, chỉ có thể di chuyển tấm trên cùng (lần cuối, lần đầu tiên). Để đạt được các tấm thấp hơn trong ngăn xếp, các tấm trên cùng phải được loại bỏ từng cái một.

Ngăn xếp và hàng đợi là tương tự nhau. Họ là cả hai bộ sưu tập tuyến tính của các mặt hàng và sự khác biệt nằm theo thứ tự các mục được truy cập trong:

Với một hàng đợi, bạn loại bỏ mục ít được thêm gần đây (đầu tiên, đầu tiên hoặc FIFO); Và với một ngăn xếp, bạn loại bỏ mục được thêm gần đây nhất (lần cuối, lần đầu tiên hoặc LIFO).queue you remove the item least recently added (first-in, first-out or FIFO); and with a stack you remove the item most recently added (last-in, first-out or LIFO).

Hiệu suất khôn ngoan, một triển khai ngăn xếp thích hợp dự kiến ​​sẽ mất thời gian O (1) để chèn và xóa các hoạt động.

Các ngăn xếp có một loạt các cách sử dụng trong các thuật toán, ví dụ như trong phân tích ngôn ngữ và quản lý bộ nhớ thời gian chạy (Call Call Stack trực tiếp). Một thuật toán ngắn và đẹp sử dụng ngăn xếp là tìm kiếm sâu (DFS) trên cấu trúc dữ liệu cây hoặc đồ thị.

Các tàu Python với một số triển khai ngăn xếp mà mỗi người có các đặc điểm hơi khác nhau. Hãy cùng xem họ:

✅ Danh sách tích hợp

Loại list tích hợp của Python, tạo ra một cấu trúc dữ liệu ngăn xếp tốt khi nó hỗ trợ các hoạt động đẩy và pop trong thời gian khấu hao O (1).

Danh sách Python, được triển khai dưới dạng các mảng động bên trong, điều đó có nghĩa là chúng thường cần thay đổi kích thước không gian lưu trữ cho các yếu tố được lưu trữ trong chúng khi các phần tử được thêm hoặc loại bỏ. Danh sách phân bổ quá mức lưu trữ sao lưu của nó để không phải mọi cú hích hoặc POP đều yêu cầu thay đổi kích thước và bạn có được độ phức tạp thời gian O (1) được khấu hao cho các hoạt động này.

Nhược điểm là điều này làm cho hiệu suất của chúng ít nhất quán hơn so với các chèn và xóa O (1) ổn định được cung cấp bởi một triển khai dựa trên danh sách được liên kết (như collections.deque, xem bên dưới). Mặt khác, danh sách cung cấp truy cập ngẫu nhiên thời gian O (1) nhanh chóng vào các yếu tố trên ngăn xếp có thể là một lợi ích bổ sung.

Ở đây, một cảnh báo hiệu suất quan trọng khi sử dụng danh sách làm ngăn xếp:important performance caveat when using lists as stacks:

Để có được hiệu suất O (1) khấu hao để chèn và xóa các mục mới phải được thêm vào cuối danh sách bằng phương thức append() và được xóa lại từ cuối bằng cách sử dụng pop(). Các ngăn xếp dựa trên danh sách Python phát triển sang phải và co lại bên trái.

Thêm và loại bỏ từ phía trước chậm hơn nhiều và mất thời gian O (n), vì các phần tử hiện có phải được thay đổi xung quanh để nhường chỗ cho phần tử mới.

# How to use a Python list as a stack (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 Class

Lớp deque thực hiện một hàng đợi hai kết thúc hỗ trợ thêm và loại bỏ các phần tử từ hai đầu trong thời gian O (1) (không amortized).

Bởi vì các deques hỗ trợ thêm và loại bỏ các yếu tố từ hai đầu tốt như nhau, chúng có thể phục vụ cả xếp hàng và như là ngăn xếp.

Các đối tượng Deque Python sườn được triển khai dưới dạng danh sách liên kết gấp đôi, cung cấp cho chúng hiệu suất tuyệt vời và nhất quán để chèn và xóa các yếu tố, nhưng hiệu suất O (N) kém để truy cập ngẫu nhiên các yếu tố ở giữa ngăn xếp.

collections.deque là một lựa chọn tuyệt vời nếu bạn đang tìm kiếm một cấu trúc dữ liệu ngăn xếp trong thư viện tiêu chuẩn 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.

# How to use collections.deque as a stack (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"

✅ Lớp hàng đợi.lifoqueue

Việc triển khai ngăn xếp này trong Thư viện tiêu 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 queue chứa một số lớp khác thực hiện các hàng đợi đa nhà sản xuất, đa tiêu dùng, hữu ích cho điện 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 trên đầu không cần thiết. Trong trường hợp này, bạn sẽ tốt hơn khi sử dụng list hoặc deque như một ngăn xếp mục đích chung.

# How to use queue.LifoQueue as a stack:

from queue import LifoQueue
s = LifoQueue()

s.put('eat')
s.put('sleep')
s.put('code')

>>> s
<queue.LifoQueue object at 0x108298dd8>

>>> s.get()
'code'
>>> s.get()
'sleep'
>>> s.get()
'eat'

>>> s.get_nowait()
queue.Empty

>>> s.get()
# Blocks / waits forever...

Một lựa chọn mặc định tốt: collections.deque

Nếu bạn không tìm kiếm hỗ trợ xử lý song song (hoặc không muốn xử lý việc khóa và mở khóa bằng tay), sự lựa chọn của bạn sẽ thuộc loại list tích hợp hoặc collections.deque.

Sự khác biệt nằm trong cấu trúc dữ liệu được sử dụng đằng sau hậu trường và dễ sử dụng.

• list được hỗ trợ bởi một mảng động làm cho nó tuyệt vời cho truy cập ngẫu nhiên nhanh nhưng yêu cầu thay đổi kích thước thỉnh thoảng khi các phần tử được thêm hoặc loại bỏ. Danh sách phân bổ quá mức lưu trữ sao lưu của nó để không phải mọi cú hích hoặc POP đều yêu cầu thay đổi kích thước và bạn có được độ phức tạp thời gian O (1) được khấu hao cho các hoạt động này. Nhưng bạn cần phải cẩn thận chỉ để chèn và loại bỏ các mục từ phía bên phải (

  # How to use collections.deque as a stack (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"
  

  6 và

  # How to use collections.deque as a stack (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"
  

  7) hoặc hiệu suất khác chậm lại thành O (n).

• collections.deque được hỗ trợ bởi một danh sách liên kết gấp đôi nhằm tối ưu hóa việc bổ sung và xóa ở cả hai đầu và cung cấp hiệu suất O (1) nhất quán cho các hoạt động này. Hiệu suất của nó không chỉ ổn định hơn, lớp deque cũng dễ sử dụng hơn bởi vì bạn không phải lo lắng về việc thêm hoặc loại bỏ các mặt hàng khỏi kết thúc sai.

Vì những lý do này, collections.deque đưa ra một lựa chọn tuyệt vời để thực hiện cấu trúc dữ liệu ngăn xếp (hàng đợi LIFO) trong Python.

Đọc các cấu trúc dữ liệu cơ bản đầy đủ trên mạng trong loạt bài viết của Python tại đây. Bài viết này bị thiếu một cái gì đó hoặc bạn đã tìm thấy một lỗi? Giúp một người anh em ra ngoài và để lại một bình luận dưới đây.