Pila
La primera estructura que veurem és la pila. És una estructura del tipus LIFO (Last In - First Out), que vol dir que traiem els elements de més recents a menys recents. Ens la podem imaginar com si traguéssim els plats del rentaplats, i els poséssim en una pila per passar-los a l'armari. El primer plat que podrem agafar serà l'últim que haguem posat a la pila
Per utilitzar-la, s'utilitza la classe stack, que trobem a la llibreria stack (esperable, no?). Tenim bàsicament les següents funcions:
push: Afegeix un element a la pila
pop: Elimina l'element de dalt de tot (és a dir, l'últim que hem afegit)
top: Retorna l'element de dalt
size: Ens retorna la mida
empty: Retorna true si la mida és 0, false si és diferent
Aleshores, treballar amb una pila és bastant senzill. Per afegir utilitzem push, per treure pop, per consultar top
Podem provar de fer alguna cosa. Per exemple, mirar si una expressió està ben parentitzada. És a dir, una expressió ben parentitzada es podria definir:
buit: Ben parentitzada
(expressió): Ben parentitzada
[expressió]: Ben parentitzada
{expressió}: Ben parentitzada
És a dir, un string buit seria una expressió ben parentitzada. () també. (()) també. ([]) també. ([({})]) també.
Podem veure com cada parèntesi obert té un que el tanca. Sabent això, podem utilitzar una pila per fer-ho:
bool ben_parentitzat(const string& s) {
stack<char> st;
for(int i=0;i<int(s.length());++i) {
char c=s[i];
if (c==')') {
if (s.top()!='(') return false;
s.pop();
}
else if (c==']') {
if (s.top()!='[') return false;
s.pop();
}
else if (c=='}') {
if (s.top()!='[') return false;
s.pop();
}
else s.push(c);
}
return s.empty();
}
int main() {
string s;
while(cin>>s) {
if (ben_parentitzat(s)) cout <<"SI"<<endl;
else cout<<"NO"<<endl;
}
}
És a dir, si obrim el parèntesi, l'empilem. Si el tanquem, comprovem que coincideixi amb l'últim obert i, si coincideix, vol dir que ja hem tancat l'últim, de manera que el podem treure. Si no coincideix, acabem directe. Quan acabem, si la pila està buida, vol dir que estava bé, mentre que si té contingut, vol dir que faltaven parèntesis per tancar
Sembla una estructura molt senzilla, no? Doncs té moltes utilitats. Per exemple, per programar l'algorisme DFS iteratiu fa falta una pila. També s'utilitza una pila per emmagatzemar les variables locals de les funcions, així com pel pas de paràmetres d'una funció a una altra. Per això mateix, quan fem una funció recursiva infinita, ens acaba sortint l'error "stack overflow".
Cua:
Un cop hem après què és una pila, podem mirar-nos la cua. La cua és una estructura FIFO (First In - First Out). Això vol dir que el primer element que entra és el primer que surt. Ho podem veure com la cua del super, el primer que s'hi posa és el primer en ser atès, i l'últim que s'hi posa és l'últim en ser atès (deixant de banda la gent que es cola). Les seves funcions són:
push: Afegeix un element a la cua
pop: Elimina l'element de davant (és a dir, el primer que hem afegit)
front: Retorna l'element de davant
size: Ens retorna la mida
empty: Retorna true si la mida és 0, false si és diferent
Aleshores la idea d'utilitzar una cua és que el primer element insertat és el primer que surt. Formats FIFO s'utilitzen per moltes coses. Per exemple, per programar l'algorisme DFS, que es fa a EDA, s'utilitzen cues.. O, per exemple, els fluxs de dades (cin, cout, cerr) funcionen igual, el primer que entra al flux és el primer que en surt. El mateix amb les pipes de Linux. I podríem seguir.
La classe queue la trobem a la llibreria queue (sorprenent).
Cap comentari:
Publica un comentari a l'entrada