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 dựng sẵn và triển khai nó bằng mã Python.
Các bài viết liên quan:
Queue là gì?
Queue là một loại 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ề Queue dựa trên FIFO, có nghĩa là “Nhập trước xuất trước”. Nó còn được gọi là “đến trước thoát trước”. Queue 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à được gỡ bỏ 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ọ; máy in sẽ in tác vụ đầu tiên và tác vụ thứ hai, v.v. 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ý Queue để xử lý các quy trình khác nhau trong máy tính.
Operations trong Python
Chúng ta có thể thực hiện các Operations sau trong Queue.
Enqueue – Enqueue là một hoạt động trong đó chúng tôi thêm các mục vào Queue. Nếu Queue đầy, đó là điều kiện của Queue. Độ 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 Queue. Một phần tử được loại bỏ theo thứ tự như khi nó được chèn vào. Nếu Queue trống, đó là một điều kiện của Dòng dưới Queue. Độ phức tạp thời gian của dequeue là O(1).
Front – Một phần tử được chèn vào giao diện người dùng. Độ phức tạp thời gian của phía trước là O(1).
Rear – 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 Queue
Python cung cấp các phương thức sau, thường được sử dụng để thực hiện Operations trong Queue.
- put(item) – Chức năng này được sử dụng để chèn phần tử vào Queue.
- get() – Hàm này được sử dụng để trích xuất phần tử từ Queue.
- empty() – Hàm này được sử dụng để kiểm tra xem Queue có trống hay không. Nó trả về true nếu Queue trống.
- qsize – Hàm này trả về độ dài của Queue.
- full() – Nếu Queue đầy trả về true; nếu không thì sai.
Chúng ta sẽ tìm hiểu các chức năng này trong các phần dưới đây.
List Python tích hợp
List có thể được sử dụng làm Queue, 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ử. Các List khá chậm vì nếu chúng ta chèn một phần tử mới vào List, tất cả các phần tử sẽ yêu cầu dịch chuyển từng phần tử. Phải mất O(n) thời gian. Vì vậy, List được khuyến nghị thay cho Queue. Hãy hiểu ví dụ sau về cách List có thể được sử dụng làm Queue.
Ví dụ:
que = []
que.append('queue1')
que.append('queue2')
que.append('queue3')
print(que)
# list chậm hơn
print(que.pop(0)) Chúng tôi đã xác định List 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 List.
Thêm phần tử vào Queue (Enqueue)
Chúng ta có thể thêm phần tử from vào đuôi xe. Quá trình này còn được gọi là enqueue. Chúng tôi tạo một lớp Queue 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 đây.
Ví dụ:
class Queue:
def __init__(self):
self.queue = list()
def add_element(self,val):
# phương thêm element
if val not in self.queue:
self.queue.insert(0,val)
return True
return False
def size(self):
return len(self.queue)
TheQueue = Queue()
TheQueue.add_element("class Queue:
def __init__(self):
self.queue = list()
def add_element(self,val):
# chèn element
if val not in self.queue:
self.queue.insert(0,val)
return True
return False
def size(self):
return len(self.queue)
TheQueue = Queue()
TheQueue.add_element("queue1")
TheQueue.add_element("queue2")
TheQueue.add_element("queue3")
TheQueue.add_element("queue4")
print("độ lớn Queue: ",TheQueue.size()) ")
TheQueue.add_element("queue5")
TheQueue.add_element("queue6")
TheQueue.add_element("queue7")
print("độ lớn Queue: ",TheQueue.size()) Xóa phần tử khỏi Queue (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 List.
Ví dụ:
class Queue:
def __init__(self):
self.queue = list()
def add_element(self,val):
# chèm thêm element
if val not in self.queue:
self.queue.insert(0,val)
return True
return False
# Pop element ra khỏi queue
def remove_element(self):
if len(self.queue)>0:
return self.queue.pop()
return ("Queue is Empty")
que = Queue()
que.add_element("Queue1")
que.add_element("Queue2")
que.add_element("Queue3")
que.add_element("Queue4")
print(que)
print(que.remove_element())
print(que.remove_element())
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 List cho biến Queue. 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 tôi 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 một hàng không bị tràn. Nếu nó trả về false, thì hãy loại bỏ từng phần tử một.
Sắp xếp Queue
Trong ví dụ sau, chúng tôi đã sắp xếp các phần tử của Queue.
Ví dụ –
import queue
q = queue.Queue()
q.put(14)
q.put(27)
q.put(11)
q.put(4)
q.put(1)
# Ở đây, chúng tôi sử dụng thuật toán sắp xếp bong bóng để sắp xếp
n = q.qsize()
for i in range(n):
# Xóa phần tử
x = q.get()
for j in range(n-1):
# Xóa phần tử
y = q.get()
if x > y :
# đặt phần tử nhỏ hơn ở đầu hàng đợi
q.put(y)
else:
# cái nhỏ hơn được đặt ở đầu hàng đợi
q.put(x)
x = y # Phần tử lớn hơn thay bằng x và kiểm tra lại
q.put(x)
while (q.empty() == False):
print(q.queue[0], end = " ")
q.get()
Mô-đun Queue
Python cung cấp mô-đun Queue để triển khai Queue nhiều nhà sản xuất, nhiều người tiêu dùng. Mô-đun Queue cung cấp lớp Queue đượ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 bắt buộc.
Chúng ta có thể thực hiện tất cả các Operations bằng cách sử dụng lớp Queue dựng sẵn.
Làm việc với lớp queue.Queue
Mô-đun Queue 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ề Queue. Lớp xếp hàng0uii
Ví dụ:
from queue import Queue
que = Queue()
que.put('queue1')
que.put('queue2')
que.put('queue3')
print(que)
print(que.get())
print(que.get())
print(que.get())
print(que.get_nowait())
print(que.get())
Làm việc với lớp collection.deque
Lớp collection.deque được sử dụng để triển khai Queue 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ả Queue 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ả.
collection.deque có thể là một lựa chọn tốt cho cấu trúc dữ liệu Queue trong thư viện chuẩn của Python.
Ví dụ:
from collections import deque
que = deque()
que.append('queue1')
que.append('queue2')
que.append('queue3')
print(que)
deque(['queue1 ', 'queue2', 'queue3'])
print(que.popleft())
print(que.popleft())
print(que.popleft())
que.popleft()
Lớp multiprocessing.Queue
Lớp multiprocessing.Queue được sử dụng để triển khai các mục được xếp Queue để xử lý song song bởi các công nhân đa dòng. multiprocessing.Queue 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 đây.
Ví dụ:
from multiprocessing import Queue
que = Queue()
que.put('queue1')
que.put('queue2')
que.put('queue3')
print(que)
print(que.get())
print(que.get())
print(que.get())
Queue ưu tiên trong Python
Queue ưu tiên là một loại Queue đặ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ư Queue thông thường, nó truy xuất 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.
Queue ư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 cá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ề Queue ưu tiên – Nó thực thi các tác vụ có mức độ ưu tiên cao hơn 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 Queue ưu tiên trong Python. Hãy hiểu những cách sau đây.
List được sắp xếp thủ công
Chúng ta có thể sử dụng List Python được sắp xếp làm Queue ư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 các Operations O(n).
Do đó, List được sắp xếp có thể hiệu quả khi sẽ có ít lần chèn vào Queue ưu tiên.
Hãy hiểu ví dụ sau –
Ví dụ:
pri_que = []
pri_que.append((2, 'queue1'))
pri_que.append((1, 'queue2'))
pri_que.append((3, 'queue3'))
# LƯU Ý: Hãy nhớ sắp xếp lại mỗi lần
# một phần tử mới được chèn vào.
pri_que.sort(reverse=True)
while pri_que:
next_item = pri_que.pop()
print(next_item)
Lớp queue.PriorityQueue
Việc triển khai Queue ư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à Queue ư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ụ –
from queue import PriorityQueue
q = PriorityQueue()
q.put((2, 'queue1'))
q.put((1, 'queue2'))
q.put((3, 'queue3'))
while not q.empty():
next_item = q.get()
print(next_item)
Chúng ta có thể chọn bất kỳ triển khai Queue ưu tiên nào trong chương trình Python nhưng hãy nhớ rằng queue.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ề Queue và cách triển khai nó. Nó tương tự như List 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 Queue ưu tiên và các cách thực hiện khác nhau của nó.
