Hàng đợi là một cấu trúc dữ liệu tuyến tính hoạt động trên Nhập trước xuất trước cơ chế (FIFO).
Phần tử nhập đầu tiên trong hàng đợi là phần tử đầu tiên được xử lý.
Ví dụ
Cấu trúc dữ liệu hàng đợi có thể được hiểu với sự trợ giúp của hàng đợi tại trạm xe buýt. Người đến đầu tiên tại bến xe buýt là người đầu tiên trong hàng đợi và những người khác đứng anh ta khi họ đến bến xe buýt. Khi xe buýt đến, người đến trước ở trạm xe buýt sẽ là người đầu tiên bước vào xe buýt và những người còn lại sẽ vào theo thứ tự đã đến trạm xe buýt. Do đó, cơ chế ĐẦU VÀO ĐẦU TIÊN được tuân theo.
Triển khai hàng đợi trong Python
Hàng đợi trong Python có thể được triển khai theo nhiều cách khác nhau bằng cách sử dụng các cấu trúc dữ liệu tuyến tính khác hoặc các mô-đun tích hợp sẵn trong thư viện Python.
Phương pháp 1 - Triển khai bằng cách sử dụng danh sách
Hàng đợi trong Python có thể được triển khai bằng cách sử dụng danh sách. Nó không hiệu quả lắm vì việc chèn hoặc xóa một phần tử ở đầu danh sách mất O (n) thời gian, chậm hơn so với việc triển khai bằng các cách khác.
Các hoạt động liên quan
append () - Hàm này thêm một phần tử vào cuối hàng đợi.
pop (0) - Hàm này loại bỏ và trả về phần tử đầu tiên trong hàng đợi.
Ví dụ
queue=[]
queue.append(1)
queue.append(2)
queue.append(3)
print("Initial queue",queue)
print("Element popped from the queue")
print(queue.pop(0))
print(queue.pop(0))
print("Queue after popping some elements",queue) Đầu ra
Initial queue [1, 2, 3] Element popped from the queue 1 2 Queue after popping some elements [3]
Bạn không thể xóa thêm phần tử khi hàng đợi trống. Làm như vậy dẫn đến một ngoại lệ.
queue.pop(0) IndexError: pop from empty list
Phương pháp 2 - Triển khai bằng queue.Queue
Đây là cách để triển khai hàng đợi bằng cách sử dụng mô-đun sẵn có từ python. Chúng ta cần nhập Hàng đợi từ hàng đợi. Chúng ta có thể khởi tạo hàng đợi với một số kích thước cụ thể. Kích thước bằng 0 có nghĩa là một hàng đợi vô hạn.
Các hoạt động liên quan
kích thước tối đa - số phần tử tối đa được phép trong một hàng đợi
get () - loại bỏ và trả về phần tử đầu tiên từ hàng đợi. Nếu hàng đợi trống, hãy đợi cho đến khi hàng đợi có ít nhất một phần tử.
get_nowait () - loại bỏ và trả về phần tử đầu tiên khỏi hàng đợi. Nếu hàng đợi trống, hãy nêu ra một ngoại lệ.
đặt (mục) - thêm một phần tử vào cuối hàng đợi. Nếu hàng đợi đầy, hãy đợi cho đến khi có sẵn vị trí trống.
put_nowait (item) - thêm một phần tử vào cuối hàng đợi. Nếu hàng đợi đầy, hãy đưa ra một ngoại lệ.
đầy đủ () - trả về true nếu hàng đợi đầy, nếu không trả về false.
trống () - trả về True nếu hàng đợi trống, ngược lại là false
qsize () - trả về số phần tử có trong hàng đợi
Ví dụ
from queue import Queue
q=Queue(maxsize=3)
q.put(1)
q.put(2)
q.put(3)
print("Is queue full",q.full())
print("Element popped from the queue")
print(q.get())
print(q.get())
print("Number of elements in queue",q.qsize())
print("Is queue empty",q.empty()) Đầu ra
Is queue full True Element popped from the queue 1 2 Number of elements in queue 1 Is queue empty False
Phương pháp 3 - Triển khai bằng cách sử dụng collection.deque
Đây là một cách khác để triển khai hàng đợi trong Python. Chúng tôi cần nhập deque từ mô-đun bộ sưu tập.
Các hoạt động liên quan
append () - Hàm này thêm một phần tử vào cuối hàng đợi.
popleft () - Hàm này loại bỏ và trả về phần tử đầu tiên trong hàng đợi với độ phức tạp thời gian O (1).
Ví dụ
from collections import deque
queue=deque()
queue.append(1)
queue.append(2)
queue.append(3)
print("Intial queue: ",queue)
print("Element popped from the queue")
print(queue.popleft())
print(queue.popleft())
print("Queue after popping some elements: ",queue) Đầu ra
Intial queue: deque([1, 2, 3]) Element popped from the queue 1 2 Queue after popping some elements: deque([3])
Sử dụng hàm popleft () trên một deque trống sẽ tạo ra một ngoại lệ.