Kolejka

REKLAMA Algorytmy i struktury danych z przykładami w Delphi
80,00 zł
Spring w akcji. Wydanie V
89,00 zł
Excel 2019 PL. Biblia
−30%90,30 zł
Wyrażenia regularne od podstaw
39,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ż

Metoda przyrostowa – technika projektowania algorytmów polegająca na dodawaniu do rozwiązania kolejnych elementów z danych wejściowych. Przykładem algorytmu opartego na tej metodzie jest sortowanie przez wstawianie, gdzie kolejne elementy są wstawiane do posortowanej części tablicy.

Jest to metoda prosta, jednak sprawdza się tylko dla niektórych problemów obliczeniowych.

→ Czytaj całość

Problem komiwojażera (ang. travelling salesman problem, w skrócie TSP) – problem obliczeniowy polegający na poszukiwaniu w grafie takiego cyklu, który zawiera wszystkie wierzchołki (każdy dokładnie raz) i ma jak najmniejszy koszt. Bardziej formalnie, problem komiwojażera polega na poszukiwaniu w grafie cyklu Hammiltona o najmniejszej wadze.

Problem ma liczne zastosowania w życiu codziennym. Najlepszym przykładem jest praca kuriera, który musi wyjechać z magazynu, zawieźć przesyłki w różne miejsca i wrócić do magazynu.

Nie jest znany efektywny (tj. działający w czasie co najwyżej wielomianowym) algorytm dający gwarancję znalezienia optymalnego rozwiązania problemu komiwojażera. Problem ten jest bowiem zaliczany do klasy problemów NP-trudnych. W wersji decyzyjnej (czy istnieje cykl o długości mniejszej od x) problem jest zaliczany do klasy problemów NP-zupełnych. W grafie pełnym mającym n wierzchołków liczba możliwych cykli Hammiltona wynosi aż (n-1)!/2. W praktyce sprawdzenie wszystkich możliwości jest zatem wykonalne tylko dla niewielkiej liczby wierzchołków.

→ Czytaj całość

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

→ Czytaj całość
Polityka prywatnościKontakt