Giới thiệu
Từ việc lưu trữ các số nguyên đơn giản đến quản lý quy trình công việc phức tạp, cấu trúc dữ liệu đặt nền tảng cho các ứng dụng mạnh mẽ. Trong số đó, hàng đợi thường nổi lên vừa hấp dẫn vừa có mặt khắp nơi. Hãy nghĩ về điều đó – một xếp hàng tại ngân hàng, chờ đến lượt tại quầy thức ăn nhanh hoặc xử lý các tác vụ trong hệ thống máy tính — tất cả các tình huống này đều cộng hưởng với cơ chế của hàng đợi.
Người đầu tiên xếp hàng sẽ được phục vụ trước và những người mới đến sẽ được phục vụ cuối cùng. Đây là một ví dụ thực tế về hoạt động của hàng đợi!
Đối với các nhà phát triển, đặc biệt là trong Python, hàng đợi không chỉ là cấu trúc lý thuyết trong sách giáo khoa khoa học máy tính. Chúng tạo thành kiến trúc cơ bản trong nhiều ứng dụng. Từ việc quản lý các tác vụ trong máy in đến đảm bảo luồng dữ liệu liền mạch trong các chương trình phát sóng trực tiếp, hàng đợi đóng một vai trò không thể thiếu.
Trong hướng dẫn này, chúng ta sẽ đi sâu vào khái niệm hàng đợi, khám phá các đặc điểm, ứng dụng trong thế giới thực của chúng và quan trọng nhất là cách triển khai và sử dụng chúng một cách hiệu quả trong Python.
Cấu trúc dữ liệu hàng đợi là gì?
Điều hướng qua bối cảnh cấu trúc dữ liệu, chúng ta thường gặp các vùng chứa có các quy tắc riêng biệt để nhập và truy xuất dữ liệu. Trong số này, hàng đợi nổi bật vì sự thanh lịch và đơn giản của nó.
Nguyên tắc FIFO
Về cốt lõi, hàng đợi là một cấu trúc dữ liệu tuyến tính tuân theo Nhập trước xuất trước (FIFO) nguyên tắc. Điều này có nghĩa là phần tử đầu tiên được thêm vào hàng đợi sẽ là phần tử đầu tiên bị xóa. Để so sánh nó với một tình huống có liên quan: hãy xem xét một hàng khách hàng tại quầy bán vé. Người đến trước nhận vé trước, những người đến sau sẽ xếp hàng cuối cùng để chờ đến lượt.
Lưu ý: Một hàng đợi có hai đầu – phía sau và phía trước. Mặt trước cho biết nơi các phần tử sẽ bị xóa và phía sau biểu thị nơi các phần tử mới sẽ được thêm vào.
Hoạt động hàng đợi cơ bản
-
xếp hàng – Hành động của thêm một phần tử ở cuối (đuôi) của hàng đợi.
-
xếp hàng – Hành động của loại bỏ một phần tử từ trước mặt của hàng đợi.
-
Peek hoặc Mặt trận – Trong nhiều trường hợp, sẽ có ích nếu chỉ quan sát phần tử phía trước mà không loại bỏ nó. Hoạt động này cho phép chúng tôi làm điều đó.
-
Không có sản phẩm nào – Một thao tác giúp xác định xem hàng đợi có phần tử nào không. Điều này có thể rất quan trọng trong các tình huống trong đó các hành động phụ thuộc vào hàng đợi có dữ liệu.
Lưu ý: Trong khi một số hàng đợi có kích thước giới hạn (hàng đợi bị giới hạn), những hàng đợi khác có khả năng phát triển miễn là bộ nhớ hệ thống cho phép (hàng đợi không bị giới hạn).
Sự đơn giản của hàng đợi và quy tắc hoạt động rõ ràng khiến chúng trở nên lý tưởng cho nhiều ứng dụng khác nhau trong phát triển phần mềm, đặc biệt là trong các tình huống yêu cầu xử lý có trật tự và có hệ thống.
Tuy nhiên, hiểu lý thuyết chỉ là bước đầu tiên. Khi tiếp tục, chúng ta sẽ đi sâu vào các khía cạnh thực tế, minh họa cách triển khai hàng đợi trong Python.
Cách triển khai hàng đợi trong Python – Mô-đun danh sách so với Deque và hàng đợi
Python, với thư viện tiêu chuẩn phong phú và cú pháp thân thiện với người dùng, cung cấp một số cơ chế để triển khai và làm việc với hàng đợi. Mặc dù tất cả đều phục vụ mục đích cơ bản của việc quản lý hàng đợi, nhưng chúng đều có những sắc thái, ưu điểm và những cạm bẫy tiềm ẩn. Hãy mổ xẻ từng phương pháp, minh họa cơ chế của nó và các trường hợp sử dụng tốt nhất.
Lưu ý: Luôn kiểm tra trạng thái hàng đợi của bạn trước khi thực hiện các thao tác. Ví dụ: trước khi xếp hàng đợi, hãy xác minh xem hàng đợi có trống hay không để tránh lỗi. Tương tự như vậy, đối với hàng đợi có giới hạn, hãy đảm bảo có khoảng trống trước khi xếp hàng.
Sử dụng danh sách Python để triển khai hàng đợi
Việc sử dụng danh sách tích hợp sẵn của Python để triển khai hàng đợi rất trực quan và đơn giản. Không cần thư viện bên ngoài hoặc cấu trúc dữ liệu phức tạp. Tuy nhiên, cách tiếp cận này có thể không hiệu quả đối với các tập dữ liệu lớn. Xóa một phần tử khỏi đầu danh sách (pop(0)) mất thời gian tuyến tính, điều này có thể gây ra vấn đề về hiệu suất.
Lưu ý: Đối với các ứng dụng yêu cầu hiệu suất cao hoặc những ứng dụng xử lý khối lượng dữ liệu đáng kể, hãy chuyển sang collections.deque cho độ phức tạp về thời gian không đổi cho cả việc xếp hàng và loại bỏ hàng đợi.
Hãy bắt đầu bằng cách tạo một danh sách đại diện cho hàng đợi của chúng ta:
queue = []
Quá trình thêm các phần tử vào cuối hàng đợi (enqueuing) không gì khác hơn là thêm chúng vào danh sách:
queue.append('A')
queue.append('B')
queue.append('C')
print(queue) Ngoài ra, việc xóa phần tử khỏi đầu hàng đợi (dequeuing) tương đương với việc chỉ xóa phần tử đầu tiên của danh sách:
queue.pop(0)
print(queue) Sử dụng Collection.deque để triển khai hàng đợi
Cách tiếp cận này có hiệu quả cao vì deque được thực hiện bằng cách sử dụng danh sách liên kết đôi. Nó hỗ trợ nối và bật O(1) nhanh từ cả hai đầu. Nhược điểm của phương pháp này là nó hơi ít trực quan hơn cho người mới bắt đầu.
Trước hết, chúng ta sẽ nhập deque đối tượng từ collections mô-đun và khởi tạo hàng đợi của chúng tôi:
from collections import deque queue = deque()
Bây giờ, chúng ta có thể sử dụng append() phương pháp liệt kê các phần tử và popleft() phương pháp loại bỏ các phần tử khỏi hàng đợi:
Xem hướng dẫn thực hành, thực tế của chúng tôi để học Git, với các phương pháp hay nhất, các tiêu chuẩn được ngành công nghiệp chấp nhận và bảng lừa đảo đi kèm. Dừng lệnh Googling Git và thực sự học nó!
queue.append('A')
queue.append('B')
queue.append('C')
print(queue) queue.popleft()
print(queue) Sử dụng Python hàng đợi Mô-đun triển khai hàng đợi
Sản phẩm queue mô-đun trong thư viện chuẩn của Python cung cấp một cách tiếp cận chuyên biệt hơn để quản lý hàng đợi, phục vụ cho nhiều trường hợp sử dụng khác nhau:
- Hàng đợi đơn giản – Hàng đợi FIFO cơ bản
- hàng đợi cuộc sống – Hàng đợi LIFO, về cơ bản là một ngăn xếp
- Hàng đợi ưu tiên – Các phần tử được sắp xếp lại dựa trên mức độ ưu tiên được chỉ định của chúng
Lưu ý: Lựa chọn cho queue mô-đun, được thiết kế để chỉ an toàn. Điều này đảm bảo rằng các hoạt động đồng thời trên hàng đợi không dẫn đến kết quả không thể đoán trước.
Cách tiếp cận này rất hay vì nó được thiết kế rõ ràng cho các hoạt động xếp hàng. Tuy nhiên, thành thật mà nói, nó có thể là quá mức cần thiết đối với các tình huống đơn giản.
Bây giờ chúng ta hãy bắt đầu sử dụng queue mô-đun bằng cách nhập nó vào dự án của chúng tôi:
import queue
Vì chúng ta đang triển khai một hàng đợi FIFO đơn giản nên chúng ta sẽ khởi tạo nó bằng cách sử dụng SimpleQueue() người xây dựng:
q = queue.SimpleQueue()
Các hoạt động Enqueue và dequeue được thực hiện bằng cách sử dụng put() và get() phương pháp từ queue mô-đun:
q.put('A')
q.put('B')
q.put('C')
print(q.queue) q.get()
print(q.queue) Lưu ý: Các hoạt động xếp hàng có thể đưa ra các ngoại lệ mà nếu không được xử lý có thể làm gián đoạn luồng ứng dụng của bạn. Để ngăn chặn điều đó, hãy gói các hoạt động hàng đợi của bạn vào try-except khối.
Ví dụ, xử lý các queue.Empty ngoại lệ khi làm việc với queue mô-đun:
import queue q = queue.SimpleQueue() try: item = q.get_nowait()
except queue.Empty: print("Queue is empty!")
Lựa chọn triển khai nào?
Lựa chọn triển khai hàng đợi trong Python của bạn phải phù hợp với yêu cầu của ứng dụng. Nếu bạn đang xử lý một lượng lớn dữ liệu hoặc yêu cầu hiệu suất được tối ưu hóa, collections.deque là một lựa chọn hấp dẫn. Tuy nhiên, đối với các ứng dụng đa luồng hoặc khi có sự ưu tiên, queue module cung cấp các giải pháp mạnh mẽ. Đối với các tập lệnh nhanh hoặc khi bạn mới bắt đầu, danh sách Python có thể là đủ, nhưng hãy luôn cảnh giác với những cạm bẫy tiềm ẩn về hiệu suất.
Lưu ý: Phát minh lại bánh xe bằng các hoạt động hàng đợi triển khai tùy chỉnh khi Python đã cung cấp các giải pháp tích hợp mạnh mẽ.
Trước khi tạo các giải pháp tùy chỉnh, hãy tự làm quen với các dịch vụ dựng sẵn của Python như deque và queue mô-đun. Thông thường, chúng đáp ứng nhiều yêu cầu khác nhau, tiết kiệm thời gian và giảm thiểu các lỗi tiềm ẩn.
Tìm hiểu sâu hơn: Các khái niệm hàng đợi nâng cao trong Python
Đối với những người đã nắm bắt được cơ chế cơ bản của hàng đợi và muốn tìm hiểu sâu hơn, Python cung cấp rất nhiều khái niệm và kỹ thuật nâng cao để tinh chỉnh và tối ưu hóa các hoạt động dựa trên hàng đợi. Hãy khám phá một số khía cạnh phức tạp này, cung cấp cho bạn một kho công cụ để giải quyết các tình huống phức tạp hơn.
Hàng đợi hai đầu với deque
Mặc dù trước đây chúng tôi đã khám phá deque dưới dạng hàng đợi FIFO, nó cũng hỗ trợ các hoạt động LIFO (Vào trước ra trước). Nó cho phép bạn nối thêm hoặc bật các phần tử từ cả hai đầu với độ phức tạp O(1):
from collections import deque dq = deque()
dq.appendleft('A') dq.append('B') dq.pop() dq.popleft() Hàng đợi ưu tiên trong hành động
Việc sử dụng hàng đợi FIFO đơn giản khi thứ tự xử lý phụ thuộc vào mức độ ưu tiên có thể dẫn đến sự thiếu hiệu quả hoặc kết quả không mong muốn, vì vậy, nếu ứng dụng của bạn yêu cầu các phần tử nhất định phải được xử lý trước các phần tử khác dựa trên một số tiêu chí, hãy sử dụng một hàng đợi FIFO đơn giản. PriorityQueue. Điều này đảm bảo các phần tử được xử lý dựa trên mức độ ưu tiên đã đặt của chúng.
Hãy xem cách chúng tôi đặt mức độ ưu tiên cho các thành phần mà chúng tôi đang thêm vào hàng đợi. Điều này yêu cầu chúng ta chuyển một bộ dữ liệu làm đối số của put() phương pháp. Bộ dữ liệu phải chứa mức độ ưu tiên làm phần tử đầu tiên và giá trị thực tế là phần tử thứ hai:
import queue pq = queue.PriorityQueue()
pq.put((2, "Task B"))
pq.put((1, "Task A")) pq.put((3, "Task C")) while not pq.empty(): _, task = pq.get() print(f"Processing: {task}")
Điều này sẽ cung cấp cho chúng tôi những điều sau đây:
Processing: Task A
Processing: Task B
Processing: Task C
Lưu ý cách chúng tôi thêm các phần tử theo thứ tự khác với thứ được lưu trong hàng đợi. Đó là vì những ưu tiên mà chúng tôi đã chỉ định trong put() phương pháp khi thêm các phần tử vào hàng đợi ưu tiên.
Thực hiện hàng đợi tròn
Hàng đợi vòng (hoặc bộ đệm vòng) là cấu trúc dữ liệu nâng cao trong đó phần tử cuối cùng được kết nối với phần tử đầu tiên, đảm bảo luồng tuần hoàn. deque có thể bắt chước hành vi này bằng cách sử dụng maxlen bất động sản:
from collections import deque circular_queue = deque(maxlen=3)
circular_queue.append(1)
circular_queue.append(2)
circular_queue.append(3) circular_queue.append(4)
print(circular_queue) Kết luận
Hàng đợi, cơ bản nhưng mạnh mẽ, tìm thấy bản chất của chúng trong nhiều ứng dụng trong thế giới thực và các vấn đề tính toán. Từ lập lịch tác vụ trong hệ điều hành đến quản lý luồng dữ liệu trong bộ đệm in hoặc yêu cầu máy chủ web, ý nghĩa của hàng đợi là rất sâu rộng.
Python mang đến một bảng công cụ và thư viện phong phú để làm việc với hàng đợi. Từ hàng đợi dựa trên danh sách đơn giản cho các tập lệnh nhanh đến hiệu quả cao deque đối với các ứng dụng quan trọng về hiệu năng, ngôn ngữ này thực sự đáp ứng được nhiều nhu cầu.
- Phân phối nội dung và PR được hỗ trợ bởi SEO. Được khuếch đại ngay hôm nay.
- PlatoData.Network Vertical Generative Ai. Trao quyền cho chính mình. Truy cập Tại đây.
- PlatoAiStream. Thông minh Web3. Kiến thức khuếch đại. Truy cập Tại đây.
- Trung tâmESG. Than đá, công nghệ sạch, Năng lượng, Môi trường Hệ mặt trời, Quản lý chất thải. Truy cập Tại đây.
- PlatoSức khỏe. Tình báo thử nghiệm lâm sàng và công nghệ sinh học. Truy cập Tại đây.
- nguồn: https://stackabuse.com/guide-to-queues-in-python/
