Phương pháp nào được sử dụng để thêm phần tử vào hàng đợi python?

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 từ phần cuối phía sau và được xóa khỏi phần đầu

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 xóa một phần tử khỏi hàng đợi. Một phần tử được loại bỏ theo thứ tự như khi 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

Thí 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

Thí 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

Thí 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[] 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 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

Thí 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

Thí 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

Thí 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

Thí 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 -

Thí dụ -

đầu ra

[1, 'Mango']
[2, 'Apple']
[3, 'Banana']

hàng đợi. Lớp PriorityQueue

Việc triển khai hàng đợi ưu tiên này 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 ngữ nghĩa khóa để sao lưu nhiều sự kiện đồng thời và người tiêu dùng

Thí 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

Sự 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ó

Phương pháp nào được sử dụng để thêm một phần tử vào hàng đợi?

Phương pháp nào được sử dụng để thêm giá trị vào cuối hàng đợi?