Memòria en pila (estructura de dades)
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
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); }
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.
Vegeu també
- Biblioteca STL
- Cues
- Arbres