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:
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.
#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 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 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 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 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 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