Wprowadzenie
Struktury danych stanowią podstawę niezawodnych aplikacji, od przechowywania prostych liczb całkowitych po zarządzanie złożonymi przepływami pracy. Wśród nich kolejka często okazuje się zarówno intrygujące, jak i wszechobecne. Pomyśl o tym – A kolejka w banku, czekanie na swoją kolej w barze fast food czy buforowanie zadań w systemie komputerowym – wszystkie te scenariusze odwołują się do mechaniki kolejki.
Pierwsza osoba w kolejce zostaje obsłużona jako pierwsza, a nowi dołączają na końcu. To prawdziwy przykład kolejki w akcji!
Dla programistów, szczególnie w Pythonie, kolejki nie są jedynie konstruktami teoretycznymi z podręcznika informatyki. Tworzą podstawową architekturę w wielu zastosowaniach. Od zarządzania zadaniami na drukarce po zapewnienie bezproblemowego przesyłania strumieni danych w transmisjach na żywo – kolejki odgrywają niezastąpioną rolę.
W tym przewodniku zagłębimy się w koncepcję kolejek, badając ich charakterystykę, zastosowania w świecie rzeczywistym i, co najważniejsze, jak skutecznie je wdrożyć i używać w Pythonie.
Co to jest struktura danych kolejki?
Poruszając się po krajobrazie struktur danych, często natrafiamy na kontenery, które mają odrębne zasady wprowadzania i wyszukiwania danych. Wśród nich kolejka wyróżnia się elegancją i prostotą.
Zasada FIFO
W swej istocie kolejka jest liniową strukturą danych, która przylega do Pierwsze weszło, pierwsze wyszło (FIFO) zasada. Oznacza to, że pierwszy element dodany do kolejki będzie pierwszym, który zostanie usunięty. Aby porównać to do możliwego scenariusza: rozważ kolejkę klientów przy kasie biletowej. Osoba, która pojawi się jako pierwsza, otrzyma swój bilet, a kolejni, którzy przyjdą, ustawiają się na końcu i czekają na swoją kolej.
Uwaga: Kolejka ma dwa końce – tył i przód. Przód wskazuje, skąd elementy zostaną usunięte, a tył oznacza, gdzie zostaną dodane nowe elementy.
Podstawowe operacje na kolejce
-
Kolejka – Akt dodanie element na końcu (tył) z kolejki.
-
Usuń z kolejki – Akt usuwanie element z z przodu z kolejki.
-
Zerknij lub z przodu – W wielu sytuacjach warto po prostu obserwować przednią soczewkę, bez jej demontażu. Ta operacja pozwala nam właśnie to zrobić.
-
Jest pusty – Operacja pomagająca określić, czy kolejka zawiera jakieś elementy. Może to mieć kluczowe znaczenie w scenariuszach, w których działania zależą od kolejki zawierającej dane.
Uwaga: Podczas gdy niektóre kolejki mają ograniczony rozmiar (kolejki ograniczone), inne mogą potencjalnie rosnąć tak długo, jak pozwala na to pamięć systemowa (kolejki nieograniczone).
Prostota kolejek i ich jasne zasady działania sprawiają, że idealnie nadają się do różnorodnych zastosowań w tworzeniu oprogramowania, szczególnie w scenariuszach wymagających uporządkowanego i systematycznego przetwarzania.
Jednak zrozumienie teorii to dopiero pierwszy krok. W dalszej części zajmiemy się aspektami praktycznymi, ilustrując sposób implementacji kolejek w Pythonie.
Jak zaimplementować kolejki w Pythonie – listy vs. Deque vs. moduł kolejki
Python, ze swoją bogatą biblioteką standardową i przyjazną dla użytkownika składnią, zapewnia kilka mechanizmów implementacji i pracy z kolejkami. Chociaż wszystkie służą podstawowemu celowi, jakim jest zarządzanie kolejkami, mają swoje niuanse, zalety i potencjalne pułapki. Przeanalizujmy każde podejście, ilustrując jego mechanikę i najlepsze przypadki użycia.
Uwaga: Zawsze sprawdzaj status swojej kolejki przed wykonaniem operacji. Na przykład przed usunięciem z kolejki sprawdź, czy kolejka jest pusta, aby uniknąć błędów. Podobnie w przypadku kolejek ograniczonych przed umieszczeniem w kolejce upewnij się, że jest wolne miejsce.
Używanie list Pythona do implementowania kolejek
Używanie wbudowanych list Pythona do implementowania kolejek jest intuicyjne i proste. Nie ma potrzeby stosowania zewnętrznych bibliotek ani skomplikowanych struktur danych. Jednak to podejście może nie być skuteczne w przypadku dużych zbiorów danych. Usuwanie elementu z początku listy (pop(0)
) zajmuje czas liniowy, co może powodować problemy z wydajnością.
Uwaga: W przypadku aplikacji wymagających dużej wydajności lub obsługujących znaczną ilość danych, przełącz się na collections.deque
dla stałej złożoności czasowej zarówno przy kolejkowaniu, jak i usuwaniu z kolejki.
Zacznijmy od stworzenia listy reprezentującej naszą kolejkę:
queue = []
Proces dodawania elementów na koniec kolejki (kolejkowania) to nic innego jak dołączanie ich do listy:
queue.append('A')
queue.append('B')
queue.append('C')
print(queue)
Ponadto usunięcie elementu z początku kolejki (usunięcie z kolejki) jest równoznaczne z usunięciem pierwszego elementu listy:
queue.pop(0)
print(queue)
Korzystanie z kolekcje.deque do implementacji kolejek
To podejście jest bardzo skuteczne, ponieważ deque
jest realizowany za pomocą a lista podwójnie połączona. Obsługuje szybkie dołączanie i wyskakiwanie O(1) z obu końców. Wadą tego podejścia jest to, że tak jest nieco mniej intuicyjny dla początkujących.
Przede wszystkim zaimportujemy plik deque
obiekt z collections
module i zainicjuj naszą kolejkę:
from collections import deque queue = deque()
Teraz możemy użyć append()
metoda kolejkowania elementów i popleft()
metoda usuwania elementów z kolejki:
Zapoznaj się z naszym praktycznym, praktycznym przewodnikiem dotyczącym nauki Git, zawierającym najlepsze praktyki, standardy przyjęte w branży i dołączoną ściągawkę. Zatrzymaj polecenia Google Git, a właściwie uczyć się to!
queue.append('A')
queue.append('B')
queue.append('C')
print(queue) queue.popleft()
print(queue)
Korzystanie z Pythona kolejka Moduł do implementacji kolejek
Połączenia queue
moduł w standardowej bibliotece Pythona zapewnia bardziej wyspecjalizowane podejście do zarządzania kolejkami, obsługując różne przypadki użycia:
- Prosta kolejka – Podstawowa kolejka FIFO
- Kolejka Życia – Kolejka LIFO, zasadniczo stos
- Kolejka priorytetowa – Elementy są usuwane z kolejki na podstawie przypisanego im priorytetu
Uwaga: Zdecyduj się na queue
moduł, który ma być bezpieczny dla wątków. Dzięki temu współbieżne operacje w kolejce nie prowadzą do nieprzewidywalnych wyników.
To podejście jest świetne, ponieważ zostało specjalnie zaprojektowane do operacji w kolejkach. Ale szczerze mówiąc, w przypadku prostych scenariuszy może to być przesada.
Teraz zacznijmy używać queue
moduł, importując go do naszego projektu:
import queue
Ponieważ implementujemy prostą kolejkę FIFO, zainicjujemy ją za pomocą SimpleQueue()
konstruktor:
q = queue.SimpleQueue()
Operacje umieszczania i usuwania z kolejki są implementowane przy użyciu put()
i get()
metody z queue
moduł:
q.put('A')
q.put('B')
q.put('C')
print(q.queue) q.get()
print(q.queue)
Uwaga: Operacje kolejkowe mogą powodować wyjątki, które, jeśli nie zostaną obsłużone, mogą zakłócić przepływ aplikacji. Aby temu zapobiec, zawiń operacje w kolejce try-except
Bloki.
Na przykład zajmij się queue.Empty
wyjątek podczas pracy z queue
moduł:
import queue q = queue.SimpleQueue() try: item = q.get_nowait()
except queue.Empty: print("Queue is empty!")
Które wdrożenie wybrać?
Twój wybór implementacji kolejki w Pythonie powinien być zgodny z wymaganiami Twojej aplikacji. Jeśli przetwarzasz dużą ilość danych lub potrzebujesz zoptymalizowanej wydajności, collections.deque
to przekonujący wybór. Jednak w przypadku aplikacji wielowątkowych lub gdy w grę wchodzą priorytety, plik queue
moduł oferuje solidne rozwiązania. W przypadku szybkich skryptów lub gdy dopiero zaczynasz, listy Pythona mogą wystarczyć, ale zawsze uważaj na potencjalne pułapki wydajności.
Uwaga: Wynalezienie koła na nowo poprzez niestandardowe wdrożenie operacji kolejkowych, gdy Python zapewnia już zaawansowane wbudowane rozwiązania.
Zanim zaczniesz tworzyć niestandardowe rozwiązania, zapoznaj się z wbudowanymi ofertami Pythona, takimi jak deque
oraz queue
moduł. Najczęściej spełniają szeroki zakres wymagań, oszczędzając czas i redukując potencjalne błędy.
Zanurz się głębiej: zaawansowane koncepcje kolejek w Pythonie
Tym, którzy zrozumieli podstawową mechanikę kolejek i chcą zagłębić się w nią, Python oferuje mnóstwo zaawansowanych koncepcji i technik pozwalających udoskonalić i zoptymalizować operacje oparte na kolejkach. Odkryjmy niektóre z tych wyrafinowanych aspektów, dając Ci arsenał narzędzi do radzenia sobie z bardziej złożonymi scenariuszami.
Kolejki dwustronne z dlatego
Chociaż już wcześniej badaliśmy deque
jako kolejka FIFO obsługuje także operacje LIFO (Last-In-First-Out). Umożliwia dołączanie lub umieszczanie elementów z obu końców ze złożonością O(1):
from collections import deque dq = deque()
dq.appendleft('A') dq.append('B') dq.pop() dq.popleft()
Kolejka priorytetowa w akcji
Używanie prostej kolejki FIFO, gdy kolejność przetwarzania zależy od priorytetu, może prowadzić do nieefektywności lub niepożądanych wyników, więc jeśli Twoja aplikacja wymaga, aby pewne elementy zostały przetworzone przed innymi w oparciu o pewne kryteria, zastosuj PriorityQueue
. Dzięki temu elementy są przetwarzane w oparciu o ustalone priorytety.
Przyjrzyj się jak ustalamy priorytety dla elementów, które dodajemy do kolejki. Wymaga to przekazania krotki jako argumentu metody put()
metoda. Krotka powinna zawierać priorytet jako pierwszy element i rzeczywistą wartość jako drugi element:
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}")
To da nam następujące:
Processing: Task A
Processing: Task B
Processing: Task C
Zwróć uwagę, jak dodaliśmy elementy w innej kolejności niż ta, która jest przechowywana w kolejce. Dzieje się tak ze względu na priorytety, które przypisaliśmy w pliku put()
metoda dodawania elementów do kolejki priorytetowej.
Implementacja kolejki cyklicznej
Kolejka cykliczna (lub bufor pierścieniowy) to zaawansowana struktura danych, w której ostatni element jest połączony z pierwszym, zapewniając przepływ cykliczny. deque
może naśladować to zachowanie, używając swojego maxlen
własność:
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)
Wnioski
Kolejki, podstawowe, ale potężne, znajdują swoją istotę w różnorodnych zastosowaniach w świecie rzeczywistym i problemach obliczeniowych. Od planowania zadań w systemach operacyjnych po zarządzanie przepływem danych w buforach wydruku lub żądaniach serwera WWW – konsekwencje kolejek są dalekosiężne.
Python udostępnia bogatą paletę narzędzi i bibliotek do pracy z kolejkami. Od prostych kolejek opartych na listach dla szybkich skryptów po wysoce wydajne deque
w przypadku zastosowań, w których wydajność jest krytyczna, język ten naprawdę zaspokaja spektrum potrzeb.
- Dystrybucja treści i PR oparta na SEO. Uzyskaj wzmocnienie już dziś.
- PlatoData.Network Pionowe generatywne AI. Wzmocnij się. Dostęp tutaj.
- PlatoAiStream. Inteligencja Web3. Wiedza wzmocniona. Dostęp tutaj.
- PlatonESG. Węgiel Czysta technologia, Energia, Środowisko, Słoneczny, Gospodarowanie odpadami. Dostęp tutaj.
- Platon Zdrowie. Inteligencja w zakresie biotechnologii i badań klinicznych. Dostęp tutaj.
- Źródło: https://stackabuse.com/guide-to-queues-in-python/
- :ma
- :Jest
- :nie
- :Gdzie
- $W GÓRĘ
- 1
- 11
- 13
- 17
- 20
- 7
- 8
- 9
- a
- O nas
- o tym
- działać
- działania
- rzeczywisty
- faktycznie
- w dodatku
- dodanie
- zaawansowany
- Zalety
- przed
- Alarm
- wyrównać
- Wszystkie kategorie
- pozwala
- już
- również
- zawsze
- wśród
- an
- i
- każdy
- Zastosowanie
- aplikacje
- podejście
- architektura
- SĄ
- argument
- Przybywa
- Arsenał
- AS
- aspekty
- przydzielony
- At
- uniknąć
- na podstawie
- podstawowy
- BE
- bo
- zanim
- początkujących
- Początek
- zachowanie
- korzystny
- BEST
- Bloki
- granica
- obie
- Przynosi
- bufor
- wbudowany
- ale
- by
- CAN
- Etui
- zaopatrywać
- caters
- Spowodować
- pewien
- Charakterystyka
- ZOBACZ
- wybór
- Dodaj
- jasny
- kolekcje
- jak
- zniewalający
- kompleks
- kompleksowość
- obliczeniowy
- komputer
- Computer Science
- pojęcie
- Koncepcje
- konkluzja
- równoległy
- połączony
- Rozważać
- stały
- zawierać
- Pojemniki
- rdzeń
- Przeciwdziałać
- Tworzenie
- Kryteria
- istotny
- zwyczaj
- Klientów
- dane
- wprowadzanie danych
- Struktura danych
- zbiory danych
- czynienia
- głęboko
- głębiej
- sięgać
- wymagający
- zależny
- zaprojektowany
- Ustalać
- deweloperzy
- oprogramowania
- różne
- Zakłócać
- odrębny
- do
- minusem
- każdy
- chętny
- faktycznie
- wydajny
- element
- Elementy
- wyłania się
- zakończenia
- kończy się
- zapewnić
- zapewnia
- zapewnienie
- wejście
- Równoważny
- Błędy
- szczególnie
- istota
- istotnie
- przykład
- wyjątek
- wyraźnie
- zbadane
- Exploring
- zewnętrzny
- oswajać
- dalekosiężny
- FAST
- Znajdź
- i terminów, a
- pływ
- Skupiać
- następujący
- W razie zamówieenia projektu
- Nasz formularz
- od
- z przodu
- w pełni
- fundamentalny
- git
- Dać
- Dający
- wspaniały
- podkład
- Rosnąć
- poprowadzi
- uchwyt
- Prowadzenie
- hands-on
- Have
- mający
- pomaga
- Wysoki
- wysoko
- uczciwy
- unosić
- W jaki sposób
- How To
- Jednak
- HTTPS
- ICON
- idealny
- if
- ilustrujące
- wdrożenia
- realizacja
- realizowane
- wykonawczych
- implikacje
- importować
- co ważne
- importowanie
- in
- włączony
- wskazuje
- nieefektywności
- przykład
- najnowszych
- intrygancki
- Wprowadzenie
- intuicyjny
- problemy
- IT
- JEGO
- przystąpić
- właśnie
- krajobraz
- język
- duży
- Nazwisko
- kłaść
- prowadzić
- nauka
- mniej
- niech
- LG
- biblioteki
- Biblioteka
- lubić
- Ograniczony
- Linia
- Lista
- wykazy
- relacja na żywo
- ll
- długo
- Popatrz
- robić
- i konserwacjami
- zarządzający
- wiele
- znaczy
- mechanika
- Mechanizmy
- Pamięć
- metoda
- metody
- może
- Moduł
- jeszcze
- większość
- ruch
- Potrzebować
- wymagania
- Nowości
- Nie
- nic
- zacienienie
- przedmiot
- obserwować
- of
- Oferty
- Oferty
- często
- on
- ONE
- operacyjny
- system operacyjny
- działanie
- operacje
- Optymalizacja
- zoptymalizowane
- or
- zamówienie
- Inne
- Pozostałe
- ludzkiej,
- na zewnątrz
- wyniki
- palecie
- przechodzić
- jest gwarancją najlepszej jakości, które mogą dostarczyć Ci Twoje monitory,
- wykonywania
- osoba
- plato
- Analiza danych Platona
- PlatoDane
- Grać
- nadmiar
- muzyka pop
- Pops
- potencjał
- potencjalnie
- mocny
- Praktyczny
- zapobiec
- poprzednio
- zasada
- priorytet
- problemy
- wygląda tak
- Obrobiony
- przetwarzanie
- projekt
- własność
- zapewnia
- cel
- Python
- Szybki
- podnieść
- zasięg
- RE
- Prawdziwy świat
- redukcja
- oczyścić
- Usunięto
- usuwanie
- reprezentować
- wywołań
- wymagać
- wymagania
- Wymaga
- rezonator
- Bogaty
- Pierścień
- krzepki
- Rola
- reguły
- s
- oszczędność
- scenariusz
- scenariusze
- szeregowanie
- nauka
- skrypty
- płynnie
- druga
- służyć
- służył
- serwer
- zestaw
- kilka
- Shadow
- arkusz
- powinien
- znaczący
- oznacza
- Prosty
- prostota
- sytuacje
- Rozmiar
- So
- Tworzenie
- rozwoju oprogramowania
- Rozwiązania
- kilka
- wyrafinowany
- Typ przestrzeni
- wyspecjalizowanym
- Widmo
- Nadużycie stosu
- standard
- standardy
- stojaki
- początek
- Startowy
- Rynek
- Ewolucja krok po kroku
- Stop
- przechowywany
- przechowywania
- bezpośredni
- Strumienie
- Struktura
- Struktury
- kolejny
- podpory
- SVG
- Przełącznik
- składnia
- system
- systemy
- stół
- sprzęt
- trwa
- Zadanie
- zadania
- Techniki
- podręcznik
- niż
- że
- Połączenia
- Krajobraz
- ich
- Im
- teoretyczny
- teoria
- Tam.
- Te
- one
- myśleć
- to
- tych
- Przez
- bilet
- czas
- do
- narzędzia
- przejście
- prawdziwy
- naprawdę
- SKRĘCAĆ
- drugiej
- wszechobecny
- odkryć
- zasadniczy
- zrozumienie
- nieobliczalny
- us
- posługiwać się
- łatwy w obsłudze
- za pomocą
- wartość
- różnorodność
- różnorodny
- Ve
- zweryfikować
- Tom
- vs
- Czekanie
- we
- sieć
- serwer wWW
- Co
- Co to jest
- Koło
- jeśli chodzi o komunikację i motywację
- który
- Podczas
- KIM
- szeroki
- Szeroki zasięg
- będzie
- w
- bez
- Praca
- przepływów pracy
- pracujący
- owinąć
- jeszcze
- You
- Twój
- siebie
- zefirnet