Memòria en pila (estructura de dades)

De Viquipèdia
(S'ha redirigit des de: Pila (estructura de dades))
Dreceres ràpides: navegació, cerca
Representació simple d'una pila (amb les opcions apilar/desempilar de la biblioteca STL

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[modifica | modifica el codi]

Les habituals dels contenidors[modifica | modifica el codi]

(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 | modifica el codi]

  • 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 | modifica el codi]

Pila dinàmica d'enters feta amb C++[modifica | modifica el codi]

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
/*
 * 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 é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'ú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 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);
}

Referències[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Memòria en pila (estructura de dades) Modifica l'enllaç a Wikidata

Vegeu també[modifica | modifica el codi]