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.
Algorytm Dijkstry – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. Algorytm wymaga, aby wagi krawędzi grafu nie były ujemne. Autorem algorytmu jest holenderski naukowiec Edsger Dijkstra.
Algorytm realizuje podejście zachłanne. W każdej iteracji wybierany jest ten spośród nieodwiedzonych wierzchołków, do którego można dotrzeć najmniejszym kosztem. Po wyznaczeniu ścieżki do konkretnego wierzchołka nie zostanie ona zmodyfikowana w trakcie wykonywania dalszej części algorytmu.
Ten artykuł opisuje algorytm rozwiązujący problem wydawania reszty oparty na programowaniu dynamicznym. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego.
Istnieje również pewna modyfikacja tego algorytmu, która została opisana w osobnym artykule.
Quicksort, sortowanie szybkie – algorytm sortowania działający w średnim przypadku w czasie liniowo-logarytmicznym. Algorytm jest oparty na metodzie dziel i zwyciężaj. Nie jest to algorytm stabilny ani wykazujący zachowanie naturalne, jednak ze względu na efektywność jest algorytmem bardzo popularnym.