Kolejka

REKLAMA

Kwalifikacja INF.03. Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych. Część 1. Projektowanie stron internetowych. Podręcznik do nauki zawodu technik informatyk i technik programista
−14%39,95 zł
Algorytmy. Ćwiczenia
34,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ż

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

Metoda Otsu – algorytm służący do binaryzacji obrazu, czyli przekształcenia obrazu w odcieniach szarości do obrazu binarnego. Metoda ta realizuje progowanie globalne – dla całego obrazu wyznaczany jest jeden próg jasności, a następnie wszystkim pikselom jaśniejszym od tego progu przypisywana jest jedna wartość, a ciemniejszym druga.

Algorytm jest oparty na analizie histogramu. Przygotowanie histogramu polega na zliczeniu pikseli w każdym możliwym odcieniu (zazwyczaj liczba odcieni wynosi 256, gdyż tyle da się zakodować w jednym bajcie). Następnie należy sprawdzić każdy możliwy próg jasności i wybrać ten, dla którego wariancja międzyklasowa jest największa (lub suma ważona wariancji wewnątrzklasowych jest najmniejsza).

Jeśli obrazem wejściowym jest obraz kolorowy, można go łatwo sprowadzić do odcieni szarości. W przypadku kolorów zakodowanych w RGB najprostszym rozwiązaniem jest uśrednienie dla każdego piksela wartości wszystkich trzech kanałów.

→ Czytaj całość

Algorytm genetycznymetaheurystyka inspirowana biologiczną ewolucją.

Pojęcie algorytmu genetycznego nie jest powiązane z żadnym konkretnym problemem obliczeniowym, algorytm ten może być wykorzystywany do rozwiązywania różnych problemów. Algorytm genetyczny nie próbuje rozwiązywać problemu w sposób analityczny, ale próbuje uzyskać jak najlepsze rozwiązania poprzez wybieranie jak najlepszych cech rozwiązań z określonej puli. Implementując algorytm genetyczny należy przedstawić potencjalne rozwiązanie problemu w postaci jakiejś struktury danych, a następnie zdefiniować operacje krzyżowania, mutacji i selekcji. Zakładamy, że z każdym kolejnym pokoleniem rozwiązania występujące w populacji będą coraz lepsze.

→ Czytaj całość
Polityka prywatnościKontakt