- push(ob): adaugă un obiect în vârful stivei.
- pop(): elimină obiectul din vârful stivei.
- top(): returnează o referinţă către vârful stivei fără a elimina obiectul.
- size(): returnează numărul obiectelor din stivă.
- isEmpty(): returnează true dacă stiva este vidă, altfel false.
template<typename T>
class Stiva
{
public:
Stiva(); // Constructor | Initializarea stivei
~Stiva(); // Destructor
int size() const; // Returneaza numarul elementelor din stiva
bool isEmpty() const; // Este stiva vida?
const T& top() const; // Returneaza o referinta constanta catre varf
void push(const T& ob); // Adauga un element
void pop(); // Elimina elementul din varf
private:
struct Element // Implementeaza un element de stiva
{
T data; // Informatia memorata in elementul stivei
Element * below; // Elementul anterior / dedesubt
};
Element * varf; // Varful stivei
int count; // Data membra cu care numar elementele stivei
};
Observaţi că la unele funcţii apare referinţa constantă. De ce fac asta? De ce nu returnez pur şi simplu un obiect T şi nu o referinţă? Datorită eficienţei. Atunci când returnez o referinţă nu se mai alocă, temporar (deci va fi dealocat; un overhead suplimentar), spaţiu pentru obiectul returnat sau pentru parametrul formal, deoarece pot accesa direct variabila referită. Referinţa este constantă tocmai pentru că nu vreau să modific din greşeală argumentul sau obiectul returnat, plus că nu aş putea transmite valori concrete (de ex: 1, 2, 'c', 4.6, etc.) funcţiei push(), dacă referinţa nu ar fi constantă.
Iniţializarea Stivei
Iniţializarea stivei presupune crearea stivei vide, adică elementul varf indică NULL (nullptr). Pentru cei care folosiţi compilatoare noi, cum ar fi cel din Visual Studio, folosiţi nullptr în loc de NULL, deoarece NULL este doar un simplu macro, este 0, este un întreg şi nu reprezintă concret o adresă inexistentă. Stiva este iniţializată în constructor:template<typename T> Stiva<T>::Stiva()
{
varf = nullptr; // stiva vida
count = 0; // zero elemente
}Stiva Vidă
Stiva este vidă atunci când varf este NULL, deci algoritmul va fi următorul:template<typename T> bool Stiva<T>::isEmpty() const
{
return varf == nullptr;
}
Calificatorul const informează compilatorul că respectiva funcţie nu modifcă obiectele stivei, nu le modifica datele membre.
Numărul de elemente dintr-o Stivă
Pur şi simplu returnăm valoarea membrului count.template<typename T> int Stiva<T>::size() const
{
return count;
}Adăugarea unui element în Stivă
Algoritmul este simplu. Aloc memorie pentru un obiect de tip Element -> Scriu informaţia în obiect -> Predecesorul acestui obiect este varf -> Noul element devine varf. Se incrementează count. Funcţia push() va implementa această operaţie.template<typename T> void Stiva<T>::push(const T& ob)
{
if(isEmpty()) // Daca stiva este vida
{
varf = new Element;
varf->data = ob;
varf->below = nullptr; // Este baza! Primul element adaugat
count = 1;
}
else
{
Element * p = new Element;
p->data = ob;
p->below = varf; // Dedesubt se afla fostul varf
varf = p; // p devine noul varf
++count; // S-a mai adaugat un element
}
}Eliminarea unui element din Stivă
Se poate elimina numai elementul din vârf. Se salvează adresa vârfului -> Elementul dedesubt devine vârf -> Se eliberează memoria fostului vârf. Se decrementează count. Funcţia pop() va implementa această operaţie.template<typename T> void Stiva<T>::pop()
{
// Daca stiva este vida, genereaza o exceptie
if(isEmpty()) throw "Eroare! Stiva Vida!";
Element * q = varf; // Salvez varful
varf = varf->below; // Elementul anterior devine noul varf
delete q;
--count; // S-a mai eliminat un element
}Obţinerea elementului din vârful Stivei
Se returnează o referinţă constantă către varf->data.template<typename T> const T& Stiva<T>::top() const
{
if(isEmpty()) throw "Eroare! Stiva Vida!";
return varf->data;
}Eliberarea spaţiului de memorie ocupat de Stivă
Se distruge pe rând fiecare element al stivei. De asta se va ocupa destructorul clasei.template<typename T> Stiva<T>::~Stiva()
{
while(varf != nullptr)
{
Element * q = varf;
varf = varf->below;
delete q;
}
}
Dacă aveţi probleme cu nullptr, atunci folosiţi NULL. De asemenea vă recomand să folosiţi Visual Studio.
În continuare vă propun să creaţi un nou fişier Stiva.h (header) şi să-l adăugaţi la proiectul vostru, după care în fişierul main (unde aveţi funcţia main) să adăugaţi, la început, directiva: #include "Stiva.h". Adăugaţi următorul cod în Stiva.h:
template<typename T>
class Stiva
{
public:
// Constructor | Initializarea stivei
Stiva() {
varf = nullptr; // stiva vida
count = 0; // zero elemente
}
~Stiva(); // Destructor
int size() const { return count; } // Returneaza numarul elementelor din stiva
bool isEmpty() const { return varf == nullptr; } // Este stiva vida?
const T& top() const { // Returneaza o referinta constanta catre varf
if(isEmpty()) throw "Eroare! Stiva Vida!";
return varf->data;
}
void push(const T& ob); // Adauga un element
void pop(); // Elimina elementul din varf
private:
struct Element // Implementeaza un element de stiva
{
T data; // Informatia memorata in elementul stivei
Element * below; // Elementul anterior / dedesubt
};
Element * varf; // Varful stivei
int count; // Data membra cu care numar elementele stivei
};
template<typename T> void Stiva<T>::push(const T& ob)
{
if(isEmpty()) // Daca stiva este vida
{
varf = new Element;
varf->data = ob;
varf->below = nullptr; // Este baza! Primul element adaugat
count = 1;
}
else
{
Element * p = new Element;
p->data = ob;
p->below = varf; // Dedesubt se afla fostul varf
varf = p; // p devine noul varf
++count; // S-a mai adaugat un element
}
}
template<typename T> void Stiva<T>::pop()
{
// Daca stiva este vida, genereaza o exceptie
if(isEmpty()) throw "Eroare! Stiva Vida!";
Element * q = varf; // Salvez varful
varf = varf->below; // Elementul anterior devine noul varf
delete q;
--count; // S-a mai eliminat un element
}
template<typename T> Stiva<T>::~Stiva()
{
while(varf != nullptr)
{
Element * q = varf;
varf = varf->below;
delete q;
}
}
PROBLEMĂ: Într-o stivă sunt memorate numere din intervalul \([1, 10]\). Să se elimine numerele pare.
Deoarece numai informaţia din vârf poate fi prelucrată, pentru a ajunge la un anumit element trebuie eliminate toate elementele până la acel element. În acest caz, pentru a nu pierde informaţia din celelalte elemente (aici, numerele impare), voi descărca elementele impare într-o stivă de rezervă (temp), iar după ce voi scăpa de numerele pare, voi încărca numerele impare din stiva de rezervă înapoi în stiva iniţială.
#include <iostream>
#include "Stiva.h"
using namespace std;
int main()
{
Stiva<int> st; // Voi memora intregi | int
Stiva<int> temp; // Stiva de rezerva in care voi memora numerele impare
for(int i = 1; i <= 10; i++)
st.push(i); // Adaug cele zece numere
while(!st.isEmpty()) // Cat timp stiva nu este vida
{
if(st.top() % 2 == 0)
st.pop(); // Daca este par, il elimin
else
{
temp.push(st.top()); // Salvez numarul impar
st.pop();
}
}
// Acum incarc numerele impare inapoi in stiva st
while(!temp.isEmpty())
{
st.push(temp.top());
temp.pop();
}
// Acum afisez stiva st
while(!st.isEmpty())
{
cout << st.top() << '\n';
st.pop();
}
system("PAUSE");
return 0;
}
Output:
9 7 5 3 1
Trebuie să ştiţi că Standard Template Library (STL) implementează o structură de tip stivă în clasa stack, ce se găseşte în headerul stack. Are aceeiaşi membri (isEmpty() este empty()) ca şi clasa definită de mine, singura diferenţa fiind că operaţiile top() şi pop() pentru o stivă vidă sunt nedefinite, adică nu se generează o excepţie (aşa cum am făcut eu). Deci este responsabilitatea programatorului pentru a se asigura că nu aplică acele operaţii pe o stivă vidă.
#include <stack> using std::stack; stack<int> myStack;
Niciun comentariu:
Trimiteți un comentariu
Rețineți: Numai membrii acestui blog pot posta comentarii.