Memòria en pila (estructura de dades)

Representació simple d'una pila (amb les opcions apilar/desempilar de la biblioteca STL

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:

• 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: 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);
}

Vegeu també

• Biblioteca STL
• Cues
• Arbres