Kolejka fifo

powrót

Kolejka fifo to abstrakcyjna struktura danych, która jest wykorzystywana w wielu algorytmach, między innymi w algorytmie grafowym (BFS) - przeszukiwanie wszerz. Skrót fifo oznacza first in first out - pierwszy na wejściu jest pierwszym na wyjściu. Strukturę danych możemy porównać do zwykłej kolejki w sklepie. Osoba, która jako pierwsza ustała w kolejce, będzie obsłużona jako pierwsza. Każda następna, która dołączyła do kolejki, będzie obsługiwana jako następna. Nowa osoba zawsze staje na końcu kolejki i będzie obsłużona jako ostatnia.

W omawianej strukturze możemy wyróżnić następujące czynności:

• push_back(element) - dodanie elementu na koniec kolejki
• pop_back() - usunięcie "obsłużenie" elementu z początku kolejki
• size() - liczba elementów w kolejce
• first() - wartość pierwszego elementu w kolejce
• last() - wartość ostatniego elementu w kolejce

Pierwsza implementacja tej struktury będzie najprostszą z możliwych. Napiszemy ją z wykorzystaniem tablicy statycznej. Ustawimy sobie dwa liczniki, $$p$$ i $$k$$ (początek i koniec kolejki). Dodając element do kolejki przesuniemy licznik $$k$$ o jeden w prawo, usuwając element przesuniemy licznik $$p$$ o jeden w prawo. W rezultacie elementy z komórki tablicy nie będą usuwane tylko licznik będzie przesuwany na następny index komórki.

Zalety:

• prostota implementacji
• szybkość działania

Wady:

• ograniczenia co do wielkości kolejki - z góry musimy znać jej rozmiar
• elementy nie są fizycznie usuwane z pamięci

Statyczna implementacja kolejki:

#include<iostream>
//maksymalna liczba wszystkich elementów w kolejce - usuniętych lub nie
#define MAX 1000 
#define ERROR 1000000000 //ustalamy taką wartość, która nie wystąpi jako element fifo
using namespace std;

int tab[MAX], p = 0, k = 0;

inline bool pop_back() //usunięcie elementu
{
	if(p==k) //jesli kolejka jest pusta
		return 0;
	
	++p;
	return 1;
}

inline bool push_back(int element)
{
	if(k==MAX) //jesli nie ma już miejsca w tablicy
		return 0;
	
	tab[k++] = element;
	return 1;
}

inline unsigned int size()
{
	return k-p; //liczba elementów w kolejce
}

inline int first()
{
	if(p==k) //jesli kolejka jest pusta
		return ERROR;
		
	return tab[p];
}

inline int last()
{
	if(p==k) //jesli kolejka jest pusta
		return ERROR;
		
	return tab[k-1];
}
int main()
{
	if(!push_back(12))cout<<"Kolejka przepełniona\n";
	if(!push_back(22))cout<<"Kolejka przepełniona\n";
	if(!push_back(32))cout<<"Kolejka przepełniona\n";
	
	int pom = first();
	if(pom!=ERROR) cout<<"Pierwszy element w kolejce: "<<pom<<endl;
	
	pom = last();
	if(pom!=ERROR) cout<<"Ostatni element w kolejce: "<<pom<<endl;
	
	cout<<"Liczba elementów w kolejce: "<<size()<<endl;
	
	if(!pop_back()) cout<<"Kolejka jest już pusta\n";
	if(!pop_back()) cout<<"Kolejka jest już pusta\n";
	
	cout<<"Liczba elementów w kolejce: "<<size()<<endl;
	
	if(!pop_back()) cout<<"Kolejka jest już pusta\n";
	if(!pop_back()) cout<<"Kolejka jest już pusta\n";

	return 0;
}

Out:

Pierwszy element w kolejce: 12
Ostatni element w kolejce: 32
Liczba elementów w kolejce: 3
Liczba elementów w kolejce: 1
Kolejka jest już pusta
 

Dynamiczna implementacja kolejki fifo wykorzystuje listę jednokierunkową. Usunięcie elementu z kolejki powoduje fizyczne usunięcie elementu z pamięci. Pamięć na następny element jest przydzielana dynamicznie.

Zalety:

• nie trzeba znać długości kolejki, jest ona tworzona w miarę potrzeb
• niewykorzystane elementy są usuwane na bieżąco
• prostota implementacji

Wady:

• nieco wolniejsze działanie od statycznego odpowiednika

Program zaimplementowany obiektowo: 

//wwww.algorytm.edu.pl
#include<iostream>
using namespace std;

class kolejka{
	public:
		kolejka(){poczatek=koniec=0;f=1;}
		~kolejka() //zwolnienie pamięci dla elementów kolejki
		{
			while(koniec-poczatek>0){
				el = p;
				p = p->nastepny;
				delete el;
				++poczatek;	
			} 
			if(!f)
				delete p;
		}
		unsigned int size(){return koniec-poczatek;}//liczba elementów w kolejce
		void push_back(int x)//dodanie elementu na koniec kolejki
		{
			if(f)//jesli pierwszy element wrzucamy do kolejki
			{
				k = new wezel;    //utworzenie elementu ostatniego
				k -> element = x; //przypisanie do niego wartosci
				p = new wezel; 		//utworzenei elemntu pierwszego
				p -> nastepny = k;  //element pierwszy wskazuje na ostatni
				f = 0;
			}
			else
			{
				el = new wezel;    //utworzenie nowego elementu kolejki
				el -> element = x;	//przypisanie do niego wartosci
				k -> nastepny = el;	//ostatni dotychczas element wskazuje na utworzony
				k = el;				//element utworzony staje się ostatnim
			}
			++koniec;
		}
		int pop_back()// usunięcie pierwszego elementu z kolejki i zwrócenie 1 gdy ok, 0 - gdy nie ma nic do usunięcia
		{
			if(koniec-poczatek==0)return 0; //gdy nie ma nic w kolejce zwracamy 0
			el = p;
			p = p->nastepny; //przejscie na następny element kolejki
			delete el;		//usunięcie pierwszego elementu w kolejce
			++poczatek;
      return 1;
		}
		int first() //zwrócenie pierwszego elementu w kolejce
		{
			return p->nastepny->element;
		}
		int last() //wyznaczenie ostatniego elementu w kolejce
		{
			return k->element;
		}
	private:
		bool f; //flaga okreslająca, czy w kolejce cos już się pojawiło
		struct wezel{
			int element;
			wezel *nastepny;
		};
		unsigned int poczatek, koniec; //początek i koniec kolejki - index
		wezel *p,*k,*el; //poczatek, koniec, 
};

int main()
{
	kolejka queue; //utworzenie kolejki
	
	queue.push_back(23); //dodaj do kolejki 23
	queue.push_back(43); //dodaj do kolejki 43
	queue.push_back(45); //dodaj do kolejki 45
	cout<<"Liczba elementów w kolejce: "<<queue.size()<<endl; //mamy 3 elementy
	cout<<"Pierwszy element kolejce: "<<queue.first()<<endl; //wypisanie 23
	cout<<"Ostatni element kolejce: "<<queue.last()<<endl;   //wypisanie 45
	queue.pop_back(); //usunięcie 23
	queue.pop_back(); //usunięcie 43
	cout<<"Liczba elementów w kolejce: "<<queue.size()<<endl; //mamy 1 element
	queue.pop_back(); //usunięcie 45
	cout<<"Liczba elementów w kolejce: "<<queue.size()<<endl; //0 elementów w kolejce
	if(!queue.pop_back())
		cout<<"Kolejka jest pusta, nie ma nic do usuwania"<<endl;
		
	return 0;
}

Out:

Liczba elementów w kolejce: 3
Pierwszy element kolejce: 23
Ostatni element kolejce: 45
Liczba elementów w kolejce: 1
Liczba elementów w kolejce: 0
Kolejka jest pusta, nie ma nic do usuwania

Omawiając daną strukturę danych nie można pominąć kolejkę zaimplementowaną w STL-u. Użycie tej struktury jest bardzo przyjemne oraz wydajne. Kolejkę queue omówiono tutaj.