Samouczek dotyczący struktury danych kolejki w języku Python

Opanuj operacje kolejkowe FIFO w Pythonie. Wykonaj i uruchom nasz interaktywny przykład kolejki prezentujący metody umieszczania w kolejce i usuwania z kolejki.

Spróbuj w Edytorze

Przegląd

Kolejka to liniowa struktura danych działająca na zasadzie „pierwsze weszło, pierwsze wyszło” (FIFO). Elementy są dodawane z tyłu (kolejkowanie) i usuwane z przodu (usuwanie z kolejki), podobnie jak linia przy kasie w sklepie.

Kolejki mają kluczowe znaczenie w informatyce, ponieważ umożliwiają przetwarzanie zadań dokładnie w takiej kolejności, w jakiej przychodzą. Działają jak bufory oddzielające procesy producenta i konsumenta.

Python udostępnia wiele sposobów budowania kolejek: podstawowe listy, moduł `collections.deque` do szybkich operacji bezpiecznych dla wątków oraz moduł `queue.Queue` zaprojektowany specjalnie dla aplikacji wielowątkowych.

Dane wyjściowe kodu i wykonania

Interaktywna kolejka FIFO zbudowana przy użyciu Collections.deque w celu wydajnego usuwania frontów.

queue_demo.py

Spróbuj w Edytorze

from collections import deque

class Queue:
    def __init__(self):
        self.buffer = deque()
        
    def enqueue(self, item):
        self.buffer.append(item)
        print(f"Enqueued: {item}")
        
    def dequeue(self):
        if self.is_empty():
            return "Underflow: Queue is empty"
        dequeued = self.buffer.popleft()
        print(f"Dequeued: {dequeued}")
        return dequeued
        
    def is_empty(self):
        return len(self.buffer) == 0
        
    def size(self):
        return len(self.buffer)

# Test the Queue
q = Queue()
q.enqueue("Customer 1")
q.enqueue("Customer 2")
q.enqueue("Customer 3")

print(f"Queue Size: {q.size()}")
q.dequeue()
q.dequeue()

print(f"Remaining in Queue: {list(q.buffer)}")

Wyjście terminala

Enqueued: Customer 1
Enqueued: Customer 2
Enqueued: Customer 3
Queue Size: 3
Dequeued: Customer 1
Dequeued: Customer 2
Remaining in Queue: ['Customer 3']

Wdrażanie krok po kroku

Obsługa żądań asynchronicznych w frameworkach sieciowych serwerów
Kolejki planowania zadań w systemach operacyjnych
Brokerzy wiadomości i bufory kolejek (takie jak RabbitMQ lub Redis)

Często zadawane pytania

Dlaczego nie użyć list.pop(0) do usunięcia z kolejki w Pythonie?

Używanie `list.pop(0)` jest powolne, ponieważ wymaga przesunięcia wszystkich kolejnych elementów w pamięci o jeden indeks w lewo, co daje wydajność O(n). Natomiast `deque.popleft()` działa w stałym czasie O(1).

Co to jest kolejka priorytetowa?

Kolejka priorytetowa to odmiana, w której elementy są obsługiwane w oparciu o powiązany priorytet, a nie kolejność przybycia. Python implementuje to poprzez moduł `heapq`.

Powiązane tematy

Samouczek dotyczący struktury danych stosu w języku Python

Zaimplementuj stos LIFO w Pythonie. Uruchom nasz przykładowy interaktywny kod stosu, aby opanować limity push, pop, peek i pojemności.

Implementacja listy pojedynczo połączonej w Pythonie

Dowiedz się, jak zaimplementować pojedynczo połączoną listę w Pythonie. Przeglądaj dynamiczną alokację pamięci, operacje na węzłach, wstawianie, przeglądanie i usuwanie.