Kolejki

https://docs.python.org/3/library/queue.html

WPROWADZENIE

Kolejka to ADT, który pozwala zapisywać dane i następnie pobierać je w takiej kolejności, w jakiej je zapisano (ang. first in, first out, FIFO; pierwszy wchodzi, pierwszy wychodzi). Interfejs kolejki ma minimum cztery funkcje:

• Inicjalizacja pustej kolejki (konstruktor).
• Test czy kolejka jest pusta (is_empty).
• Wstawienie elementu (push, put, enqueue).
• Pobranie elementu (pop, get, dequeue).
• Odczyt liczby elementów w kolejce (size).
• Czyszczenie kolejki (clear).

Jeżeli kolejka ma ograniczenie na liczbę przechowywanych elementów, to stosuje się jeszcze funkcję is_full(). Sytuacje prowadzące do błędu: przepełnienie kolejki, pobieranie elementu z pustej kolejki.

KOLEJKI W PYTHONIE

#from Queue import Queue   # Py2
from queue import Queue   # Py3

Q = Queue()
# Q.put(item)
# item = Q.get()
# Q.empty()   # czy pusta

Inna implementacja kolejki może korzystać z collections.deque i operacji len, clear, append+popleft lub appendleft+pop.

IMPLEMENTACJA 1

Implementacja kolejki FIFO za pomocą list Pythona. Robimy otoczkę wokół list stosując podejście obiektowe. Python sam wykryje próbę pobierania elementu z pustej kolejki.

class Queue:

    def __init__(self):
        self.items = []

    def __str__(self):   # podglądanie kolejki
        return str(self.items)

    def is_empty(self):
        return not self.items

    def is_full(self):   # nigdy nie jest pusta
        return False

    def put(self, data):
        self.items.append(data)

    def get(self):
        return self.items.pop(0)   # mało wydajne!

Po zapisaniu tego kodu do osobnego modułu queue.py możemy w dowolnym programie korzystać z kolejek.

import queue

aqueue = queue.Queue()    # inicjalizacja kolejki
for item in ["a", 2, 3.5]:
    aqueue.put(item)
# Pobieranie elementów z kolejki w kolejności: "a", 2, 3.5
while not aqueue.is_empty():
    print(aqueue.get())

IMPLEMENTACJA 2

Implementacja kolejki FIFO za pomocą listy jednokierunkowej.

class Node:

    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

    def __str__(self):
        return str(self.data)

class Queue:

    def __init__(self):
        self.head = None

    def is_empty(self):
        return not self.head

    def put(self, data):   # linear-time O(n)
        node = Node(data)   # next jest domyślnie None
        if self.is_empty():
            self.head = node
        else:    # dajemy na koniec listy
            last = self.head
            while last.next:
                last = last.next
            last.next = node

    def get(self):   # constat-time O(1)
        data = self.head.data
        self.head = self.head.next
        return data

Metoda put() nie jest optymalna, ponieważ jest klasy O(n). Wymaga przejścia przez wszystkie węzły, aby dotrzeć do ostatniego węzła. Rozwiązaniem tego problemu jest dodatkowy atrybut tail w klasie Queue, w którym zapisana będzie referencja do ostatniego elementu.

IMPLEMENTACJA 3

Implementacja kolejki FIFO za pomocą listy jednokierunkowej. Dodajemy wskaźnik do ogona, aby poprawić wydajność listy.

class Node:

    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

    def __str__(self):
        return str(self.data)

class Queue:

    def __init__(self):
        self.head = None
        self.tail = None

    def is_empty(self):
        return not self.head

    def put(self, data):   # constat-time O(1)
        node = Node(data)   # next jest domyślnie None
        if self.is_empty():
            self.head = self.tail = node
        else:   # dajemy na koniec listy
            self.tail.next = node
            self.tail = node

    def get(self):   # constat-time O(1)
        data = self.head.data
        self.head = self.head.next
        if self.is_empty():   # zabezpieczenie
            self.tail = None
        return data

# Wykorzystanie klasy SingleList do budowy kolejki.
# Tutaj insert_tail() i remove_head() używają 'node.data', a nie 'node'.
import slist

class Queue(slist.SingleList):
    put = slist.SingleList.insert_tail
    get = slist.SingleList.remove_head

IMPLEMENTACJA 4

Implementacja kolejki FIFO za pomocą listy dwukierunkowej.

import dlist

class Queue(dlist.DoubleList):
    put = dlist.DoubleList.insert_head
    get = dlist.DoubleList.remove_tail

import dlist

class Queue(dlist.DoubleList):
    put = dlist.DoubleList.insert_tail
    get = dlist.DoubleList.remove_head

IMPLEMENTACJA 5

Implementacja kolejki FIFO za pomocą tablicy cyklicznej. Przy inicjalizacji kolejki trzeba podać maksymalną liczbę przechowywanych w kolejce elementów (size). Wykorzystywana w implementacji tablica będzie o jeden większa, aby przy pełnej tablicy head i tail były różne.

class Queue:

    def __init__(self, size=5):
        self.n = size + 1         # faktyczny rozmiar tablicy
        self.items = self.n * [None] 
        self.head = 0           # pierwszy do pobrania 
        self.tail = 0           # pierwsze wolne

    def is_empty(self):
        return self.head == self.tail

    def is_full(self):
        return (self.tail + 1) % self.n == self.head

    def put(self, data):
        self.items[self.tail] = data
        self.tail = (self.tail + 1) % self.n

    def get(self):
        data = self.items[self.head]
        self.items[self.head] = None   # usuwam referencję
        self.head = (self.head + 1) % self.n
        return data

Przykładowe operacje dla tablicy pięcioelementowej (size = 4, n = 5).
kolejka pusta (head == tail)
+--+--+--+--+--+ head = 0 (pierwszy zajęty)
|  |  |  |  |  | tail = 0 (pierwszy wolny)
+--+--+--+--+--+
put(11) ; put(22) ; put(33) ; put(44)
+--+--+--+--+--+ head = 0
|11|22|33|44|  | tail = 4
+--+--+--+--+--+ kolejka pełna ((tail + 1) % n == head)
get() ; get()
+--+--+--+--+--+ head = 2
|  |  |33|44|  | tail = 4
+--+--+--+--+--+
put(55) ; put(66)
+--+--+--+--+--+ head = 2
|66|  |33|44|55| tail = 1
+--+--+--+--+--+ kolejka pełna