Pila Java

Stack in Java di solito indica la classe di Collection Framework che implementa l'interfaccia List. Funziona secondo il principio della struttura dati Stack, che viene utilizzata per organizzare uno dei tipi di memoria. Inoltre potrebbe essere la parte della memoria a conservare i dati. In questo articolo presteremo prima di tutto attenzione alla classe Stack , considereremo i suoi metodi e forniremo degli esempi. Ma parleremo anche di una struttura dati come Stack e per cosa viene utilizzata.

Che cos'è la struttura dei dati dello stack

Prima di tutto, diamo una rapida occhiata a cos'è una struttura di dati dello stack. È una struttura dati lineare basata sul principio LIFO (Last-in-First-out). È una specie di anti-coda. Immagina un mazzo di carte o una pila di libri in una scatola. Il libro che metti per primo nella pila è in fondo, e il primo che tireremo fuori dalla scatola è il libro che era in cima, cioè quello che è entrato per ultimo nella scatola. Ecco un'immagine gif per dimostrare questo principio. Cosa sta succedendo qui? Abbiamo un pallone in cui può colpire solo una palla alla volta. La prima nel pallone è una pallina arancione, poi viola e infine verde (mi scuso con chi conosce i nomi più precisi di questi colori). Tuttavia per estrarre una pallina arancione dal nostro pallone-pila, dobbiamo estrarre prima la pallina che è arrivata per ultima (quella verde), poi quella che era la penultima (ma al momento dell'estrazione è l'ultima uno). La struttura dei dati dello stack in Java o altrove nella programmazione ha le due operazioni più importanti, push e pop . L'operazione push inserisce un elemento nello stack e l'operazione pop rimuove un elemento dalla parte superiore dello stack.

A cosa serve la struttura dati Stack?

Uno degli usi più importanti dello stack è organizzare le chiamate alle subroutine. Il punto di chiamata sullo stack memorizza l'indirizzo di ritorno dalla subroutine dopo che termina (e possibilmente i parametri passati). Con ogni chiamata nidificata (inclusa quella ricorsiva) di subroutine, nuovi indirizzi di ritorno vengono aggiunti allo stack. Con ogni operazione di ritorno dalla subroutine (ritorno), l'indirizzo di ritorno viene rimosso dallo stack e il controllo viene trasferito ad esso. Questa applicazione è così importante per la programmazione che nella maggior parte dei processori lo stack di ritorno è implementato nell'hardware nel set di istruzioni. Tuttavia, in altri casi, lo stack deve essere modellato su strutture di dati più generali.

Classe Java Stack di Collection Framework

In Java Stack Class è una classe del framework Collection che implementa l'interfaccia List ed estende la classe Vector. Implementa anche le interfacce Collection, Iterable, Cloneable, Serializable. Come probabilmente avrai già intuito, questa classe rappresenta la pila di oggetti LIFO. Ecco la chiamata al costruttore della classe Stack , ovvero la creazione di un oggetto di questa classe.

Stack<E> stack = new Stack<E>();

Dove E è il tipo di oggetto.

Metodi dello stack Java

Questa classe ha un solo costruttore predefinito e tutti i metodi della classe Vector . Inoltre, Stack ha i suoi 5 metodi:

• boolean empty() il metodo controlla se lo stack è vuoto o meno. Restituisce vero se lo stack è vuoto, falso in caso contrario.

• Object peek() il metodo restituisce l'elemento che si trova in cima allo stack.

• Object pop() il metodo restituisce l'elemento che si trova in cima allo stack e lo rimuove.

• Object push(Object element) il metodo aggiunge l'elemento specificato in cima allo stack.

• int search(Object element) il metodo cerca nello stack l'elemento specificato. Se l'elemento richiesto viene trovato, viene restituita la sua "distanza" dall'alto (numero di serie). Se l'elemento non viene trovato, viene restituito -1.

Esempio di codice dello stack

Creiamo un esempio di programma che funzioni come l'immagine gif qui sopra. Metteremo in pila tre "palline", arancione, viola e verde. Controlliamo che lo stack non sia vuoto. Quindi, estrarremo le palline dalla pila finché la pila non sarà vuota.

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.push("Orange Ball");
           myStack.push("Violet Ball");
           myStack.push("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

Ecco l'output di questo programma: Poiché Stack è ereditato da Vector Class e implementa l' interfaccia List , Stack , oltre alle classiche operazioni push e pop per questa struttura dati per l'aggiunta e l'estrazione di elementi, ha anche uno standard per le operazioni add() e remove() della struttura elenco. Nel nostro esempio, l'aggiunta di elementi può essere implementata allo stesso modo utilizzando il metodo add() . Tuttavia puoi estrarre usando remove() solo con un elemento specificato, il che non ha senso per la struttura dei dati dello stack.

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.add("Orange Ball");
           myStack.add("Violet Ball");
           myStack.add("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

Il risultato del lavoro del programma, ovviamente, sarà esattamente lo stesso.

E la tua implementazione di Stack?

È possibile creare la propria struttura di dati stack in Java utilizzando array o classi di elenchi collegati. Nel primo caso, viene assegnato un array continuo di celle per memorizzare i valori in memoria, che vengono utilizzati secondo necessità. Nella seconda, per ogni elemento dello stack, viene ordinato un blocco di memoria, sufficiente a memorizzare il valore ei riferimenti agli elementi precedenti e successivi dello stack. L'implementazione basata su array è più semplice, più efficiente e più efficiente in termini di memoria, ma richiede una conoscenza preliminare del limite della dimensione dello stack e può portare a bug difficili da trovare. L'implementazione basata su elenchi è più robusta ma meno efficiente. Facciamo una semplice implementazione basata su array dello stack. Comprenderà le funzioni.

• push — un metodo che assicurerà l'aggiunta di un elemento (nella prima posizione)

• pop — un metodo che fornirà la rimozione di un elemento (dalla posizione più alta)

• readTop — un metodo che restituirà il valore dell'elemento che si trova in posizione top

• sEmpty — un metodo che verificherà se lo stack è vuoto

• isFull — un metodo che verificherà se il nostro array in cui memorizziamo lo stack non è pieno

import java.util.Arrays;

public class MyStack {

   private int maxSize;
   private String[] stackArray;
   private int top;

   public MyStack(int size) {
       this.maxSize = size;
       stackArray = new String[maxSize];
       top = -1;
   }

   public String push (String element) {
       return stackArray[++top] = element;

   }

   public String pop (String element) {

       if (isEmpty())
       {
           System.out.println("Underflow\nProgram Terminated");
           System.exit(-1);
       }

       System.out.println("Removing " + readTop());

       return stackArray[top--];

   }

   public String readTop() {
       return stackArray[top];

   }

   public boolean isEmpty() {
       return (top ==  -1);
   }

   public boolean isFull() {
       return (top == maxSize - 1);
   }

   public void printStack(){
       System.out.println(Arrays.toString(stackArray));
   }
}

Ora implementiamo un esempio con tre palline basate sul nostro stack:

public class myStackTest {
   public static void main(String[] args) {
       MyStack  myStack = new MyStack(3);
       System.out.println("Is my stack empty? " + myStack.isEmpty());

       myStack.push("Orange Ball");
       myStack.push("Violet Ball");
       myStack.push("Green Ball");

      myStack.printStack();

       System.out.println("Is my stack empty? " + myStack.isEmpty());
       while (!myStack.isEmpty()) {
           myStack.pop(myStack.readTop());
           System.out.println("Is my stack empty? " + myStack.isEmpty());
       }
   }

}

L'output è qui: Se guardi da vicino, la variabile superiore contiene effettivamente l'indice dell'ultimo elemento e il riferimento all'oggetto rimane nell'array. Quindi questa implementazione necessita di qualche miglioramento. Pensa al modo più semplice per farlo.

Dovremmo usare Java Stack?

In effetti, Java Stack , come il suo genitore Vector , è una classe legacy. Al contrario, viene solitamente utilizzata la classe ArrayList . ArrayList non è sincronizzato mentre Vector è sincronizzato. Ciò significa che con Vector solo un thread alla volta può accedere al codice, mentre ArrayList può funzionare con più thread. Inoltre, ArrayList è più efficiente e veloce. Quindi molto probabilmente vedrai questa classe solo nel codice legacy. Ma la struttura dei dati Stack viene utilizzata molto spesso nella programmazione.