Share
Cosa starai creandoDue delle strutture dati più comunemente usate nello sviluppo web sono stack e code. Molti utenti di Internet, compresi gli sviluppatori web, non sono consapevoli di questo fatto sorprendente. Se sei uno di questi sviluppatori, preparati a due esempi illuminanti: l'operazione "annulla" di un editor di testo utilizza uno stack per organizzare i dati; il ciclo di eventi di un browser web, che gestisce gli eventi (clic, hoover, ecc.), utilizza una coda per elaborare i dati.
Ora fermati un attimo e immagina quante volte noi, sia come utente che come sviluppatore, usiamo stack e code. È fantastico, vero? A causa della loro ubiquità e somiglianza nel design, ho deciso di usarli per introdurvi alle strutture dati.
In informatica, uno stack è una struttura di dati lineare. Se questa affermazione ha un valore marginale per te, come originariamente ha fatto con me, considera questa alternativa: uno stack organizza i dati in ordine sequenziale.
Questo ordine sequenziale è comunemente descritto come una pila di piatti in una caffetteria. Quando una piastra viene aggiunta a una pila di piatti, la piastra mantiene l'ordine di quando è stata aggiunta; inoltre, quando viene aggiunta una piastra, viene spinta verso il fondo di una pila. Ogni volta che aggiungiamo una nuova piastra, la piastra viene spinta verso il fondo della pila, ma rappresenta anche la parte superiore della pila di piastre.
Questo processo di aggiunta di piastre manterrà l'ordine sequenziale di quando ogni piastra è stata aggiunta alla pila. Rimuovere le lastre da una pila manterrà anche l'ordine sequenziale di tutte le lastre. Se una piastra viene rimossa dalla cima di una pila, ogni altra piastra nella pila manterrà comunque l'ordine corretto nella pila. Quello che sto descrivendo, possibilmente con troppe parole, è come le tavole vengono aggiunte e rimosse nella maggior parte delle mense!
Per fornire un esempio più tecnico di una pila, ricordiamo l'operazione 'annulla' di un editor di testo. Ogni volta che il testo viene aggiunto a un editor di testo, questo testo viene inserito in una pila. La prima aggiunta all'editor di testo rappresenta la parte inferiore della pila; la modifica più recente rappresenta la parte superiore della pila. Se un utente desidera annullare la modifica più recente, la parte superiore della pila viene rimossa. Questo processo può essere ripetuto fino a quando non ci sono più aggiunte allo stack, che è un file vuoto!
Dato che ora abbiamo un modello concettuale di uno stack, definiamo le due operazioni di uno stack:
Accentsconagua
push (dati) aggiunge dati.pop() rimuove i dati aggiunti più di recente.Ora scriviamo il codice per uno stack!
Per la nostra implementazione, creeremo un costruttore chiamato Pila. Ogni istanza di Pila avrà due proprietà: _taglia e _Conservazione.
function Stack () this._size = 0; this._storage = ;
this._storage abilita ogni istanza di Pila avere il proprio contenitore per la memorizzazione dei dati; this._size riflette il numero di volte in cui i dati sono stati trasferiti alla versione corrente di a Pila. Se una nuova istanza di Pila viene creato e i dati vengono inseriti nella sua memoria, quindi this._size aumenterà a 1. Se i dati vengono inseriti nuovamente nella pila, this._size aumenterà a 2. Se i dati vengono rimossi dallo stack, quindi this._size diminuirà a 1.
Dobbiamo definire metodi che possono aggiungere (push) e rimuovere (pop) i dati da una pila. Iniziamo con la spinta dei dati.
Metodo 1 di 2: push (dati)
(Questo metodo può essere condiviso tra tutte le istanze di Pila, quindi lo aggiungeremo al prototipo di Pila.)
Abbiamo due requisiti per questo metodo:
Stack.prototype.push = function (data) // aumenta la dimensione della nostra memoria var size = this._size ++; // assegna le dimensioni come chiave di archiviazione // assegna i dati come valore di questa chiave this._storage [size] = data; ;
La nostra implementazione di push (dati) include la seguente logica. Dichiarare una variabile denominata taglia e assegnagli il valore di this._size++. Assegnare taglia come una chiave di this._storage. E assegnare dati come il valore di una chiave corrispondente.
Se il nostro stack è stato invocato push (dati) cinque volte, la dimensione del nostro stack sarebbe 5. La prima spinta allo stack assegnerebbe a quel dato una chiave di 1 pollice this._storage. La quinta invocazione di push (dati) assegnerebbe a quei dati una chiave di 5 pollici this._storage. Abbiamo appena assegnato l'ordine ai nostri dati!
Metodo 2 di 2: pop()
Ora possiamo inviare dati in pila; il prossimo passo logico è scoppiare (rimuovere) i dati da una pila. Scoppiare i dati da una pila non significa semplicemente rimuovere i dati; rimuove solo i dati aggiunti più di recente.
Ecco i nostri obiettivi per questo metodo:
_this._size da uno.Stack.prototype.pop = function () var size = this._size, deletedData; deletedData = this._storage [dimensione]; elimina this._storage [dimensione]; this.size--; return deletedData; ;
pop() incontra ognuno dei nostri quattro obiettivi. Innanzitutto, dichiariamo due variabili: taglia è inizializzato alla dimensione di una pila; deletedData è assegnato ai dati aggiunti più di recente a uno stack. In secondo luogo, eliminiamo la coppia chiave-valore dei nostri dati aggiunti più di recente. Terzo, diminuiamo le dimensioni di uno stack di 1. In quarto luogo, restituiamo i dati che sono stati rimossi dallo stack.
Se testiamo la nostra attuale implementazione di pop(), troviamo che funziona per il seguente caso d'uso. Se noi push (dati) dati in una pila, la dimensione della pila aumenta di uno. Se noi pop() dati dal nostro stack, la dimensione del nostro stack diminuisce di uno.
Un problema sorge, tuttavia, quando invertiamo l'ordine di invocazione. Considera il seguente scenario: invochiamo pop() e poi push (dati). La dimensione del nostro stack cambia a -1 e poi a 0. Ma la dimensione corretta del nostro stack è 1!
Per gestire questo caso d'uso, aggiungeremo un Se dichiarazione a pop().
Stack.prototype.pop = function () var size = this._size, deletedData; if (size) deletedData = this._storage [size]; elimina this._storage [dimensione]; this._size--; return deletedData; ;
Con l'aggiunta del nostro Se dichiarazione, il corpo del nostro codice viene eseguito solo quando ci sono dati nel nostro archivio.
La nostra implementazione di Pila è completo. Indipendentemente dall'ordine in cui invochiamo uno dei nostri metodi, il nostro codice funziona! Ecco la versione finale del nostro codice:
function Stack () this._size = 0; this._storage = ; Stack.prototype.push = function (data) var size = ++ this._size; this._storage [size] = data; ; Stack.prototype.pop = function () var size = this._size, deletedData; if (size) deletedData = this._storage [size]; elimina this._storage [dimensione]; this._size--; return deletedData; ;
Uno stack è utile quando vogliamo aggiungere dati in ordine sequenziale e rimuovere i dati. In base alla sua definizione, uno stack può rimuovere solo i dati aggiunti più di recente. Cosa succede se vogliamo rimuovere i dati più vecchi? Vogliamo utilizzare una struttura dati chiamata queue.
Simile a uno stack, una coda è una struttura di dati lineare. A differenza di uno stack, una coda cancella solo i dati aggiunti più vecchi.
Per aiutarti a concettualizzare come funzionerebbe, prendiamoci un momento per usare un'analogia. Immagina che una coda sia molto simile al sistema di ticketing di una gastronomia. Ogni cliente prende un biglietto e viene servito quando viene chiamato il suo numero. Il cliente che prende il primo biglietto dovrebbe essere servito per primo.
Immaginiamo inoltre che questo ticket abbia il numero "uno" visualizzato su di esso. Il prossimo ticket ha il numero "due" visualizzato su di esso. Il cliente che prende il secondo biglietto verrà servito secondo. (Se il nostro sistema di ticketing funziona come una pila, il cliente che è entrato nella pila per primo sarebbe l'ultimo ad essere servito!)
Un esempio più pratico di una coda è il ciclo di eventi di un browser web. Quando vengono attivati diversi eventi, come il clic di un pulsante, vengono aggiunti alla coda di un ciclo di eventi e gestiti nell'ordine in cui sono entrati nella coda.
Dato che ora abbiamo un modello concettuale di una coda, definiamo le sue operazioni. Come noterai, le operazioni di una coda sono molto simili a una pila. La differenza sta nel luogo in cui i dati vengono rimossi.
enqueue (dati) aggiunge dati a una coda. dequeue rimuove i dati aggiunti più vecchi in una coda. Ora scriviamo il codice per una coda!
Per la nostra implementazione, creeremo un costruttore chiamato Coda. Aggiungeremo quindi tre proprietà: _oldestIndex, _newestIndex, e _Conservazione. Il bisogno di entrambi _oldestIndex e _newestIndex diventerà più chiaro durante la prossima sezione.
function Queue () this._oldestIndex = 1; this._newestIndex = 1; this._storage = ;
Creeremo ora i tre metodi condivisi tra tutte le istanze di una coda: taglia(), enqueue (dati), e dequeue (dati). Illustrerò gli obiettivi per ciascun metodo, rivelerò il codice per ciascun metodo e quindi spiegherò il codice per ciascun metodo.
Metodo 1 di 3: taglia()
Abbiamo due obiettivi per questo metodo:
Queue.prototype.size = function () return this._newestIndex - this._oldestIndex; ;
Implementazione taglia() potrebbe sembrare banale, ma lo troverai presto falso. Per capire perché, dobbiamo rivisitare rapidamente come taglia è stato implementato per uno stack.
Usando il nostro modello concettuale di una pila, immaginiamo di spingere cinque piatti su una pila. La dimensione della nostra pila è cinque e ogni piastra ha un numero associato da una (prima piastra aggiunta) a cinque (ultima piastra aggiunta). Se togliamo tre piatti, allora abbiamo due piatti. Possiamo semplicemente sottrarre tre da cinque per ottenere la dimensione corretta, che è due. Ecco il punto più importante sulla dimensione di una pila: la dimensione corrente rappresenta la chiave corretta associata alla piastra in cima alla pila (2) e l'altra piastra nella pila (1). In altre parole, l'intervallo di chiavi è sempre dalla dimensione corrente a 1.
Ora, applichiamo questa implementazione di stack taglia alla nostra coda. Immagina che cinque clienti prendano un biglietto dal nostro sistema di ticketing. Il primo cliente ha un ticket che visualizza il numero 1 e il quinto cliente ha un ticket che visualizza il numero 5. Con una coda, il cliente con il primo ticket viene servito per primo.
Immaginiamo ora che il primo cliente sia servito e che questo ticket sia rimosso dalla coda. Simile a uno stack, possiamo ottenere la dimensione corretta della nostra coda sottraendo 1 da 5. Attualmente la nostra coda ha quattro ticket non serviti. Ora, questo è dove sorge un problema: la dimensione non rappresenta più i numeri di biglietto corretti. Se abbiamo semplicemente sottratto uno da cinque, avremmo una dimensione di 4. Non possiamo usare 4 per determinare l'attuale gamma di biglietti rimanenti nella coda. Abbiamo biglietti in coda con i numeri da 1 a 4 o da 2 a 5? La risposta non è chiara.
Questo è il vantaggio di avere le seguenti due proprietà in una coda: _oldestIndex e _newestIndex. Tutto ciò può sembrare confuso - sono ancora occasionalmente confuso. Ciò che mi aiuta a razionalizzare tutto è il seguente esempio che ho sviluppato.
Immagina che la nostra gastronomia abbia due sistemi di bigliettazione:
_newestIndex rappresenta un biglietto da un sistema di ticketing del cliente._oldestIndex rappresenta un biglietto da un sistema di ticketing dei dipendenti.Ecco il concetto più difficile da comprendere per quanto riguarda l'avere due sistemi di biglietteria: quando i numeri in entrambi i sistemi sono identici, ogni cliente in coda è stato indirizzato e la coda è vuota. Utilizzeremo il seguente scenario per rafforzare questa logica:
_newestIndex, è 1. Il prossimo ticket disponibile nel sistema di ticket cliente è 2. _oldestIndex, che visualizza il numero 1. Ora abbiamo una proprietà (_newestIndex) che può dirci il numero più grande (chiave) assegnato in coda e una proprietà (_oldestIndex) che può dirci il più vecchio numero di indice (chiave) nella coda.
Abbiamo adeguatamente esplorato taglia(), quindi passiamo a enqueue (dati).
Metodo 2 di 3: enqueue (dati)
Per enqueue, abbiamo due obiettivi:
_newestIndex come una chiave di this._storage e utilizzare tutti i dati aggiunti come valore di quella chiave._newestIndex per 1.Sulla base di questi due obiettivi, creeremo la seguente implementazione di enqueue (dati):
Queue.prototype.enqueue = function (data) this._storage [this._newestIndex] = data; this._newestIndex ++; ;
Il corpo di questo metodo contiene due righe di codice. Sulla prima riga, usiamo this._newestIndex creare una nuova chiave per this._storage e assegnare dati ad esso. this._newestIndex inizia sempre con 1. Sulla seconda riga di codice, incrementiamo this._newestIndex per 1, che aggiorna il suo valore a 2.
Questo è tutto il codice di cui abbiamo bisogno enqueue (dati). Eseguiamo ora dequeue ().
Metodo 3 di 3: dequeue ()
Ecco gli obiettivi per questo metodo:
_oldestIndex da uno.Queue.prototype.dequeue = function () var oldestIndex = this._oldestIndex, deletedData = this._storage [oldestIndex]; elimina this._storage [oldestIndex]; this._oldestIndex ++; return deletedData; ;
Nel corpo di dequeue (), dichiariamo due variabili. La prima variabile, oldestIndex, viene assegnato il valore corrente di una coda per this._oldestIndex. La seconda variabile, deletedData, è assegnato il valore contenuto in this._storage [oldestIndex].
Successivamente, cancelliamo l'indice più vecchio nella coda. Dopo che è stato eliminato, incrementiamo this._oldestIndex entro il 1. Infine, restituiamo i dati che abbiamo appena cancellato.
Simile al problema nella nostra prima implementazione di pop() con una pila, la nostra implementazione di dequeue () non gestisce le situazioni in cui i dati vengono rimossi prima che vengano aggiunti dati. Dobbiamo creare un condizionale per gestire questo caso d'uso.
Queue.prototype.dequeue = function () var oldestIndex = this._oldestIndex, newestIndex = this._newestIndex, deletedData; if (oldestIndex! == newestIndex) deletedData = this._storage [oldestIndex]; elimina this._storage [oldestIndex]; this._oldestIndex ++; return deletedData; ;
Ogni volta che i valori di oldestIndex e newestIndex non sono uguali, quindi eseguiamo la logica che avevamo prima.
La nostra implementazione di una coda è completa. Vediamo l'intero codice.
function Queue () this._oldestIndex = 1; this._newestIndex = 1; this._storage = ; Queue.prototype.size = function () return this._newestIndex - this._oldestIndex; ; Queue.prototype.enqueue = function (data) this._storage [this._newestIndex] = data; this._newestIndex ++; ; Queue.prototype.dequeue = function () var oldestIndex = this._oldestIndex, newestIndex = this._newestIndex, deletedData; if (oldestIndex! == newestIndex) deletedData = this._storage [oldestIndex]; elimina this._storage [oldestIndex]; this._oldestIndex ++; return deletedData; ;
In questo articolo, abbiamo esplorato due strutture di dati lineari: pile e code. Uno stack memorizza i dati in ordine sequenziale e rimuove i dati aggiunti più di recente; una coda memorizza i dati in ordine sequenziale ma rimuove i dati aggiunti più vecchi.
Se l'implementazione di queste strutture di dati sembra banale, ricorda a te stesso lo scopo delle strutture dati. Non sono progettati per essere eccessivamente complicati; sono progettati per aiutarci a organizzare i dati. In questo contesto, se ti trovi con dati che devono essere organizzati in ordine sequenziale, considera l'utilizzo di uno stack o di una coda.
