Stack
stack.png

Uno stack (pila) è una struttura dati di tipo LIFO (Last In First Out), dove l'ultimo elemento inserito è il primo ad essere estratto. Essa è costituita da un'insieme di elementi che possiede due operazioni fondamentali:

  • push: inserisce un elemento nello stack
  • pop: preleva l'ultimo elemento inserito

Uno stack può essere immaginato come una pila di oggetti dove questi vengono messi uno sopra l'altro. Può essere prelevato solo l'elemento che sta in cima alla pila, ovvero l'ultimo elemento inserito.

stack_example.png

Nella figura si vede come il puntatore top all'elemento in cima allo stack. L'operazione di {{push inserisce un nuovo elemento e viene modificato il puntatore top per indicare il nuovo elemento. Nell'operazione pop viene estratto l'elemento in cima allo stack e viene modificato il puntatore.

Implementazione

È utile introdurre l'interfaccia attraverso cui si opera sullo stack. Sono presenti i metodi push che inserisce un nuovo oggetto in cima allo stack e lo restituisce, pop che estrae l'elemento in cima e lo restituisce. Oltre ad essi sono presenti anche altri metodi utili, come peek che restituisce l'oggetto in cima allo stack senza estrarlo, isEmpty che restituisce true se lo stack è vuoto e clear che elimina tutti gli elementi presenti nello stack.

interface IStack
{
    void push(object x);
    object pop();
    object peek();
    void clear();
}

L'implementazione utilizza un array per memorizzare i dati.

class Stack : IStack
{
    object[] data;
    int top;
 
    public bool isEmpty
    {
        get
        {
            return (top == 0);
        }
    }
 
    public Stack(int dimension)
    {
        data = new object[dimension];
        top = 0;
    }
 
    public object push(object x)
    {
        if (top < data.Length)
        {
            data[top] = x;
            top++;
        }
        else
        {
            Console.Out.WriteLine("Lo stack è pieno");
        }
        return x;
    }
 
        public object pop()
        {
            object temp;
             if (top > 0)
                {
                    top--;
                    temp = data[top];
                        return temp;
                }
                else
                {
                    Console.Out.WriteLine("Lo stack è vuoto");
                    return null;
                }
 
        }
 
        public object peek()
        {
                if (top > 0)
                {
                    return data[top];
                }
                else
                {
                    Console.Out.WriteLine("Lo stack è vuoto");
                    return null;
                }
        }
 
        public void clear()
        {
            top = 0;
        }
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License