Memòria en pila (estructura de dades) - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for Memòria en pila (estructura de dades).

Memòria en pila (estructura de dades)

De Viquipèdia

Representació simple d'una pila (amb les opcions apilar/desempilar de la biblioteca STL
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:[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
  1. «memòria en pila». Cercaterm. TERMCAT, Centre de Terminologia.

Vegeu també

{{bottomLinkPreText}} {{bottomLinkText}}
Memòria en pila (estructura de dades)
Listen to this article