Memòria en pila (estructura de dades)
Aparença
(S'ha redirigit des de: Pila (estructura de dades))
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/29/Data_stack.svg/220px-Data_stack.svg.png)
La memòria en pila en informàtica és una estructura de dades seqüencial (que conté elements ordenats) amb aquestes restriccions d'accés:[1]
- 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
[modifica]Les habituals dels contenidors
[modifica](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
[modifica]- 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ó
[modifica]Pila dinàmica d'enters feta amb C++
[modifica]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: monitoratge de la memòria:
- Bucle que va empilant nombres aleatoris, i va dient quants n'ha empilat. Executar el programa, i monitorar la memòria, de forma que es pugui veure que el programa va agafant memòria
- Sortir del programa
/*
* 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'està 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 es 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'últim 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(); //així 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'últim 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 automàticament
if(!Buida()){ //si Buida es fals executa sino no fa res perquè no peti si estigues buida
aux=ultim;
ultim=aux->seguent;
delete aux; //alliberem la memòria del node que havíem 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: monitoratge 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 monitorar 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);
}
Referències
[modifica]- ↑ «memòria en pila». Cercaterm. TERMCAT, Centre de Terminologia.