Kolejka

REKLAMA

Kwalifikacja INF.02. Administracja i eksploatacja systemów komputerowych, urządzeń peryferyjnych i lokalnych sieci komputerowych. Część 3. Lokalne sieci komputerowe. Podręcznik do nauki zawodu technik informatyk
−25%29,92 zł

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.

Implementacja

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:

  1. Utwórz nową strukturę ElementKolejki,
  2. Jako element danej struktury przypisujemy liczbę, którą chcemy dodać do kolejki,
  3. Wskaźnik do następnego elementu ustawiamy na 0 (element ten ma być na końcu),
  4. Jeśli kolejka była pusta, ustaw wskaźnik początku kolejki na nowy element. W przeciwnym razie, ustaw wskaźnik w ostatnim elemencie kolejki na nowy element,
  5. Ustaw wskaźnik końca kolejki na nowy element.

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;
}
Ocena: +1 Tak Nie
Liczba głosów: 3.

Dodano: 10 listopada 2018 11:10.

REKLAMA

Zobacz też

Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).

→ Czytaj całość

2-opt, algorytm 2-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Jest to szczególny przypadek algorytmu k-optymalnego.

Algorytm 2-opt nie służy do wyznaczania trasy, a jedynie do ulepszania jej. Samą trasę można wyznaczyć np. za pomocą algorytmu najbliższego sąsiada. Algorytm może być wykorzystany do ulepszenia algorytmu genetycznego – w ten sposób powstanie algorytm memetyczny.

→ Czytaj całość

Symulowane wyżarzanie – jedna z technik projektowania algorytmów heurystycznych (metaheurystyka). Cechą charakterystyczną tej metody jest występowanie parametru sterującego zwanego temperaturą, który maleje w trakcie wykonywania algorytmu. Im wyższą wartość ma ten parametr, tym bardziej chaotyczne mogą być zmiany. Podejście to jest inspirowane zjawiskami obserwowanymi w metalurgii – im większa temperatura metalu, tym bardziej jest on plastyczny.

Jest to metoda iteracyjna: najpierw losowane jest pewne rozwiązanie, a następnie jest ono w kolejnych krokach modyfikowane. Jeśli w danym kroku uzyskamy rozwiązanie lepsze, wybieramy je zawsze. Istotną cechą symulowanego wyżarzania jest jednak to, że z pewnym prawdopodobieństwem może być również zaakceptowane rozwiązanie gorsze (ma to na celu umożliwienie wyjście z maksimum lokalnego).

Prawdopodobieństwo przyjęcia gorszego rozwiązania wyrażone jest wzorem e(f(X)−f(X'))/T (rozkład Boltzmanna), gdzie X jest poprzednim rozwiązaniem, X' nowym rozwiązaniem, a f funkcją oceny jakości – im wyższa wartość f(X), tym lepsze rozwiązanie. Ze wzoru można zauważyć, że prawdopodobieństwo przyjęcia gorszego rozwiązania spada wraz ze spadkiem temperatury i wzrostem różnicy jakości obu rozwiązań.

→ Czytaj całość
Polityka prywatnościKontakt