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/
- : có
- :là
- :không phải
- :Ở đâu
- $ LÊN
- 1
- 11
- 13
- 17
- 20
- 7
- 8
- 9
- a
- Giới thiệu
- về nó
- Hành động
- hành động
- thực tế
- thực sự
- thêm
- thêm
- tiên tiến
- lợi thế
- trước
- Cảnh báo
- sắp xếp
- Tất cả
- cho phép
- Đã
- Ngoài ra
- luôn luôn
- trong số
- an
- và
- bất kì
- Các Ứng Dụng
- các ứng dụng
- phương pháp tiếp cận
- kiến trúc
- LÀ
- đối số
- Đến
- Arsenal
- AS
- các khía cạnh
- giao
- At
- tránh
- dựa
- cơ bản
- BE
- bởi vì
- trước
- Người mới bắt đầu
- Bắt đầu
- hành vi
- mang lại lợi ích
- BEST
- Khối
- biên giới
- cả hai
- Mang lại
- đệm
- được xây dựng trong
- nhưng
- by
- CAN
- trường hợp
- phục vụ
- phục vụ
- Nguyên nhân
- nhất định
- đặc điểm
- kiểm tra
- sự lựa chọn
- Chọn
- trong sáng
- bộ sưu tập
- Đến
- thuyết phục
- phức tạp
- phức tạp
- tính toán
- máy tính
- Khoa học Máy tính
- khái niệm
- khái niệm
- phần kết luận
- đồng thời
- kết nối
- Hãy xem xét
- không thay đổi
- chứa
- Container
- Trung tâm
- Counter
- Tạo
- tiêu chuẩn
- quan trọng
- khách hàng
- khách hàng
- dữ liệu
- nhập dữ liệu
- Cấu trúc dữ liệu
- bộ dữ liệu
- xử lý
- sâu
- sâu sắc hơn
- đào sâu
- yêu cầu
- phụ thuộc
- thiết kế
- Xác định
- phát triển
- Phát triển
- khác nhau
- Làm gián đoạn
- khác biệt
- do
- nhược điểm
- mỗi
- hăng hái
- hiệu quả
- hiệu quả
- thành phần
- các yếu tố
- nổi lên
- cuối
- kết thúc
- đảm bảo
- đảm bảo
- đảm bảo
- nhập
- Tương đương
- lỗi
- đặc biệt
- bản chất
- chủ yếu
- ví dụ
- ngoại lệ
- rõ ràng
- Khám phá
- Khám phá
- ngoài
- làm quen
- sâu rộng
- NHANH
- Tìm kiếm
- Tên
- dòng chảy
- Tập trung
- tiếp theo
- Trong
- hình thức
- từ
- trước mặt
- đầy đủ
- cơ bản
- đi
- Cho
- Cho
- tuyệt vời
- nền tảng
- Phát triển
- hướng dẫn
- xử lý
- Xử lý
- hands-on
- Có
- có
- giúp
- Cao
- cao
- trung thực
- di chuột
- Độ đáng tin của
- Hướng dẫn
- Tuy nhiên
- HTTPS
- ICON
- lý tưởng
- if
- minh họa
- thực hiện
- thực hiện
- thực hiện
- thực hiện
- hàm ý
- nhập khẩu
- quan trọng
- nhập khẩu
- in
- bao gồm
- chỉ
- không hiệu quả
- ví dụ
- trong
- intriguing
- Giới thiệu
- trực quan
- các vấn đề
- IT
- ITS
- tham gia
- chỉ
- cảnh quan
- Ngôn ngữ
- lớn
- Họ
- nằm xuống
- dẫn
- học tập
- ít
- cho phép
- LG
- thư viện
- Thư viện
- Lượt thích
- Hạn chế
- Dòng
- Danh sách
- Chức năng
- sống
- ll
- dài
- Xem
- làm cho
- quản lý
- quản lý
- nhiều
- có nghĩa
- cơ khí
- cơ chế
- Bộ nhớ
- phương pháp
- phương pháp
- Might
- Mô-đun
- chi tiết
- hầu hết
- di chuyển
- Cần
- nhu cầu
- Mới
- Không
- không
- che
- vật
- tuân theo
- of
- Cung cấp
- Cung cấp
- thường
- on
- ONE
- hoạt động
- các hệ điều hành
- hoạt động
- Hoạt động
- Tối ưu hóa
- tối ưu hóa
- or
- gọi món
- Nền tảng khác
- Khác
- vfoXNUMXfipXNUMXhfpiXNUMXufhpiXNUMXuf
- ra
- kết quả
- palette
- vượt qua
- hiệu suất
- biểu diễn
- người
- plato
- Thông tin dữ liệu Plato
- PlatoDữ liệu
- Play
- quá nhiều
- bật
- Rất tiếc
- tiềm năng
- có khả năng
- mạnh mẽ
- Thực tế
- ngăn chặn
- trước đây
- nguyên tắc
- In
- ưu tiên
- vấn đề
- quá trình
- Xử lý
- xử lý
- dự án
- tài sản
- cung cấp
- mục đích
- Python
- Nhanh chóng
- nâng cao
- phạm vi
- RE
- thế giới thực
- giảm
- lọc
- Đã loại bỏ
- loại bỏ
- đại diện
- yêu cầu
- yêu cầu
- Yêu cầu
- đòi hỏi
- tiếng kêu vang
- Giàu
- Nhẫn
- mạnh mẽ
- Vai trò
- quy tắc
- s
- tiết kiệm
- kịch bản
- kịch bản
- lập kế hoạch
- Khoa học
- kịch bản
- liền mạch
- Thứ hai
- phục vụ
- phục vụ
- máy chủ
- định
- một số
- Bóng tối
- tấm
- nên
- có ý nghĩa
- biểu thị
- Đơn giản
- đơn giản
- tình huống
- Kích thước máy
- So
- Phần mềm
- phát triển phần mềm
- Giải pháp
- một số
- tinh vi
- Không gian
- chuyên nghành
- quang phổ
- xếp chồng lên nhau
- Tiêu chuẩn
- tiêu chuẩn
- đứng
- Bắt đầu
- Bắt đầu
- Trạng thái
- Bước
- Dừng
- lưu trữ
- lưu trữ
- đơn giản
- dòng
- cấu trúc
- cấu trúc
- tiếp theo
- Hỗ trợ
- SVG
- Công tắc điện
- cú pháp
- hệ thống
- hệ thống
- bàn
- giải quyết
- mất
- Nhiệm vụ
- nhiệm vụ
- kỹ thuật
- sách giáo khoa
- hơn
- việc này
- Sản phẩm
- Phong cảnh
- cung cấp their dịch
- Them
- lý thuyết
- lý thuyết
- Đó
- Kia là
- họ
- nghĩ
- điều này
- những
- Thông qua
- vé
- thời gian
- đến
- công cụ
- quá trình chuyển đổi
- đúng
- thực sự
- XOAY
- hai
- phổ cập
- khám phá
- cơ bản
- sự hiểu biết
- không thể đoán trước
- us
- sử dụng
- sử dụng
- sử dụng
- giá trị
- nhiều
- khác nhau
- Ve
- xác minh
- khối lượng
- vs
- Đợi
- we
- web
- máy chủ web
- Điều gì
- Là gì
- Wheel
- khi nào
- cái nào
- trong khi
- CHÚNG TÔI LÀ
- rộng
- Phạm vi rộng
- sẽ
- với
- không có
- Công việc
- Luồng công việc
- đang làm việc
- bọc
- nhưng
- Bạn
- trên màn hình
- mình
- zephyrnet