Struktury danych/Implementacje w C++/Kolejki

Implementacja tablicowa

template <typename type>
class Queue
{
	type* tab; // dynamicznie alokowana pamięć na tablicę cykliczną
	int size; // aktualna wielkość tablicy
	int front;// indeks tablicy wskazujący na początek kolejki
	int back; // indeks tablicy wskazujący na koniec kolejki, normalnie będzie wskazywał na pierwsze wolne pole w tablicy
	int index_add(int);// funkcja pomocnicza do obliczania indeksu
public:
	Queue(); //konstruktor domyślny tworzący kolejkę wielkości 
	Queue(int s);
	~Queue();

	void enqueue(type co); //ustawia na końcu kolejki
	type dequeue();        //usuwa z początku kolejki
	bool empty();
	bool full();
};

template <typename type>
Queue<typ>::Queue()
{
	size=10; //domyślna wielkość kolejki
	front=0; 
	back=0; 

	tab = new type[size];
	if (tab == NULL) // ewentualne zabezpieczenie przed brakiem pamięci
	{
		throw "Błąd alokacji pamięci!";
	}
}

template <typename type>
Queue<type>::Queue(int s) // konstruktor z zadaną przez nas wielkością kolejki
{
	size=s; // przypisanie przekazanej wielkości
	front=0;
	back=0;

	tab = new type[size];
	if (tab == NULL)
	{
		throw "Błąd alokacji pamięci!";
	}

}

template <typename type>
Queue<type>::~Queue()
{
	delete []tab; // zwolnienie zaalokowanej wcześniej pamięci
}

template <typename type>
void Queue<type>::enqueue(type co)
{
	if(full())
		throw "Queue jest pełna!";
	else
	{
		tab[back]=co;
		back=index_add(back);
	}
}

template <typename type>
type Queue<type>::dequeue()
{
	if(empty())
	{
		throw "Queue jest pusta!";
		return -1;
	}
	else
	{
		type tmp = tab[front];
		front = index_add(front);
		return tmp;
	}
}

template <typename type>
int Queue<type>::index_add(int i)
{
	return (i+1)%size;
}

template <typename type>
bool Queue<type>::empty()
{
	return back == front;
}

template <typename type>
bool Queue<type>::full()
{
	return index_add(back) == front;
}