Memòria en pila (estructura de dades)
En informàtica, la memòria en pila[1] és una estructura de dades seqüencial (que conté elements ordenats) amb aquestes restriccions d'accés:
- només es pot afegir elements al cim de la pila
- només es pot treure elements del cim de la pila
Per analogia amb objectes quotidians, una operació apilar equivaldria a posar un plat sobre una pila de plats, i una operació desempilar a retirar-lo.
Les operacions habituals sobre una pila són
Les habituals dels contenidors
(vegeu l'article contenidor):
- Una operació per comprovar quan una pila està buida.
- Una operació per obtenir el nombre d'elements que conté la pila
Les específiques d'una pila
- Un constructor que crea una pila buida
- Una operació per afegir un nou element al cim de la pila
- Una operació per obtenir l'element del cim de la pila
- Una operació per treure l'element del cim de la pila
Implementació
Pila dinàmica d'enters feta amb C++
Executant el següent codi podem veure un menú amb les opcions:
Problema 1: Apilar enters amb un menú:
- Empilar un enter
- Veure el cim de la pila
- Desempilar un enter
- Veure si la pila es buida
Problema 2: monitorització de la memòria:
- Bucle que va empilant nombres aleatoris, i va dient quants n'ha empilat. Executar el programa, i monitoritzar la memòria, de forma que es pugui veure que el programa va agafant memòria
- Sortir del programa
<source lang=cpp> /*
* Program name: Pila dinàmica d'enters (Problema 1 i 2) * File name: nvidal_pila_dinamica.cpp * Description: Pila dinàmica d'enters utilitzant classes. * Les piles serveixen per exemple: Quan un programa s'esta executant * necessita anar guardant les variables locals per no perdre-les (quan canvia de context), * per tant ha de fer servir una pila dinàmica perquè pot anar creixent il·limitadament. * Pila dinàmica d'enters (Problema 1 i 2) de Narcís Vidal i Tulsà està subjecta a una llicència de * Reconeixement-CompartirIgual 3.0 No adaptada de Creative Commons. * Els permisos addicionals als d'aquesta llicència es poden trobar a nvidal(arroba(@))tulsa.eu. */
- include <cstdio>//printf
- include <iostream>//minim c++
using namespace std;
class Node{ private:
int valor; //dades Node *seguent; //punter
public:
void SetValor(int v){valor=v;} //Modificador del valor
void SetSeguent(Node *seg){seguent=seg;} //Modificador del punter
Node(){valor=0,seguent=NULL;} //constructor sempre és diu igual que la classe
friend class Pila; //Classe amiga que pot accedir a les propietats privades
};
typedef Node *pnode; //Definim una nou tipus de dades del tipus: punter a Node
class Pila{ private:
pnode ultim;
public:
Pila(); //Constructor void Empilar(int v); //Posa un element a la pila int Cim(); //Et retorna l'ultim element de la pila void Desempilar(); //Treu un element de la pila bool Buida(); //Retorna si la pila es plena o buida ~Pila(); //Destructor
};
int Pila::Cim(){
return ultim->valor; //Retorna el últim valor
}
Pila::Pila(){
ultim=NULL; //el constructor l'únic que ha de fer és posar el primer apuntant a NULL
}
void Pila::Empilar(int v){
pnode aux; aux=new Node(); //aixi creem el punter a un tipus Node aux->SetValor(v); //posem el valor que ens han passat aux->SetSeguent(ultim); //deixara d'apuntar a NULL per apuntar a l'ultim de la pila ultim=aux; //li diem a la variable ultim el nou punter que hem inserit
}
void Pila::Desempilar(){
pnode aux; //les variables estatiques quan s'ecava d'executar la funcio és destrueixen i alliberen l'espai de memòria automaticament
if(!Buida()){ //si Buida es fals executa sino no fa res per que no peti si estigues buida
aux=ultim;
ultim=aux->seguent;
delete aux; //alliberem la memoria de del node que aviem creat abans
cout << "\nDesempilat correctament\n" << endl;
}
else{ cout << "La pila es buida " << endl; }
}
bool Pila::Buida(){
if(ultim==NULL) {return true;}
else {return false;}
}
Pila::~Pila(){ //el destructor amb memòria dinamica s'ha de fer per alliberar la memòria quan ja no ho necessitem
while (!Buida()){
Desempilar();
}
}
void menu(){
cout << "\n\n\n\nProblema 1: Apilar enters amb un menú"; cout << "\n\n\tEscull una de les opcions:\n\t1. Empilar un enter.\n\t2. Veure el cim de la pila"; cout << "\n\t3. Desempilar un enter.\n\t4. Veure si la pila es buida.\n"; cout << "\n\nProblema 2: monitorització de la memòria;"; cout << "\n\n\t5. Bucle que va empilant nombres aleatoris, i va dient\n\tquants n'ha empilat. Executar el programa, i monitoritzar la\n\tmemòria, de forma que es pugui veure que el programa va agafant memòria."; cout << "\n\n\t6. Sortir del programa.\n";
}
void llegeix_opcio(int *opcio){
scanf("%d",opcio);
}
int sortida(){
printf("\nPer sortir prem alguna tecla\n");
//system("PAUSE"); si fos en windows
return (0);
}
int main(){
int opcio, numero, cont=0;
Pila x;
do{
menu();
llegeix_opcio(&opcio);
switch (opcio){
case 1: cout << "\nQuin numero vols empilar\n";
cin >> numero;
x.Empilar(numero);
cout << "\nEmpilat correctament\n";
break;
case 2: if(!x.Buida()){numero = x.Cim();
cout << "\nEl cim de la pila conte el numero\n" << x.Cim() << endl;}
else cout << "\n No pots veure el cim la pila es buida" << endl;
break;
case 3: x.Desempilar();
break;
case 4: if(x.Buida()) cout << "\nLa pila es buida\n";
else cout << "\nLa pila es plena\n";
break;
case 5://Per mirar com puja la memoria ocupada pel nostre programa col·lapsara l'ordinador
while (cont<300000){
x.Empilar(20);
cont++;
cout << "\n empilant vegada " << cont;
}
//Per fer baixar la memoria
while (cont>1){
x.Desempilar();
cont--;
cout << "\n desempilant vegada " << cont;
}
break;
case 6: sortida();
break;
default: printf("\nOpcio equivocada\n");
}
}while (opcio!=6);
} </source>
Referències
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Memòria en pila
- ↑ «memòria en pila». Cercaterm. TERMCAT, Centre de Terminologia.