miniatura|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); }
Referències
Vegeu també Biblioteca STL Cues Arbres
Categoria:Dades informàtiques Categoria:Tipus abstracte de dades