Python có cấu trúc dữ liệu hàng đợi không?
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 Show
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 PythonChúng ta có thể thực hiện các thao tác sau trong Queue
Các phương thức có sẵn trong hàng đợiPython 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
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ợpDanh 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 đợiTrong 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 đợiPython 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àngMô-đ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 dequeBộ 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 PythonHà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ôngChú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 PriorityQueueHà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ậnChú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ó Python có ngăn xếp và hàng đợi không?Ngăn xếp và Hàng đợi là cấu trúc dữ liệu sớm nhất được định nghĩa trong khoa học máy tính. Một danh sách Python đơn giản cũng có thể hoạt động như một hàng đợi và ngăn xếp . Hàng đợi tuân theo quy tắc FIFO (Vào trước ra trước) và được sử dụng trong lập trình để sắp xếp. Thông thường, ngăn xếp và hàng đợi được triển khai bằng một mảng hoặc danh sách liên kết.
Chúng ta có thể triển khai hàng đợi trong Python không?Hàng đợi trong Python có thể được triển khai theo các cách sau. danh sách . bộ sưu tập. deque .
Danh sách Python có phải là ngăn xếp hoặc hàng đợi không?Danh sách cấu trúc dữ liệu tích hợp sẵn của Python có thể được sử dụng làm ngăn xếp .
Cấu trúc dữ liệu nào được sử dụng trong Python?Danh sách, bộ và bộ là các cấu trúc dữ liệu cơ bản trong ngôn ngữ lập trình Python. |