Kolejka (ang. Queue) – struktura danych, w której elementy pobierane są z początku, a dodawane na końcu. Z kolejki można zatem pobrać tylko ten element, który był dodany najwcześniej. Kolejka bywa określana również jako kolejka FIFO (z ang. First In, First Out), w odróżnieniu od kolejki LIFO, czyli stosu.
W tej sekcji przedstawiona jest przykładowa implementacja w języku C++ kolejki przechowującej liczby typu int. Opis ten zakłada znajomość treści zaprezentowanych w artykule stos. Podobnie jak tamten, opis ten jest adresowany przede wszystkim do osób początkujących.
Tak jak w przypadku stosu, musimy mieć strukturę zawierającą liczbę i wskaźnik do kolejnego elementu. Nazwijmy tę strukturę ElementKolejki. W funkcji main będziemy przechowywać tym razem nie jeden, ale dwa wskaźniki: do pierwszego (czyli dodanego najwcześniej) i ostatniego (dodanego najpóźniej) elementu kolejki. Początkowo wartości te będą ustawione na 0 (pusta kolejka). Funkcja pobierająca element kolejki będzie bardzo podobna do funkcji pobierającej element ze stosu. Jedyna różnica w działaniu tej funkcji wystąpi wtedy, gdy pobierzemy ostatni element – wtedy będziemy musieli dodatkowo ustawić na 0 wskaźnik do ostatniego elementu kolejki. W kodzie źródłowym będzie to wyglądać następująco:
struct ElementKolejki { int liczba; ElementKolejki* nastepny; }; int pobierzZKolejki(ElementKolejki* &poczatek, ElementKolejki* &koniec) { int liczba = poczatek->liczba; ElementKolejki* doUsuniecia = poczatek; poczatek = poczatek->nastepny; delete doUsuniecia; if (poczatek == 0) { koniec = 0; } return liczba; };
Inaczej będzie natomiast wyglądała funkcja dodająca element. W przypadku stosu nowy element był dodawany na początku, tutaj zaś – na końcu. Algorytm ten będzie wyglądał następująco:
Kod źródłowy tej funkcji wygląda następująco:
void dodajDoKolejki(ElementKolejki* &poczatek, ElementKolejki* &koniec, int liczba) { ElementKolejki* nowy = new ElementKolejki(); nowy->liczba = liczba; nowy->nastepny = 0; if (koniec == 0) { poczatek = nowy; } else { koniec->nastepny = nowy; } koniec = nowy; }
Pełny przykład programu zaprezentowano poniżej. Zawiera on także funkcję wypisującą zawartość kolejki – działa ona tak samo, jak funkcja wypisująca zawartość stosu. Warto zauważyć, że program ten nie zawiera zabezpieczeń przed usuwaniem elementu z pustej kolejki. Aby to osiągnąć, trzeba by funkcję usuwającą element obłożyć warunkiem if (poczatek != 0).
#include<iostream> using namespace std; struct ElementKolejki { int liczba; ElementKolejki* nastepny; }; void dodajDoKolejki(ElementKolejki* &poczatek, ElementKolejki* &koniec, int liczba) { ElementKolejki* nowy = new ElementKolejki(); nowy->liczba = liczba; nowy->nastepny = 0; if (koniec == 0) { poczatek = nowy; } else { koniec->nastepny = nowy; } koniec = nowy; } int pobierzZKolejki(ElementKolejki* &poczatek, ElementKolejki* &koniec) { int liczba = poczatek->liczba; ElementKolejki* doUsuniecia = poczatek; poczatek = poczatek->nastepny; delete doUsuniecia; if (poczatek == 0) { koniec = 0; } return liczba; }; void wypiszKolejke(ElementKolejki* &poczatek) { ElementKolejki* aktualny = poczatek; while (aktualny != 0) { cout << aktualny->liczba << " "; aktualny = aktualny->nastepny; } cout << "\n"; }; int main() { cout << "Kolejka: \n"; ElementKolejki* poczatek = 0; ElementKolejki* koniec = 0; dodajDoKolejki(poczatek, koniec, 2); dodajDoKolejki(poczatek, koniec, 5); dodajDoKolejki(poczatek, koniec, 7); wypiszKolejke(poczatek); int pobrane = pobierzZKolejki(poczatek, koniec); cout << "Pobrano: " << pobrane << "\n"; wypiszKolejke(poczatek); dodajDoKolejki(poczatek, koniec, 6); wypiszKolejke(poczatek); system("pause"); // Czyszczenie pamieci while (poczatek != 0) { pobierzZKolejki(poczatek, koniec); } return 0; }
Dodano: 10 listopada 2018 11:10.
Rekurencja (inaczej rekursja) – odwołanie się funkcji lub definicji do samej siebie. Mówiąc inaczej, podejście rekurencyjne polega na tym, że rozwiązanie problemu wyraża się za pomocą rozwiązania tego samego problemu dla mniejszych danych wejściowych. Stosowanie rekurencji jest charakterystyczne dla algorytmów projektowanych metodą dziel i zwyciężaj.
Typowym problemem, dla którego można zastosować rekurencję, jest obliczanie silni. Przypomnijmy, że silnia z n jest zdefiniowana jako n!=1×2×…×n. Funkcja ta może być równoważnie zapisana jako:
n!=(n−1)!×n, dla n>0,
n!=1, dla n=0.
W powyższym przykładzie górny wiersz jest ogólnym równaniem rekurencji, zaś dolny wiersz jest wartością brzegową. W języku C++ powyższa funkcja byłaby zapisana w poniższy sposób.
int silnia(int n) { if (n > 0) { return n * silnia(n-1); } else { return 1; } };
Przekształcenie postaci rekurencyjnej funkcji do postaci zwartej (tzn. takiej, która nie zawiera odwołania do samej siebie) jest określane jako rozwiązanie rekurencji. Metody rozwiązywania rekurencji są dostępne między innymi w książkach podanych w bibliografii.
Algorytmy stosujące rekurencję są zazwyczaj proste w implementacji. Jednocześnie wiążą się one z pewnymi problemami. Przy podejściu rekurencyjnym ta sama funkcja jest wywoływana wielokrotnie, co zużywa pamięć operacyjną (w skrajnych przypadkach może to spowodować przepełnienie stosu).
Zanieczyszczenie Giniego (ang. Gini Impurity) – miara niejednorodności danego zbioru wyrażająca się wzorem:
$$G = ∑↙{n} p_n (1-p_n),$$gdzie pn jest prawdopodobieństwem przynależności elementu do klasy n, czyli liczbą elementów danej klasy podzieloną przez liczbę elementów całego zbioru. Jeśli wszystkie elementy zbioru należą do tej samej klasy, zanieczyszczenie Giniego jest równe 0.
Zanieczyszczenia Giniego nie należy mylić ze współczynnikiem Giniego. Są to miary służące do wyrażania zupełnie innych rzeczy. Współczynnik Giniego określa nierównomierność rozkładu i jest wykorzystywany między innymi do liczbowego wyrażania nierówności w dochodach danego społeczeństwa.
Kolejka (ang. Queue) – struktura danych, w której elementy pobierane są z początku, a dodawane na końcu. Z kolejki można zatem pobrać tylko ten element, który był dodany najwcześniej. Kolejka bywa określana również jako kolejka FIFO (z ang. First In, First Out), w odróżnieniu od kolejki LIFO, czyli stosu.