Gli stack sono strutture di dati lineari che seguono il principio di LIFO. LIFO sta per last in first out, il che significa che l'elemento aggiunto più di recente è il primo a essere rimosso. Questa struttura di dati è denominata pila come analogia con le pile del mondo reale, ad esempio una pila di biscotti in un barattolo di biscotti o una pila di libri su uno scaffale. Nella pila l'inserimento e l'estrazione possono essere eseguiti solo su un'estremità, ovvero la parte superiore della pila. Ad esempio, se vogliamo mangiare un biscotto, otterremo prima quello più in alto, poi il secondo e così via.
Questo post riguarderà l'implementazione dello stack in JavaScript. Poiché stiamo lavorando con JavaScript, non ci preoccuperemo delle dimensioni dello stack poiché le dimensioni degli oggetti JavaScript possono crescere dinamicamente.
Implementazione di Stack in JavaScript
Useremo una classe JavaScript per implementare la struttura dei dati dello stack. Il pila class conterrà un array nel suo costruttore che verrà utilizzato per memorizzare gli elementi nello stack. La classe definirà anche diversi metodi che verranno utilizzati per manipolare i dati archiviati all'interno dello stack. I metodi più basilari dell'array sono i inserire() e estratto() metodi utilizzati per aggiungere e rimuovere elementi dalla cima dello stack.
Il pila class definisce anche altri metodi come sbirciare() , è vuoto() , chiaro() , Stampa() e taglia() anche:
pila di classe {
costruttore ( ) {
questo.elementi = [ ] ;
}
// Posiziona un oggetto in cima alla pila
inserire ( elemento ) {
questo.elementi.push ( elemento ) ;
}
// Rimuove un elemento dalla cima della pila
estratto ( ) {
questo.elementi.pop ( ) ;
}
// Restituisce l'elemento più in alto dello stack
sbirciare ( ) {
Restituzione questo.elementi [ questo.elementi.lunghezza - 1 ] ;
}
// Controlli Se la pila è vuota
è vuoto ( ) {
Restituzione this.elements.length == 0 ;
}
// Stampa l'intera pila
Stampa ( ) {
per ( permettere io = 0 ; io < questa.lunghezza.di.elementi; io++ ) {
console.log ( questo.elementi [ io ] ) ;
}
}
// Restituisce il taglia della pila
taglia ( ) {
Restituzione questa.lunghezza.di.elementi;
}
// cancella la pila
chiaro ( ) {
questo.elementi = [ ] ;
}
}
Spingere e far scoppiare elementi dalla pila
L'operazione più semplice della pila è inserire ed estrarre elementi dalla parte superiore della pila. La classe stack fornisce due metodi per queste operazioni:
La prima riga del suddetto codice dichiara un nuovo stack denominato S . Poi il inserire() viene utilizzato per inserire quattro elementi nella pila, due dei quali vengono poi rimossi dal estratto() metodo.
Come ottenere l'elemento superiore dallo stack
Il pila classe definisce il sbirciare() metodo per ottenere l'elemento superiore dallo stack:
Come verificare se lo stack è vuoto?
La classe definisce anche un metodo che può essere utilizzato per verificare se lo stack è vuoto:
Come stampare l'intera pila?
Il Stampa() può essere chiamato per stampare l'intero stack
Come controllare la dimensione della pila?
Il taglia() metodo utilizza il .lunghezza proprietà per ottenere la dimensione dello stack:
Come cancellare l'intero stack?
Basta invocare il chiaro() metodo per rimuovere ogni elemento dello stack:
Conclusione
Gli stack sono utili strutture di dati con molte applicazioni del mondo reale come la cronologia del browser, il pulsante Annulla negli editor di testo e i registri delle chiamate. Tutte queste applicazioni seguono il principio LIFO, ad esempio il pulsante Indietro nel browser riporta all'ultima pagina visitata e la prima voce del registro chiamate è sempre l'ultima chiamata.
L'implementazione di stack in JavaScript è davvero semplice in quanto ha il built-in spingere e pop metodi per gli array. Questo articolo illustra il processo di implementazione dello stack in JavaScript.