Trong Python, rất dễ dàng để triển khai cấu trúc dữ liệu stack và queue. Stack được gọi là LIFO vì Stack hoạt động theo nguyên tắc "Last-in, first-out" (vào sau ra trước) và Queue được gọi là FIFO vì Queue hoạt động theo nguyên tắc "First-in, first-out" (vào trước ra trước), và các hàm built-in trong Python làm cho mã ngắn gọn và đơn giản.
Module Queue triển khai hàng đợi multi-producer, multi-consumer và nó đặc biệt hữu ích trong lập trình đa luồng khi thông tin phải được trao đổi an toàn giữa nhiều luồng. Lớp Queue trong module này triển khai tất cả ngữ nghĩa khóa bắt buộc và nó phụ thuộc vào sự có sẵn của hỗ trợ luồng trong Python.
Module này triển khai ba loại hàng đợi, chỉ khác nhau về thứ tự các mục được truy xuất. Đối với hàng đợi FIFO, tác vụ đầu tiên được thêm là tác vụ đầu tiên được truy xuất và đối với hàng đợi LIFO, mục được thêm gần đây nhất là mục đầu tiên được truy xuất (hoạt động như một stack). Và đối với hàng đợi ưu tiên, các mục được giữ được sắp xếp (sử dụng module heapq) và mục có giá trị thấp nhất được truy xuất đầu tiên.
Module hàng đợi này định nghĩa các lớp và ngoại lệ sau:
class Queue.Queue(maxsize=0)
Đây là constructor cho hàng đợi FIFO. Tham số maxsize là một số nguyên đặt giới hạn trên trên số lượng mục có thể đặt trong hàng đợi. Chèn sẽ bị chặn một khi kích thước này đạt đến, cho đến khi các mục hàng đợi được tiêu thụ. Nếu maxsize nhỏ hơn hoặc bằng không thì kích thước hàng đợi sẽ là vô hạn.
class Queue.LifoQueue(maxsize=0)
Đây là constructor cho hàng đợi LIFO. Tham số maxsize là một số nguyên đặt giới hạn trên trên số lượng mục có thể đặt trong hàng đợi. Chèn sẽ bị chặn một khi kích thước này đạt đến, cho đến khi các mục hàng đợi được tiêu thụ. Nếu maxsize nhỏ hơn hoặc bằng không thì kích thước hàng đợi sẽ là vô hạn.
class Queue.PriorityQueue(maxsize=0)
Đây là constructor cho hàng đợi ưu tiên. Tham số maxsize là một số nguyên đặt giới hạn trên trên số lượng mục có thể đặt trong hàng đợi. Chèn sẽ bị chặn một khi kích thước này đạt đến, cho đến khi các mục hàng đợi được tiêu thụ. Nếu maxsize nhỏ hơn hoặc bằng không thì kích thước hàng đợi là vô hạn.
exception Queue.Empty
Dòng này chỉ ra ngoại lệ được ném khi get() không chặn (hoặc get_nowait()) được gọi trên đối tượng Queue rỗng.
exception Queue.Full
Dòng này chỉ ra ngoại lệ được ném khi put() không chặn (hoặc put_nowait()) được gọi trên đối tượng Queue đầy.
Đối tượng Queue
Queue.qsize()
Hàm này trả về kích thước xấp xỉ của hàng đợi.
Queue.empty()
Hàm này trả về True nếu hàng đợi rỗng ngược lại False. Nếu empty() trả về True nó không đảm bảo rằng một lời gọi tiếp theo đến put() sẽ không chặn. Tương tự, nếu empty() trả về False nó không đảm bảo rằng một lời gọi tiếp theo đến get() sẽ không chặn.
Queue.full()
Trả về True nếu hàng đợi đầy, False ngược lại. Nếu full() trả về True nó không đảm bảo rằng một lời gọi tiếp theo đến get() sẽ không chặn. Tương tự, nếu full() trả về False nó không đảm bảo rằng một lời gọi tiếp theo đến put() sẽ không chặn.
Queue.put(item[, block[, timeout]])
Đặt mục vào hàng đợi. Nếu đối số tùy chọn block là true và timeout là None (mặc định), chặn nếu cần thiết cho đến khi một khe trống có sẵn. Nếu timeout là một số dương, nó chặn tối đa timeout giây và ném ngoại lệ Full nếu không có khe trống nào có sẵn trong thời gian đó. Ngược lại (block là false), đặt một mục lên hàng đợi nếu một khe trống ngay lập tức có sẵn, ngược lại ném ngoại lệ Full (timeout bị bỏ qua trong trường hợp đó).
Queue.get([block[, timeout]])
Xóa và trả về một mục từ hàng đợi. Nếu đối số tùy chọn block là true và timeout là None (mặc định), chặn nếu cần thiết cho đến khi một mục có sẵn. Nếu timeout là một số dương, nó chặn tối đa timeout giây và ném ngoại lệ Empty nếu không có mục nào có sẵn trong thời gian đó. Ngược lại (block là false), trả về một mục nếu có sẵn ngay lập tức, ngược lại ném ngoại lệ Empty (timeout bị bỏ qua trong trường hợp đó).
Queue.task_done()
Chỉ ra rằng một tác vụ đã được xếp hàng trước đó đã hoàn thành. Được sử dụng bởi các luồng tiêu thụ hàng đợi. Với mỗi get() được dùng để lấy một tác vụ, một lời gọi tiếp theo đến task_done() báo cho hàng đợi rằng xử lý trên tác vụ đó đã hoàn tất.
Nếu join() hiện đang chặn, nó sẽ tiếp tục khi tất cả các mục đã được lấy và xử lý (nghĩa là lời gọi task_done() đã được nhận cho mọi mục đã được put() vào hàng đợi).
Ném ValueError nếu được gọi nhiều lần hơn số mục được đặt trong hàng đợi.
Queue.join()
Chặn cho đến khi tất cả các mục trong hàng đợi đã được lấy và xử lý.
Số lượng tác vụ chưa hoàn thành tăng lên mỗi khi một mục được thêm vào hàng đợi. Số lượng giảm xuống mỗi khi một luồng tiêu thụ gọi task_done() để chỉ ra rằng mục đã được truy xuất và tất cả công việc trên nó đã hoàn thành. Khi số lượng tác vụ chưa hoàn thành giảm xuống không, join() bỏ chặn.
Mã ví dụ
import queue # Dung lượng tối đa của hàng đợi là 20 Q = queue.Queue(maxsize=40) Q.put(50) Q.put(90) Q.put(10) Q.put(70) print(Q.get()) print(Q.get()) print(Q.get()) print(Q.get())
Đầu ra
50 90 10 70
Ví dụ Underflow/Overflow
import queue
Q = queue.Queue(maxsize=30)
print(Q.qsize())
Q.put(50)
Q.put(90)
Q.put(10)
Q.put(70)
print("Full: ", Q.full())
Q.put(90)
Q.put(100)
print("Full: ", Q.full())
print(Q.get())
print(Q.get())
print(Q.get())
print("Empty: ", Q.empty())
print(Q.get())
print(Q.get())
print(Q.get())
print("Empty: ", Q.empty())
print("Full: ", Q.full())
Đầu ra
0 Full: False Full: False 50 90 10 Empty: False 70 90 100 Empty: True Full: False
Ví dụ 3 của Stack
import queue
S = queue.LifoQueue(maxsize=10)
# qsize() cho maxsize của Queue
print(S.qsize())
S.put(50)
S.put(90)
S.put(10)
S.put(70)
S.put(90)
S.put(10)
print("Full: ", S.full())
print("Size: ", S.qsize())
# Dữ liệu sẽ được truy cập theo thứ tự ngược lại của Queue
print(S.get())
print(S.get())
print(S.get())
print(S.get())
print(S.get())
print("Empty: ", S.empty())
Đầu ra
0 Full: False Size: 6 10 90 70 10 90 Empty: False