Przejdź do zawartości

Struktury danych/Implementacje w C++/Stosy

Z Wikibooks, biblioteki wolnych podręczników.
template <class typ>  //większa uniwersalnosć - szablon
class stos
{
	typ *tab;		//do przechowywania danych użyję dyanamicznie przydzialanej pamięci
	long size;		//ile elementów możemy pomieścić w stosie
	long wybrany;	//numer pierwszego wolnego elementu

	void powiekszSie();	//jeśli braknie miejsca, stos się powiększy

public:
	stos();			//konstruktor domyślny
	stos(long rozm);//tu możemy określić ile elementów będzie można pomieścić
	~stos();		//destruktor (zwróci zaalokowaną pamięć)

	void push(typ &co);	//funkcja do umieszczania elementu na stosie
	void pop();			//funkcja do zdejmowania elementu ze stosu
	const typ& top();			//funkcja zwraca to co jest na górze stosu
};

template <class typ>
stos<typ>::stos()
{
	wybrany = 0;	//na początku stos jest pusty
	size = 10;		//na starcie dajemy możliwość wrzucenia 10 elementów
	
	tab = new typ[size];	//dynamicznie przydzielana pamięć

	if(tab == NULL)		//coś się nie powiodło przy alokacji pamięci
	{
		throw "Błąd alokcacji pamięci!";	//rzucamy wyjątek
	}
}

template <class typ>
stos<typ>::stos(long rozm)
{
	wybrany = 0;	//na stosie pusto
	size = rozm;	//ustawiamy zgodnie z zyczeniem

	tab = new typ[size];	//tak jak wyżej

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

template <class typ>
stos<typ>::~stos()
{
	delete []tab;	//zwalniamy pamięć 
}

template <class typ>
void stos<typ>::push(typ &co)
{
	if(wybrany == size)	//jeśli kończy się miejsce
		powiekszSie();	//stos się powiększa

	tab[wybrany] = co;	//umieszczamy element na stosie
}

template <class typ>
void stos<typ>::pop()
{
	wybrany --;	//nie kasujemy obiektu, ale przy wywołaniu push, i tak będzie nadpisany
}

template <class typ>
const typ& stos<typ>::top()
{
	return tab[wybrany];	//zwracamy to co jest na szczycie (wybrany wskazuje na pierwszy WOLNY element tablicy, daltego zmniejszam o 1)
        wybrany++;
}

template <class typ>
void stos<typ>::powiekszSie()
{
	typ *nowa = new typ[size + 10];		//nowa tablica jest o 10 el. większa

	for(int i=0;i<size;++i)
		nowa[i] = tab[i];	//kopiujemy starą tablicę do nowej

	delete []tab;	//starą tablicę możemy skasować

	tab = nowa;		//teraz tab pokazuje na nową, większą tablicę
	size += 10;		//trzeba zapisać o ile powiększyliśmy tablicę
}