W informatyce struktury danych stanowią fundamentalny element. To dzięki nim dane są organizowane w sposób umożliwiający ich efektywne wykorzystanie. Wśród różnorodnych struktur, kolejka wyróżnia się swoją prostotą i użytecznością.
W tym tekście przyjrzymy się bliżej koncepcji kolejki i zaprezentujemy, jak można ją zaimplementować w języku Python.
Czym jest kolejka?
Kolejka, jako liniowa struktura danych, działa zgodnie z zasadą FIFO (ang. First In, First Out), co oznacza „pierwsze weszło, pierwsze wyszło”. Jest ona przeciwieństwem stosu, który działa na zasadzie LIFO (ang. Last In, First Out).
Działanie kolejki można łatwo zilustrować na przykładzie kolejki do kasy w kinie. Wyobraźmy sobie następującą sytuację.
Osoba stojąca na początku kolejki jest obsługiwana jako pierwsza, a kolejne osoby czekają na swoją kolej. Zatem, każdy uczestnik kolejki przestrzega zasady FIFO. Kto pierwszy stanie w kolejce, ten pierwszy zostanie obsłużony. Identyczne sytuacje obserwujemy na co dzień w wielu innych miejscach.
Struktura danych kolejki działa na tej samej zasadzie. Teraz, gdy wiesz już, na czym polega zasada działania kolejki, zobaczmy, jakie operacje można wykonywać na tej strukturze danych.
Operacje na kolejce
Podobnie jak w przypadku stosu, w kolejce wyróżniamy dwie podstawowe operacje.
Enqueue (dane)
Ta operacja polega na dodaniu nowych danych na koniec kolejki. Koniec kolejki nazywany jest tyłem.
Dequeue ()
Usuwa element z początku kolejki, który nazywany jest przodem.
Dla lepszego zrozumienia operacji na kolejce, spójrzmy na ilustracje. Jeden obraz często wart jest więcej niż tysiąc słów.
Oprócz tych dwóch podstawowych operacji, warto zaimplementować kilka dodatkowych funkcji pomocniczych, które dostarczą nam więcej informacji o kolejce. Liczba takich funkcji nie jest ograniczona, jednak na początek skupmy się na najważniejszych.
rear()
Zwraca element znajdujący się na końcu kolejki (jej tył).
front()
Zwraca element znajdujący się na początku kolejki (jej przód).
is_empty()
Informuje, czy kolejka jest pusta, czy zawiera elementy.
Czy ta dawka teorii Cię nie znudziła? Rozumiem, że abstrakcyjne pojęcia mogą być przytłaczające.
Dla mnie również!
Jednak, bez znajomości teoretycznych podstaw, trudno będzie nam przejść do praktyki. Uzupełnijmy więc tę wiedzę zanim zaczniemy pisać kod. Nie martw się, zaraz przejdziemy do bardziej angażującej części.
Zakładam, że masz już zainstalowanego Pythona. Jeśli nie, możesz skorzystać z kompilatora online.
Implementacja kolejki
Zaimplementowanie kolejki nie powinno zająć programiście więcej niż kwadrans. Po przyswojeniu tej wiedzy, być może uda Ci się to zrobić w kilka minut.
Istnieje kilka sposobów implementacji kolejki w Pythonie. Prześledźmy krok po kroku różne możliwości.
#1. Lista
Lista jest wbudowanym typem danych w Pythonie. Wykorzystamy ją do zaimplementowania kolejki w formie klasy. Przejdziemy przez wszystkie etapy tworzenia struktury danych kolejki od podstaw, bez użycia dodatkowych modułów. Zaczynajmy!
Krok 1:
Zdefiniujmy klasę o nazwie Queue.
class Queue:
pass
Krok 2:
W klasie musi istnieć zmienna do przechowywania danych kolejki. Nazwijmy ją elements i zainicjujmy jako pustą listę.
class Queue:
def __init__(self):
self.elements = []
Krok 3:
Aby móc dodawać dane do kolejki, potrzebujemy metody o nazwie enqueue, o której wspominaliśmy już wcześniej.
Metoda ta będzie przyjmować dane i dodawać je do kolejki (listy elements) za pomocą metody append, która dodaje nowy element na koniec listy.
class Queue:
# ...
def enqueue(self, data):
self.elements.append(data)
return data
Krok 4:
Kolejka musi umożliwiać pobieranie z niej danych. Użyjemy do tego metody dequeue. Zapewne domyślasz się, że wykorzystamy tutaj metodę pop, która jest dostępna dla list.
Metoda pop usuwa element z listy o podanym indeksie. Jeżeli nie podamy indeksu, usunie ostatni element.
W naszym przypadku, musimy usuwać pierwszy element listy, więc przekażemy indeks 0 do metody pop.
class Queue:
# ...
def dequeue(self):
return self.elements.pop(0)
To wystarczy, aby nasza kolejka działała. Jednak potrzebujemy funkcji pomocniczych, aby sprawdzić, czy wszystko działa poprawnie. Zdefiniujmy je.
Krok 5:
Metoda rear() ma zwrócić ostatni element kolejki. Wykorzystamy tu indeksowanie ujemne, które w listach pozwala na dostęp do elementów od końca.
class Queue:
# ...
def rear(self):
return self.elements[-1]
Krok 6:
Metoda front() zwraca pierwszy element kolejki. Uzyskamy go za pomocą indeksu 0.
class Queue:
# ...
def front(self):
return self.elements[0]
Krok 7:
Metoda is_empty() sprawdza, czy kolejka jest pusta. Zweryfikujemy to za pomocą długości listy.
class Queue:
# ...
def is_empty(self):
return len(self.elements) == 0
Uff! Zakończyliśmy implementację struktury danych kolejki. Teraz musimy utworzyć obiekt, aby móc korzystać z naszej klasy.
Zróbmy to.
class Queue:
# ...
if __name__ == '__main__':
queue = Queue()
Mamy już obiekt kolejki. Przetestujmy go za pomocą kilku operacji.
- Sprawdźmy, czy kolejka jest pusta, używając metody is_empty. Powinna zwrócić True.
- Dodajmy liczby 1, 2, 3, 4 i 5 do kolejki za pomocą metody enqueue.
- Metoda is_empty powinna zwrócić False. Sprawdźmy to.
- Wyświetlmy elementy z przodu i z tyłu kolejki za pomocą metod front i rear.
- Usuńmy element z kolejki metodą dequeue.
- Sprawdźmy element z przodu. Powinien zwrócić element 2.
- Usuńmy wszystkie elementy z kolejki.
- Metoda is_empty powinna zwrócić True. Sprawdźmy to.
Myślę, że to wystarczy, aby przetestować naszą implementację kolejki. Spróbuj napisać kod dla każdego z wymienionych kroków.
Udało Ci się?
Nie martw się, jeśli nie.
Sprawdź poniższy kod.
class Queue:
def __init__(self):
self.elements = []
def enqueue(self, data):
self.elements.append(data)
return data
def dequeue(self):
return self.elements.pop(0)
def rear(self):
return self.elements[-1]
def front(self):
return self.elements[0]
def is_empty(self):
return len(self.elements) == 0
if __name__ == '__main__':
queue = Queue()
## checking is_empty method -> True
print(queue.is_empty())
## adding the elements
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)
## again checking is_empty method -> False
print(queue.is_empty())
## printing the front and rear elements using front and rear methods respectively -> 1, 5
print(queue.front(), end=' ')
print(queue.rear())
## removing the element -> 1
queue.dequeue()
## checking the front and rear elements using front and rear methods respectively -> 2 5
print(queue.front(), end=' ')
print(queue.rear())
## removing all the elements
queue.dequeue()
queue.dequeue()
queue.dequeue()
queue.dequeue()
## checking the is_empty method for the last time -> True
print(queue.is_empty())
Uruchom powyższy kod. Powinieneś uzyskać wynik podobny do poniższego:
True False 1 5 2 5 True
Jak widzisz, lista może być bezpośrednio wykorzystana jako struktura danych kolejki. Powyższa implementacja ma na celu lepsze zrozumienie, jak kolejka działa od środka.
Możesz wykorzystać powyższą klasę Queue w innych projektach, tworząc nowy obiekt.
Stworzyliśmy kolejkę od podstaw, używając list. Czy istnieją jakieś wbudowane moduły ułatwiające to zadanie? Oczywiście! Zobaczmy, jakie gotowe implementacje mamy do dyspozycji.
#2. deque z modułu collections
Deque (double-ended queue), czyli kolejka dwustronna, jest implementowana w Pythonie. Ponieważ pozwala na dodawanie i usuwanie elementów z obu końców, można jej używać zarówno jako stosu, jak i kolejki. Zobaczmy, jak można zaimplementować kolejkę przy użyciu deque.
Deque jest oparta na liście podwójnie połączonej, dzięki czemu operacje dodawania i usuwania elementów są szybkie. Dostęp do elementów w środku listy podwójnie połączonej zajmuje O(n) czasu. W przypadku kolejki, nie ma potrzeby dostępu do elementów środkowych, co sprawia, że deque jest dla niej odpowiednią strukturą.
Spójrzmy na metody, które oferuje deque:
- append(data) – służy do dodawania danych na koniec kolejki
- popleft() – służy do usuwania pierwszego elementu z kolejki
Nie ma bezpośrednich odpowiedników dla metod front, rear i is_empty. W zamian możemy wyświetlić całą kolejkę, a długość kolejki sprawdzić za pomocą funkcji len().
Przetestujmy deque, wykonując te same operacje, które przeprowadziliśmy przy implementacji z użyciem listy.
from collections import deque ## creating deque object queue = deque() ## checking whether queue is empty or not -> True print(len(queue) == 0) ## pushing the elements queue.append(1) queue.append(2) queue.append(3) queue.append(4) queue.append(5) ## again checking whether queue is empty or not -> False print(len(queue) == 0) ## printing the queue print(queue) ## removing the element -> 1 queue.popleft() ## printing the queue print(queue) ## removing all the elements queue.popleft() queue.popleft() queue.popleft() queue.popleft() ## checking the whether queue is empty or not for the last time -> True print(len(queue) == 0)
Otrzymasz wynik podobny do poniższego:
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Queue z modułu queue
Python oferuje również moduł o nazwie queue, który zawiera klasę Queue do implementacji kolejek. Jest ona bardzo podobna do tej, którą zaimplementowaliśmy samodzielnie na początku.
Sprawdźmy, jakie metody oferuje ta klasa:
- put(data) – dodaje dane do kolejki
- get() – usuwa pierwszy element z kolejki i go zwraca
- empty() – informuje, czy kolejka jest pusta
- qsize() – zwraca długość kolejki
Zaimplementujmy kolejkę, wykorzystując te metody.
from queue import Queue
## creating Queue object
queue_object = Queue()
## checking whether queue is empty or not -> True
print(queue_object.empty())
## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)
## again checking whether queue is empty or not -> False
print(queue_object.empty())
## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())
## checking the queue size
print("Size", queue_object.qsize())
print(queue_object.get())
print(queue_object.get())
## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())
Sprawdźmy wynik tego kodu:
True False 1 2 3 Size 2 4 5 True
Klasa Queue ma kilka innych metod, które możesz eksplorować samodzielnie, używając funkcji dir().
Podsumowanie
Mam nadzieję, że udało Ci się zrozumieć, jak działa struktura danych kolejki i jak ją implementować. Na tym kończymy temat kolejki. Możesz używać kolejek wszędzie tam, gdzie trzeba przetwarzać dane w kolejności FIFO (ang. First In/First Out). Wykorzystuj je w rozwiązywaniu problemów, gdy tylko nadarzy się ku temu okazja.
Chcesz zostać mistrzem Pythona? Sprawdź te materiały edukacyjne.
Udanej zabawy z kodowaniem 🙂 👨💻
newsblog.pl
Maciej – redaktor, pasjonat technologii i samozwańczy pogromca błędów w systemie Windows. Zna Linuxa lepiej niż własną lodówkę, a kawa to jego główne źródło zasilania. Pisze, testuje, naprawia – i czasem nawet wyłącza i włącza ponownie. W wolnych chwilach udaje, że odpoczywa, ale i tak kończy z laptopem na kolanach.