Kolejka

REKLAMA C++. Algorytmy i struktury danych
103,95 zł
Praktyczne projekty sieciowe
59,00 zł
WordPress 5 dla początkujących
−30%41,30 zł
Kubernetes. Tworzenie niezawodnych systemów rozproszonych
44,90 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: 1.

Dodano: 10 listopada 2018 11:10.

REKLAMA

Zobacz też

Ten artykuł opisuje algorytm zachłanny rozwiązujący problem wydawania reszty. Algorytm ten polega na wybieraniu zawsze największej dostępnej monety, tzn. takiej, która nie jest większa od kwoty pozostałej do wydania.

Algorytm nie zawsze znajduje rozwiązanie optymalne. Przykładowo, dla zbioru nominałów {1, 3, 4} i kwoty 6 algorytm użyje najpierw monety o nominale 4 (pozostaje do wydania kwota 2), potem monety o nominale 1 (pozostaje kwota 1) i jeszcze raz monety o nominale 1. Łącznie algorytm użyje więc trzech monet, podczas gdy rozwiązanie optymalne wymaga użycia tylko dwóch (dwie monety o nominale 3).

→ 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ść

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.

→ Czytaj całość
Polityka prywatnościKontakt