Kolejka (Queue) – samouczek, FIFO krok po kroku

Wiesz, że kolejka (Queue) jest jedną z częściej wykorzystywanych struktur danych w Javie? – I co kryje się pod akronimem FIFO? Dzięki temu materiałowi dowiesz się jak krok po kroku wykorzystać kolejkę do budowania własnej aplikacji oraz jak samodzielnie zaimplementować FIFO.

Witaj w drugiej części wpisu na temat struktur danych: FIFO oraz LIFO. W dzisiejszej odcinku zajmiemy się szczegółowo kolejką (ang. queue) oraz akronimem FIFO.
Jeżeli jednak nie czytałeś jeszcze pierwszej części, to gorąco zachęcam do zapoznania się z nią w pierwszej kolejności: Stos (Stack) – 7+ tajników implementacji LIFO.

Zapraszam do lektury.

[SprawnyProgramista_intro]

Z tej serii dowiesz się:

• co to jest LIFO, FIFO, HIFO, FEFO, FINO oraz FISH; 🙂
• co to jest i jak działa stos (ang. stack);
• jak działa kolejka (ang. queue) oraz kolejka priorytetowa (ang. priority queue);
• jak samodzielnie zaimplementować takie struktury danych;
• oraz jak korzystać z gotowych rozwiązań.

Kolejka (ang. queue)

Gdy myślę o kolejce, nasuwa mi się przede wszystkim skojarzenie z kolejką ludzi czekających do kasy w sklepie lub też ze sznurem samochodów stojących w korku na drodze jednopasmowej.

W kontekście informatyki jest to jak najbardziej trafna analogia. Kolejkę danych rozumiemy jako ciąg elementów ułożonych jeden za drugim, który charakteryzuje się przede wszystkim tym, że zachowana jest konkretna kolejność przechowywania tych elementów.

Kolejka zazwyczaj porządkuje elementy zgodnie z zasadą FIFO. Wyjątek od tej reguły stanowi kolejka priorytetowa, ale do tego jeszcze wrócimy.

FIFO (ang. First In, First Out)

Wszystkie elementy w kolejce – czy to w kolejce danych, czy w kolejce osób w sklepie zwyczajowo zachowują się zgodnie z FIFO (ang. First In, First Out) – czyli w dosłownym tłumaczeniu: pierwszy na wejściu, pierwszy na wyjściu. Pomijamy na chwilę przypadek z przepychankami kolejkowymi, zakładamy, że każdy będzie grzecznie stał i czekał na swoją kolej.

Dzięki takiemu przechowywaniu elementów mamy pewność, że natłok nowych elementów nie spowoduje niejako zagłodzenia elementów już znajdujących się w kolejce od pewnego czasu, jak mogłoby to mieć miejsce w przypadku stosu. Musimy się jednak liczyć z możliwością, że w procesie dodawania bardzo wielu elementów do kolejki i wolnego ich przetwarzania, czyli zdejmowania ich z kolejki, czas oczekiwania w naszej kolejce bardzo się wydłuży.

LIFO vs FIFO

Przeciwieństwem omawianej tu kolejki i organizacji elementów zgodnie z FIFO
jest stos z elementami ułożonymi wg zasady LIFO (ang. Last In, First Out) – czyli ostatni na wejściu, pierwszy na wyjściu.

Więcej na ten temat będziesz mógł przeczytać w pierwszej części wpisu:
Stos (Stack) – 7+ tajników implementacji LIFO

Struktury danych oparte o FIFO bardzo chętnie wykorzystywane są w informatyce przede wszystkim do przechowywania danych lub jako systemy planowania zadań.

Omówimy sobie teraz główne koncepcje związane z wykorzystywaniem kolejki.

Głowa kolejki (ang. queue head or front)

Zacznijmy od pojęcia głowy (ang. head) kolejki – jest to wskaźnik określający, w którym miejscu znajduje się najstarszy/pierwszy element kolejki.

Niektóre z operacji wykonywanych na kolejce, takie jak np. pobranie pierwszego elementu (ang. poll) czy podejrzenie pierwszego elementu (ang. peek), będą właśnie korzystały z tego wskaźnika.

Ogon kolejki (ang. queue tail)

Ogonem kolejki (ang. queue tail) zwyczajowo nazywamy wskaźnik wskazujący na ostatni element w kolejce. Operacja korzystająca z tego wskaźnika to dodanie nowego elementu na końcu kolejki (ang. queue offer or insert).

Dodanie elementu do kolejki (ang. queue offer or insert)

Korzystając z metody offer, nowo dodane elementy domyślnie lądują na końcu kolejki i wskazuje na nie wskaźnik tail. W przypadku, gdy w kolejce będzie tylko jeden element, oba wskaźniki head i tail będą wskazywały na ten sam obiekt.

Wyjście z kolejki (ang. queue poll or remove)

Metoda poll pobiera pierwszy element z kolejki i go z niej zdejmuje. Wskaźnik head będzie teraz wskazywał na element, który był drugi lub na wartość pustą NULL, jeżeli nie ma więcej elementów.

Podejrzenie pierwszego elementu kolejki (ang. queue peek or element)

Metoda peek zwraca pierwszy element z kolejki, czyli ten wskazywany przez head, ale – w przeciwieństwie do metody poll – jej nie modyfikuje.

Przyjrzyjmy się teraz bliżej, co Java oferuje nam w kontekście kolejek.

Zamieszczone poniżej fragmenty kodu napisano w Javie, jednak przykłady są na tyle uniwersalne, że nie powinno być problemu z odniesieniem ich do innych języków programowania.

Do dyspozycji mamy przede wszystkim interfejs: java.util.Queue oraz rozszerzające go subinterfejsy: java.util.concurrent.BlockingDeque, java.util.concurrent.TransferQueue i java.util.Deque.

Wszystkie te interfejsy i ich różne implementacje wykorzystywane są do obsługi większości kolejek w Javie. Przyjrzyjmy się teraz im trochę dokładniej.

AbstractQueue

java.util.AbstractQueue to najprostsza dostępna implementacja. Nie jest to jeszcze pełnoprawna kolejka i stanowi jedynie szkielet dla konkretnych implementacji.

Kolejki blokujące (ang. blocking queues)

java.util.concurrent.BlockingQueue obsługuje dodatkowe metody wspierające blokowanie operacji, np. poczekanie i przytrzymanie logiki pobierania elementu z kolejki, jeżeli jeszcze nic w niej nie ma.

Jeżeli chodzi o implementacje, to możemy skorzystać z java.util.concurrent.LinkedBlockingQueue, java.util.concurrent.SynchronousQueue i java.util.concurrent.ArrayBlockingQueue.

Prześledźmy to na przykładzie poniższego kodu:

BlockingQueue<String> blockingQueue = new ArrayBlockingQueue<>(10);

try {
	new Thread(() -> {
		try {
			Thread.sleep(1000);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}

		blockingQueue.offer("Hello from another thread.");
	}).start();

	System.out.println(blockingQueue.poll());

	System.out.println(blockingQueue.poll(5, TimeUnit.SECONDS));
} catch (InterruptedException e) {
	e.printStackTrace();
}

• tworzymy blokującą kolejkę o pojemności 10 elementów: BlockingQueue blockingQueue = new ArrayBlockingQueue<>(10);
• tworzymy i uruchamiamy nowy wątek, który czeka sekundę i dodaje nowy element do kolejki;
• wywołujemy standardową metodę: blockingQueue.poll(), która zwraca NULL, ponieważ kolejka jest jeszcze pusta;
• natomiast wywołanie metody: blockingQueue.poll(5, TimeUnit.SECONDS) poczeka maksymalnie 5 sekund, aż coś pojawi się w kolejce i pobierze ten element – w naszym wypadku po około jednej sekundzie drugi wątek uzupełni kolejkę, przez co metoda poll będzie mogła go pobrać.

Kolejki a wielowątkowość (ang. Thread Safety)

W przypadku aplikacji wielowątkowych warto zainteresować się dedykowanymi implementacjami, takimi jak: java.util.concurrent.ConcurrentLinkedDeque, java.util.concurrent.ConcurrentLinkedQueue, czy java.util.concurrent.ArrayBlockingQueue.

Deque

Deque to skrót od ang. Double-Ended Queue – czyli podwójnie zakończona kolejka. W tym wypadku możemy dodawać i usuwać elementy zarówno z początku, jak i z końca takiej kolejki.

W Javie do obsługi Deque mamy interfejs java.util.Deque oraz między innymi implementacje: java.util.ArrayDeque i java.util.LinkedList.

Kolejka priorytetowa (ang. priority queue)

Kolejka priorytetowa łamie już zasady FIFO. W tym wypadku o tym, który element zostanie pobrany jako pierwszy, nie decyduje już to, kiedy został dodany, ale jego waga – ważność.

Możesz to sobie wyobrazić jako standardową kolejkę np. przy wsiadaniu do samolotu – wszyscy czekają, jeden za drugim, aż tu nagle przychodzi VIP z wykupionym specjalnym pakietem członkowskim i ładuje się na sam początek kolejki.

Sprawa trochę bardziej się komplikuje, gdy mamy więcej osób/elementów w kolejce z różnymi wagami – wtedy poszczególne elementy w kolejce są układane właśnie według ich wagi.

HIFO (ang. Highest In, First Out)

Kolejka priorytetowa bywa nazywana również HIFO (ang. Highest In, First Out) – czyli najwyższe/najdroższe elementy będą przetwarzane jako pierwsze.

Elementy dodawane do java.util.PriorityQueue domyślne układane są według ich naturalnej kolejności, czyli np. dla liczb całkowitych zostaną one posortowane wg wielkości. Natomiast dla ciągów znaków byłaby to kolejność alfabetyczna.

// given
PriorityQueue<Integer> queue = new PriorityQueue<>();

queue.offer(1);
queue.offer(10);
queue.offer(2);
queue.offer(20);
queue.offer(3);
queue.offer(30);

// when
List<Integer> list = new ArrayList<>();

while (!queue.isEmpty()) {
	list.add(queue.poll());
}

// then
assertThat(list).containsExactly(1, 2, 3, 10, 20, 30);

Comparator i Comparable

Na to domyślne zachowanie też możemy wpłynąć. Jeżeli elementy przechowywane w kolejce będą implementowały interfejs: java.lang.Comparable, jak ma to miejsce w przypadku klas String i Integer, to zostaną one ułożone zgodnie z implementacją metody: java.lang.Comparable#compareTo.

Możemy jednak nadpisać to zachowanie i – tworząc kolejkę – jako argument przekazać komparator (obiekt implementujacy: java.util.Comparator), który zdecyduje, w jakiej kolejności mają zostać ułożone elementy.

// given
Comparator<String> comparator = (o1, o2) -> {
	int length1 = o1.length();
	int length2 = o2.length();

	if (length1 == length2) {
		return o1.compareTo(o2);
	}

	return length1 - length2;
};

PriorityQueue<String> queue = new PriorityQueue<>(comparator);

queue.offer("a");
queue.offer("c");
queue.offer("cc");
queue.offer("ccc");
queue.offer("C");
queue.offer("aa");

// when
List<String> list = new ArrayList<>();

while (!queue.isEmpty()) {
	list.add(queue.poll());
}

// then
assertThat(list).containsExactly("C", "a", "c", "aa", "cc", "ccc");

W naszym przykładzie elementy w kolejce przechowującej ciągi znaków zostaną ułożone według ich długości.

1. Utworzenie kolejki

Queue<Integer> queue = new ArrayDeque<>();

2. Dodanie nowego elementu do kolejki (ang. queue offer)

queue.offer(1);
queue.add(2);

Obie metody różnią się tylko raportowaniem ewentualnych problemów podczas dodawania nowego elementu:

• offer – w przypadku niewystarczającej ilości miejsca zwróci false, natomiast:
• add – zwróci wyjątek: IllegalStateException.

3. Zdjęcie z kolejki pierwszego elementu (ang. queue poll)

Integer poll1 = queue.poll();
Integer remove1 = queue.remove();

Te dwie metody też różnią się tylko raportowaniem błędów:

• poll – zwróci wartość pustą NULL, jeżeli kolejka będzie pusta, natomiast:
• remove – zwróci wyjątek: NoSuchElementException.

4. Pobranie pierwszego elementu bez modyfikacji kolejki (ang. queue peek)

Integer peek1 = queue.peek();
Integer element1 = queue.element();

I w przypadku tej operacji mamy do dyspozycji dwie metody różniące się tylko nieznacznie:

• peek – zwróci NULL w przypadku pustej kolejki, natomiast:
• element – zwróci wyjątek: NoSuchElementException.

5. Przeglądanie kolejki i wyświetlenie elementów (ang. queue iterate)

Elementy w kolejce możemy przeglądać na kilka różnych sposobów, np. korzystając ze wbudowanego iteratora: queue.iterator().

Iterator<Integer> it = queue.iterator();
while (it.hasNext()) {
	Integer item = it.next();
	System.out.println(item);
}

Alternatywnie można skorzystać z pętli while oraz metody poll – jak w drugim przykładzie.

while (!queue.isEmpty()) {
	Integer item = queue.poll();
	System.out.println(item);
}

6. Korzystanie z kolejki przy pomocy strumieni i wyrażeń lambda (ang. queue java stream)

Nic nie stoi na przeszkodzie, żeby z kolejki korzystać przy pomocy strumieni i wyrażeń lambda.
Najpierw pobieramy strumień, korzystając z metody: stream(), i wykonujemy niezbędne operacje.

Poniżej kilka przykładów.

• Wyświetlenie wszystkich elementów na standardowe wyjście.

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);

queue.stream().forEach(System.out::print);

• Zamiana kolejki na listę.

List<Integer> list = queue.stream().collect(Collectors.toList());
System.out.println(list);

• Usunięcie wybranych elementów.

queue.removeIf(element -> element > 3);

• Zamiana kolejki na tablicę.

int[] intArray = queue.stream()
		.mapToInt(element -> element)
		.toArray();

System.out.println(Arrays.toString(intArray));

PHP

Ds\Queue implements Ds\Collection {
/* Constants */
const int MIN_CAPACITY = 8 ;
/* Methods */
public allocate ( int $capacity ) : void
public capacity ( void ) : int
public clear ( void ) : void
public copy ( void ) : Ds\Queue
public isEmpty ( void ) : bool
public peek ( void ) : mixed
public pop ( void ) : mixed
public push ([ mixed $...values ] ) : void
public toArray ( void ) : array
}

Źródło: The Queue class

Python

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

tw@tw:~$ python
Python 2.7.15+ (default, Oct  7 2019, 17:39:04) 
[GCC 7.4.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import Queue
>>> 
>>> queue = Queue.Queue()
>>> 
>>> for i in range(3):
...     queue.put(i)
... 
>>> while not queue.empty():
...     print queue.get()
... 
0
1
2
>>> 

C/C++

// queue::push/pop
#include <iostream>       // std::cin, std::cout
#include <queue>          // std::queue

int main ()
{
  std::queue<int> myqueue;
  int myint;

  std::cout << "Please enter some integers (enter 0 to end):\n";

  do {
    std::cin >> myint;
    myqueue.push (myint);
  } while (myint);

  std::cout << "myqueue contains: ";
  while (!myqueue.empty())
  {
    std::cout << ' ' << myqueue.front();
    myqueue.pop();
  }
  std::cout << '\n';

  return 0;
}

Źródło

W celu utrwalenia omawianych tu zagadnień spróbujemy teraz samodzielnie zaimplementować standardową kolejkę typu FIFO.

Najczęściej możemy spotkać się z dwiema różnymi implementacjami kolejki:

• Array queue – bazującej na tablicy oraz
• Linked queue – wykorzystującej listę wskaźnikową.

W naszych rozważaniach zaimplementujemy kolejkę opartą na tablicy.

Przerobienie tych przykładów nie jest konieczne do zrozumienia omawianych tu pojęć i w zdecydowanej większości przypadków dużo lepszym wyjściem jest skorzystanie z gotowych już klas implementujących kolejkę, takich jak java.util.ArrayDeque czy java.util.LinkedList.
Mimo wszystko zachęcam do ich przejrzenia i samodzielnej próby implementacji – jest to świetny sposób na utrwalenie wiedzy w praktyce i pełniejsze zrozumienie tematu.

Interfejs stosu i główne wymagania

Nasza kolejka powinna implementować wszystkie podstawowe metody, takie jak: peek, pull, offer i size. Zanim jednak przejdziemy do samej implementacji, zacznijmy od zdefiniowania interfejsu – czyli określmy, co właściwie będzie robiła nasza kolejka.

Na tym etapie jeszcze nie określamy, jak będzie to realizowane – tym zajmiemy się podczas implementacji.

public interface Queue<T> {

	void offer(T element);

	T poll();

	T peek();

	int size();
}

Wewnętrzna tablica przechowująca elementy

Elementy w naszej kolejce przechowamy w tablicy, dzięki czemu będziemy mieć prawie za darmo zapewnioną ich kolejność.

Nie musimy też przejmować się takimi wskaźnikami, jak head czy tail, jak miałoby to miejsce w przypadku implementacji z listą wskaźnikową.

public class ArrayQueue<T> implements Queue<T> {

	private Object[] array = new Object[MAX_SIZE];

Ponieważ tablice mają stały rozmiar, musimy określić maksymalną ilość przechowywanych elementów.

Tablica będzie przechowywała referencje typu Object, jednak później będziemy je rzutować na konkretne klasy.

Rozmiar (ang. queue size) i pojemność (ang. queue capacity) kolejki 

private final int MAX_SIZE = 10; 
private int size = 0;

Żeby za każdym razem nie liczyć wszystkich elementów, które są w kolejce, do przechowania rozmiaru wykorzystamy wewnętrzną zmienną.

Natomiast maksymalna pojemność kolejki została pobrana ze stałej.

Dodanie elementu do kolejki (ang. offer)

Dodawanie nowego elementu do kolejki musimy zacząć od sprawdzenia, czy mamy jeszcze wolne miejsce. Jeżeli nie ma już miejsca, to odpowiednio to komunikujemy wyjątkiem, jak w przykładzie lub np. zwracając z metody FALSE.
Następnie wstawiamy element na ostatnim miejscu w tablicy i inkrementujemy licznik, który jest jednocześnie ilością przechowywanych elementów w tablicy.

@Override
public void offer(T value) {
	if (size == MAX_SIZE) {
		throw new IllegalArgumentException(String.format("Maximum stack size: %s has been reached.", MAX_SIZE));
	}

	array[size++] = value;
}

Zdjęcie elementu z kolejki (ang. poll)

W metodzie poll zaczynamy od sprawdzenia, czy są już jakieś elementy w kolejce i jeżeli ich nie ma, to trzeba zwrócić użytkownikowi odpowiednią informację. Możemy to zrobić, jak w przykładzie, zwracając NULL lub rzucić wyjątek.

W kolejnych krokach:

• pobieramy pierwszy element z tablicy;
• dekrementujemy licznik, a zarazem zmienną przechowującą rozmiar tablicy;
• przesuwamy wszystkie pozostałe elementy w tablicy o jedną pozycję do przodu;
• czyścimy ostatnie, już niewykorzystywane, miejsce w tablicy;
• i zwracamy wynik.

@Override
public T poll() {
	if (size <= 0) {
		return null;
	}

	T value = (T) array[0];

	size--;

	System.arraycopy(array, 1, array, 0, size);
	array[size] = null;

	return value;
}

Przyjrzyjmy się trochę dokładniej, jak wygląda takie przesunięcie elementów w tablicy. Komenda: System.arraycopy(array, 1, array, 0, size);  skopiuje dotychczasowe elementy i wklei je, przesuwając o jedną pozycję w lewo.

A

B

C

NULL

Jednak ostatni element będzie znajdował się w dwóch miejscach – w nowym, przesuniętym, oraz na swojej starej pozycji, dlatego musimy go wyczyścić kolejną komendą: array[size] = null; .

B

C

C

NULL

Po tych operacjach tablica powinna zawierać następujące elementy:

B

C

NULL

NULL

Podejrzenie elementu znajdującego się na początku kolejki (ang. peek)

Podobnie jak w przypadku metody poll, sprawdzamy, czy mamy jakieś elementy w kolejce. Jeżeli mamy, to zwracamy pierwszy z nich – znajdujący się pod indeksem 0  w tablicy.

@Override
public T peek() {
	if (size <= 0) {
		return null;
	}

	return (T) array[0];
}

Pełna implementacja

public class ArrayQueue<T> implements Queue<T> {

	private final int MAX_SIZE = 10;
	private int size = 0;
	private Object[] array = new Object[MAX_SIZE];

	@Override
	public T peek() {
		if (size <= 0) {
			return null;
		}

		return (T) array[0];
	}

	@Override
	public T poll() {
		if (size <= 0) {
			return null;
		}

		T value = (T) array[0];

		size--;

		System.arraycopy(array, 1, array, 0, size);
		array[size] = null;

		return value;
	}

	@Override
	public void offer(T value) {
		if (size == MAX_SIZE) {
			throw new IllegalArgumentException(String.format("Maximum stack size: %s has been reached.", MAX_SIZE));
		}

		array[size++] = value;
	}

	@Override
	public int size() {
		return size;
	}
}

Kolejka, queue, FIFO – zadania do samodzielnego rozwiązania

Jeżeli ciągle szukasz wyzwań i chcesz poćwiczyć zadania z wykorzystaniem kolejki – poniżej masz kilka inspiracji.

• implementacja kolejki z listą wskaźnikową;
• implementacja Deque – listy z możliwością dodawania elementów na początku i na końcu.

Rozwiązania zadań i inne przykłady kodu znajdziesz na repozytorium github.

Wynikami swojej pracy możesz jak zawsze podzielić się na grupie.

Kolejka, queue, FIFO – podsumowanie

To już koniec serii na temat FIFO i LIFO. Jestem przekonany, że jeżeli udało Ci się przerobić przynajmniej połowę pokazanych tu przykładów, to kolejki i stosy nie będą stanowiły dla Ciebie już żadnego problemu 🙂

Dodatkowe materiały:

• kurs java
• Struktury danych – podstawy algorytmów
• Jak się uczyć programowania? Sprawdzone sposoby na naukę nowych rzeczy i pogłębianie wiedzy.