Kolejka

REKLAMA

Kwalifikacja INF.03. Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych. Część 3. Programowanie aplikacji internetowych. Podręcznik do nauki zawodu technik informatyk i technik programista
−15%38,16 zł
C++. Algorytmy i struktury danych
129,00 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ż

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

Sortowanie przez scalanie – rekurencyjny algorytm sortowania wykorzystujący metodę dziel i zwyciężaj.

→ Czytaj całość

Drzewo decyzyjne – metoda graficzna wspierająca podejmowanie decyzji, jak również model stosowany w uczeniu maszynowym do klasyfikacji lub regresji.

Podejmowanie decyzji z wykorzystaniem drzewa decyzyjnego odbywa się poprzez odpowiadanie na kolejne pytania. Pojedyncze pytanie musi być proste i dotyczyć jednego konkretnego atrybutu. Pytania ułożone są w strukturę hierarchiczną – wybór następnego pytania (lub końcowej decyzji) zależy od odpowiedzi udzielonej na poprzednie.

Proste drzewo decyzyjne może być w pełni zaprojektowane już przy tworzeniu programu i zaimplementowane w kodzie np. za pomocą instrukcji warunkowych. W uczeniu maszynowym drzewo jest generowane automatycznie na podstawie próbek ze zbioru uczącego.

→ Czytaj całość
Polityka prywatnościKontakt