Struktury danych/Implementacje w C++/Stosy

Z Wikibooks, biblioteki wolnych podręczników.
Przejdź do nawigacji Przejdź do wyszukiwania
 1 template <class typ>  //większa uniwersalnosć - szablon
 2 class stos
 3 {
 4 	typ *tab;		//do przechowywania danych użyję dyanamicznie przydzialanej pamięci
 5 	long size;		//ile elementów możemy pomieścić w stosie
 6 	long wybrany;	//numer pierwszego wolnego elementu
 7 
 8 	void powiekszSie();	//jeśli braknie miejsca, stos się powiększy
 9 
10 public:
11 	stos();			//konstruktor domyślny
12 	stos(long rozm);//tu możemy określić ile elementów będzie można pomieścić
13 	~stos();		//destruktor (zwróci zaalokowaną pamięć)
14 
15 	void push(typ &co);	//funkcja do umieszczania elementu na stosie
16 	void pop();			//funkcja do zdejmowania elementu ze stosu
17 	const typ& top();			//funkcja zwraca to co jest na górze stosu
18 };
19 
20 template <class typ>
21 stos<typ>::stos()
22 {
23 	wybrany = 0;	//na początku stos jest pusty
24 	size = 10;		//na starcie dajemy możliwość wrzucenia 10 elementów
25 	
26 	tab = new typ[size];	//dynamicznie przydzielana pamięć
27 
28 	if(tab == NULL)		//coś się nie powiodło przy alokacji pamięci
29 	{
30 		throw "Błąd alokcacji pamięci!";	//rzucamy wyjątek
31 	}
32 }
33 
34 template <class typ>
35 stos<typ>::stos(long rozm)
36 {
37 	wybrany = 0;	//na stosie pusto
38 	size = rozm;	//ustawiamy zgodnie z zyczeniem
39 
40 	tab = new typ[size];	//tak jak wyżej
41 
42 	if(tab == NULL)
43 	{
44 		throw "Błąd alokacji pamięci!";
45 	}
46 }
47 
48 template <class typ>
49 stos<typ>::~stos()
50 {
51 	delete []tab;	//zwalniamy pamięć 
52 }
53 
54 template <class typ>
55 void stos<typ>::push(typ &co)
56 {
57 	if(wybrany == size)	//jeśli kończy się miejsce
58 		powiekszSie();	//stos się powiększa
59 
60 	tab[wybrany] = co;	//umieszczamy element na stosie
61 }
62 
63 template <class typ>
64 void stos<typ>::pop()
65 {
66 	wybrany --;	//nie kasujemy obiektu, ale przy wywołaniu push, i tak będzie nadpisany
67 }
68 
69 template <class typ>
70 const typ& stos<typ>::top()
71 {
72 	return tab[wybrany];	//zwracamy to co jest na szczycie (wybrany wskazuje na pierwszy WOLNY element tablicy, daltego zmniejszam o 1)
73         wybrany++;
74 }
75 
76 template <class typ>
77 void stos<typ>::powiekszSie()
78 {
79 	typ *nowa = new typ[size + 10];		//nowa tablica jest o 10 el. większa
80 
81 	for(int i=0;i<size;++i)
82 		nowa[i] = tab[i];	//kopiujemy starą tablicę do nowej
83 
84 	delete []tab;	//starą tablicę możemy skasować
85 
86 	tab = nowa;		//teraz tab pokazuje na nową, większą tablicę
87 	size += 10;		//trzeba zapisać o ile powiększyliśmy tablicę
88 }