Trong hướng dẫn này, chúng ta sẽ thảo luận về các khái niệm cơ bản của Queue và lớp Queue tích hợp và triển khai nó bằng mã Python
Hàng đợi là gì?
Hàng đợi là một kiểu cấu trúc dữ liệu tuyến tính được sử dụng để lưu trữ dữ liệu theo trình tự. Khái niệm về hàng đợi dựa trên FIFO, có nghĩa là "Vào trước ra trước". Nó còn được gọi là "ai đến trước được phục vụ trước". Hàng đợi có hai đầu phía trước và phía sau. Phần tử tiếp theo được chèn vào từ phía sau và bị xóa khỏi phía trước
Ví dụ - Có 20 máy tính trong phòng thí nghiệm khoa học máy tính và được kết nối với một máy in. Các sinh viên muốn in giấy của họ; . Nếu chúng tôi là người xếp hàng cuối cùng, chúng tôi cần đợi cho đến khi tất cả các nhiệm vụ khác được hoàn thành trước chúng tôi
Hệ điều hành quản lý hàng đợi để xử lý các quy trình khác nhau trong máy tính
Thao tác trong Python
Chúng ta có thể thực hiện các thao tác sau trong Queue
- Enqueue - Enqueue là một hoạt động mà chúng tôi thêm các mục vào hàng đợi. Nếu hàng đợi đầy, đó là điều kiện của Hàng đợi. Độ phức tạp về thời gian của enqueue là O[1]
- Dequeue - Dequeue là một hoạt động trong đó chúng tôi loại bỏ một phần tử khỏi hàng đợi. Một phần tử được loại bỏ theo thứ tự như nó được chèn vào. Nếu hàng đợi trống, đó là điều kiện của Luồng dưới hàng đợi. Độ phức tạp thời gian của dequeue là O[1]
- Mặt trước - Một phần tử được chèn vào mặt trước. Độ phức tạp thời gian của phía trước là O[1]
- Phía sau - Một phần tử được loại bỏ khỏi phía sau. Độ phức tạp thời gian của phía sau là O[1]
Các phương thức có sẵn trong hàng đợi
Python cung cấp các phương thức sau, thường được sử dụng để thực hiện thao tác trong Hàng đợi
- put[item] - Chức năng này được sử dụng để chèn phần tử vào hàng đợi
- get[] - Hàm này được sử dụng để trích xuất phần tử từ hàng đợi
- trống [] - Hàm này được sử dụng để kiểm tra xem hàng đợi có trống hay không. Nó trả về true nếu hàng đợi trống
- qsize - Hàm này trả về độ dài của hàng đợi
- full[] - Nếu hàng đợi đầy trả về true;
Chúng ta sẽ tìm hiểu các chức năng này trong các phần dưới đây
Danh sách Python tích hợp
Danh sách có thể được sử dụng làm hàng đợi, nhưng nó không phù hợp với góc độ hiệu suất. Python cung cấp các phương thức tích hợp sẵn hàm insert[] và pop[] để thêm và xóa các phần tử. Danh sách khá chậm vì nếu chúng ta chèn một phần tử mới vào danh sách, tất cả các phần tử sẽ yêu cầu dịch chuyển theo một. Phải mất O[n] thời gian. Vì vậy, danh sách được khuyến nghị thay cho hàng đợi. Hãy hiểu ví dụ sau về cách danh sách có thể được sử dụng làm hàng đợi
Ví dụ -
đầu ra
['Apple', 'Mango', 'Papaya'] Apple
Giải trình -
Chúng tôi đã xác định danh sách trống trong đoạn mã trên và chèn một vài phần tử bằng phương thức append[]. Nó sẽ thêm một phần tử vào cuối danh sách
Thêm phần tử vào hàng đợi [Enqueue]
Chúng ta có thể thêm phần tử from vào phía sau. Quá trình này còn được gọi là enqueue. Chúng tôi tạo một lớp Hàng đợi nơi chúng tôi sẽ triển khai khái niệm Nhập trước xuất trước. Hãy hiểu ví dụ sau
Ví dụ -
đầu ra
Xóa phần tử khỏi hàng đợi [Dequeue]
Chúng ta có thể loại bỏ các phần tử từ phía sau. Quá trình này được gọi là dequeue. Trong ví dụ sau, chúng tôi sử dụng phương thức pop[] tích hợp để xóa một phần tử khỏi danh sách
Ví dụ -
đầu ra
Giải trình -
Trong đoạn mã trên, chúng ta đã định nghĩa một lớp có tên Queue và hàm tạo trong đó. Chúng tôi đã gán một hàm tạo danh sách cho biến hàng đợi. Sau đó, chúng tôi đã xác định hai phương thức - add_element[] và remove_element[]. Trong khối add_element[] chúng ta kiểm tra điều kiện nếu giá trị không có trong Queue. Nếu không có giá trị, hãy chèn phần tử
Trong khối chức năng remove_element[], chúng ta kiểm tra điều kiện xem hàng đợi có bị tràn hay không. Nếu nó trả về false, thì hãy loại bỏ từng phần tử một
Sắp xếp hàng đợi
Trong ví dụ sau, chúng tôi đã sắp xếp các phần tử của hàng đợi
Ví dụ -
đầu ra
Mô-đun hàng đợi
Python cung cấp mô-đun hàng đợi để triển khai hàng đợi nhiều nhà sản xuất, nhiều người tiêu dùng. Mô-đun hàng đợi cung cấp lớp Hàng đợi được sử dụng đặc biệt cho lập trình luồng. Lớp Queue thực hiện tất cả các ngữ nghĩa khóa cần thiết
Chúng tôi có thể thực hiện tất cả các thao tác bằng cách sử dụng lớp hàng đợi dựng sẵn
Làm việc với hàng đợi. Lớp xếp hàng
Mô-đun hàng đợi chứa một số lớp. Queue là một trong những class quan trọng của chúng. Điều này rất hữu ích trong tính toán song song và đa chương trình. Hãy hiểu ví dụ sau về hàng đợi. Lớp xếp hàng0uii
Ví dụ -
đầu ra
Apple
Mango
Papaya
Traceback [most recent call last]:
File "C:/Users/DEVANSH SHARMA/PycharmProjects/Hello/Queue.py", line 78, in
print[que.get_nowait[]]
File "C:\Python\lib\queue.py", line 198, in get_nowait
return self.get[block=False]
File "C:\Python\lib\queue.py", line 167, in get
raise Empty
_queue.Empty
Làm việc với bộ sưu tập. Lớp deque
Bộ sưu tập. lớp deque được sử dụng để triển khai hàng đợi hai đầu hỗ trợ thêm và xóa phần tử ở cả hai đầu. Phải mất O[1] thời gian để hoàn thành quá trình
Lớp deque có thể được sử dụng trong cả Hàng đợi và dưới dạng ngăn xếp vì nó loại bỏ và thêm các phần tử một cách hiệu quả
Bộ sưu tập. deque có thể là một lựa chọn tốt cho cấu trúc dữ liệu hàng đợi trong thư viện chuẩn của Python
Ví dụ -
đầu ra
deque[['Apple', 'Mango', 'Banana']]
Apple
Mango
Banana
Traceback [most recent call last]:
File "C:/Users/DEVANSH SHARMA/PycharmProjects/Hello/Queue.py", line 101, in
que.popleft[]
IndexError: pop from an empty deque
đa xử lý. Lớp xếp hàng
đa xử lý. Lớp hàng đợi được sử dụng để triển khai các mục được xếp hàng đợi để xử lý song song bởi các công nhân đa dòng. đa xử lý. Hàng đợi chia sẻ dữ liệu giữa các quy trình và có thể lưu trữ bất kỳ đối tượng nào có thể chọn. Hãy hiểu ví dụ sau
Ví dụ -
đầu ra
Apple Mango Banana
Hàng đợi ưu tiên trong Python
Hàng đợi ưu tiên là một loại hàng đợi đặc biệt trong cấu trúc dữ liệu. Như tên cho thấy, nó sắp xếp các phần tử và sắp xếp các phần tử dựa trên mức độ ưu tiên của chúng
Không giống như hàng đợi thông thường, nó lấy phần tử có mức ưu tiên cao nhất thay vì phần tử tiếp theo. Mức độ ưu tiên của các phần tử riêng lẻ được quyết định bằng thứ tự áp dụng cho các khóa của chúng
Hàng đợi ưu tiên có lợi nhất để xử lý các vấn đề lập lịch trong đó một số nhiệm vụ sẽ xảy ra dựa trên mức độ ưu tiên
Ví dụ - Một tác vụ của hệ điều hành là ví dụ tốt nhất về hàng đợi ưu tiên - Nó thực thi các tác vụ có mức độ ưu tiên cao so với các tác vụ có mức độ ưu tiên thấp hơn [tải xuống các bản cập nhật trong nền]. Bộ lập lịch tác vụ có thể cho phép các tác vụ có mức độ ưu tiên cao nhất chạy trước
Có nhiều cách khác nhau để triển khai hàng đợi ưu tiên trong Python. Hãy hiểu những cách sau đây
Danh sách được sắp xếp thủ công
Chúng ta có thể sử dụng danh sách Python được sắp xếp làm hàng đợi ưu tiên để nhanh chóng xác định và xóa phần tử nhỏ hơn và lớn nhất. Nhưng việc chèn phần tử mới chậm vì phải thực hiện thao tác O[n]
Do đó, danh sách được sắp xếp có thể hiệu quả khi sẽ có ít lần chèn vào hàng đợi ưu tiên
Hãy hiểu ví dụ sau -
Ví dụ -
đầu ra
[1, 'Mango'] [2, 'Apple'] [3, 'Banana']
hàng đợi. Lớp PriorityQueue
Hàng đợi ưu tiên này triển khai sử dụng heapq trong nội bộ và chia sẻ cùng độ phức tạp về thời gian và không gian
Sự khác biệt là hàng đợi ưu tiên được phối hợp và cung cấp khóa ngữ nghĩa để sao lưu nhiều sự kiện đồng thời và người tiêu dùng
Ví dụ -
đầu ra
[1, 'Banana'] [2, 'Apple'] [3, 'Mango']
Chúng tôi có thể chọn bất kỳ triển khai hàng đợi ưu tiên nào trong chương trình Python nhưng hãy nhớ rằng hàng đợi. PriorityQueue là lựa chọn mặc định tốt
Phần kết luận
Chúng ta đã thảo luận tất cả các khái niệm cơ bản về hàng đợi và cách triển khai nó. Nó tương tự như danh sách tiêu chuẩn, nhưng về mặt hiệu suất thì nó luôn tốt hơn. Chúng tôi cũng đã xác định hàng đợi ưu tiên và các cách thực hiện khác nhau của nó