Share
Hva du skal skapeTo av de mest brukte datastrukturene i webutvikling er stabler og køer. Mange brukere av Internett, inkludert webutviklere, er uvitende om dette fantastiske faktumet. Hvis du er en av disse utviklerne, forbereder du deg på to opplysende eksempler: 'Løsning' av en tekstredigerer bruker en stabel for å organisere data; Event-loop av en nettleser, som håndterer hendelser (klikk, hoovers, etc.), bruker en kø til å behandle data.
Nå pause et øyeblikk og forestill deg hvor mange ganger vi, både som bruker og utvikler, bruker stabler og køer. Det er fantastisk, ikke sant? På grunn av deres ubiquity og likhet i design, har jeg besluttet å bruke dem til å introdusere deg til datastrukturer.
I datavitenskap er en stabel en lineær datastruktur. Hvis denne setningen inneholder marginal verdi for deg, som det opprinnelig gjorde med meg, kan du vurdere dette alternativet: En stabel organiserer data i rekkefølge.
Denne sekvensielle rekkefølgen er vanligvis beskrevet som en stabel av retter i en kafeteria. Når en plate legges til en stabel med retter, beholder platen rekkefølgen når den ble tilsatt; Videre, når en plate legges, skyves den mot bunnen av en bunke. Hver gang vi legger til en ny tallerken, skyves platen mot bunnen av stabelen, men den representerer også toppen av bunken av plater.
Denne prosessen med å legge plater vil beholde sekvensiell rekkefølge når hver plate ble tilsatt i stabelen. Fjerning av plater fra en stabel vil også beholde sekvensiell rekkefølge på alle plater. Hvis en tallerken fjernes fra toppen av en stabel, beholder hver annen plate i stakken fortsatt den riktige rekkefølgen i stakken. Det jeg beskriver, muligens med for mange ord, er hvordan plater legges til og fjernes på de fleste kantiner!
For å gi et mer teknisk eksempel på en stabel, la oss tilbakekalle "angre" operasjonen av en tekstredigerer. Hver gang tekst legges til et tekstredigeringsprogram, skyves denne teksten inn i en stabel. Det første tillegget til teksteditoren representerer bunnen av stakken; Den siste endringen representerer toppen av stabelen. Hvis en bruker ønsker å angre den siste endringen, blir toppen av stabelen fjernet. Denne prosessen kan gjentas til det ikke er flere tillegg til stakken, som er en tom fil!
Siden vi nå har en konseptuell modell av en stabel, la oss definere de to operasjonene av en stabel:
Accentsconagua
push (data) legger til data.pop () fjerner de sist oppdaterte dataene.La oss nå skrive koden for en stabel!
For implementeringen skal vi opprette en konstruktør som heter Stable. Hver forekomst av Stable vil ha to egenskaper: _størrelse og _Oppbevaring.
funksjon Stack () this._size = 0; this._storage = ;
this._storage gjør hver forekomst av Stable å ha sin egen beholder for lagring av data; this._size gjenspeiler antall ganger data ble presset til gjeldende versjon av a Stable. Hvis en ny forekomst av Stable er opprettet og data blir skjøvet inn i lagringsplassen da this._size vil øke til 1. Hvis data skyves, igjen, inn i stabelen, this._size vil øke til 2. Hvis data blir fjernet fra stabelen, så this._size vil synke til 1.
Vi må definere metoder som kan legge til (push) og fjerne (pop) data fra en stabel. La oss begynne med å trykke data.
Metode 1 av 2: push (data)
(Denne metoden kan deles mellom alle forekomster av Stable, så legger vi til prototypen til Stable.)
Vi har to krav til denne metoden:
Stack.prototype.push = funksjon (data) // øker størrelsen på vår lagring var size = this._size ++; // tilordner størrelse som en nøkkel for lagring // tilordner data som verdien av denne nøkkelen this._storage [size] = data; ;
Vår implementering av push (data) inkluderer følgende logikk. Erklære en variabel som heter størrelse og tilordne verdien av this._size++. Tildele størrelse som en nøkkel til this._storage. Og tilordne data som verdien av en tilsvarende nøkkel.
Hvis stakken påkrevd push (data) fem ganger, da størrelsen på stabelen vår ville være 5. Den første pushen til stakken ville tildele dataene en nøkkel på 1 i this._storage. Den femte påstanden om push (data) vil tilordne dataene en nøkkel på 5 i this._storage. Vi har nettopp tildelt ordre til våre data!
Metode 2 av 2: pop ()
Vi kan nå trykke data til en stabel; Det neste logiske trinnet popper (fjerner) data fra en stabel. Popping data fra en stabel er ikke bare å fjerne data; det fjerner bare de sist oppdaterte dataene.
Her er våre mål for denne metoden:
_this._size av en.Stack.prototype.pop = function () var size = this._size, deletedData; deletedData = this._storage [size]; slett this._storage [size]; this.size--; returnere deletedData; ;
pop () møter hvert av våre fire mål. Først erklærer vi to variabler: størrelse er initialisert til størrelsen på en stabel; deletedData er tilordnet dataene sist lagt til en stabel. For det andre sletter vi nøkkelverdier-paret for de siste dataene vi har lagt til. For det tredje reduserer vi størrelsen på en stabel med 1. For det fjerde returnerer vi dataene som ble fjernet fra stakken.
Hvis vi tester vår nåværende implementering av pop (), Vi finner at det fungerer for følgende brukstilfelle. Hvis vi push (data) data til en stabel, størrelsen på stakken øker med en. Hvis vi pop () data fra stabelen vår, størrelsen på stakken minker med en.
Et problem oppstår imidlertid når vi reverserer anropsordren. Vurder følgende scenario: Vi påberoper pop () og så push (data). Størrelsen på stabelen vår endres til -1 og deretter til 0. Men den riktige størrelsen på stabelen vår er 1!
For å håndtere dette brukstilfellet vil vi legge til en hvis uttalelse til pop ().
Stack.prototype.pop = function () var size = this._size, deletedData; hvis (størrelse) deletedData = this._storage [size]; slett this._storage [size]; this._size--; returnere deletedData; ;
Med tillegg av vår hvis erklæringen, kroppen vår kode blir utført bare når det er data i vår lagring.
Vår implementering av Stable er ferdig. Uavhengig av hvilken rekkefølge vi påberoper oss til våre metoder, fungerer koden vår! Her er den endelige versjonen av koden vår:
funksjon Stack () this._size = 0; this._storage = ; Stack.prototype.push = funksjon (data) var size = ++ this._size; this._storage [size] = data; ; Stack.prototype.pop = function () var size = this._size, deletedData; hvis (størrelse) deletedData = this._storage [size]; slett this._storage [size]; this._size--; returnere deletedData; ;
En stabel er nyttig når vi vil legge til data i rekkefølge og fjerne data. Basert på definisjonen, kan en stabel bare fjerne de siste dataene som ble lagt til. Hva skjer hvis vi vil fjerne de eldste dataene? Vi ønsker å bruke en datastruktur kalt kø.
I likhet med en stabel er en kø en lineær datastruktur. I motsetning til en stabel sletter en kø bare de eldste dataene som er lagt til.
For å hjelpe deg med å konseptualisere hvordan dette ville fungere, la oss ta et øyeblikk å bruke en analogi. Tenk deg at en kø er svært lik billettsystemet til en deli. Hver kunde tar en billett og blir servert når nummeret heter. Kunden som tar den første billetten, bør serveres først.
La oss videre forestille oss at denne billetten har nummeret "en" som vises på den. Neste billett har nummeret "to" som vises på den. Kunden som tar den andre billetten, blir servert andre. (Hvis vårt billettsystem fungerte som en stabel, ville kunden som gikk inn i stakken først være den siste som ble servert!)
Et mer praktisk eksempel på en kø er hendelsesløkken til en nettleser. Når ulike hendelser utløses, for eksempel et klikk, blir de lagt til i en event-loop-kø og håndtert i den rekkefølgen de gikk inn i køen.
Siden vi nå har en konseptuell modell av en kø, la oss definere operasjonen. Som du vil merke, er operasjonen til en kø veldig lik en stabel. Forskjellen ligger i hvor data blir fjernet.
Enqueue (data) legger til data i en kø. dequeue fjerner de eldste lagt til data i en kø. La oss nå skrive koden for en kø!
For implementeringen skal vi opprette en konstruktør som heter Kø. Vi vil da legge til tre egenskaper: _oldestIndex, _newestIndex, og _Oppbevaring. Behovet for begge deler _oldestIndex og _newestIndex blir tydeligere i neste avsnitt.
funksjonskø () this._oldestIndex = 1; this._newestIndex = 1; this._storage = ;
Vi skal nå lage de tre metodene som er delt blant alle forekomster av en kø: størrelse(), Enqueue (data), og dequeue (data). Jeg vil skissere målene for hver metode, avsløre koden for hver metode, og deretter forklare koden for hver metode.
Metode 1 av 3: størrelse()
Vi har to mål for denne metoden:
Queue.prototype.size = function () returnér dette._newestIndex - this._oldestIndex; ;
implementering størrelse() kan virke trivial, men du vil raskt finne det å være usant. For å forstå hvorfor, må vi raskt se hvordan størrelse ble implementert for en stabel.
Ved å bruke vår konseptuelle modell av en stabel, la oss forestille oss at vi skyver fem plater på en stabel. Størrelsen på stabelen vår er fem og hver tallerken har et nummer tilknyttet det fra en (første lagt plate) til fem (sist lagt plate). Hvis vi fjerner tre plater, har vi to plater. Vi kan bare trekke tre fra fem for å få den riktige størrelsen, som er to. Her er det viktigste punktet på størrelsen på en stabel: Gjeldende størrelse representerer den riktige nøkkelen som er knyttet til platen øverst på stakken (2) og den andre platen i stakken (1). Med andre ord, er rekkevidden av nøkler alltid fra gjeldende størrelse til 1.
La oss nå bruke denne implementeringen av stacken størrelse til køen vår. Tenk deg at fem kunder tar en billett fra billettsystemet vårt. Den første kunden har en billett som viser nummer 1 og den femte kunden har en billett som viser nummer 5. Med en kø serveres kunden med den første billetten først.
La oss nå forestille oss at den første kunden blir servert og at denne billetten er fjernet fra køen. I likhet med en stabel, kan vi få den riktige størrelsen på køen vår ved å trekke 1 fra 5. Vår kø har for tiden fire ubemerkede billetter. Nå er dette et problem som oppstår: Størrelsen representerer ikke lenger de riktige billettnumrene. Hvis vi bare subtraherer en fra fem, ville vi ha en størrelse på 4. Vi kan ikke bruke 4 for å bestemme gjeldende utvalg av gjenværende billetter i køen. Har vi billetter i køen med tallene fra 1 til 4 eller fra 2 til 5? Svaret er uklart.
Dette er fordelen ved å ha følgende to egenskaper i en kø: _oldestIndex og _newestIndex. Alt dette kan virke forvirrende - jeg er av og til forvirret. Hva som hjelper meg med å rasjonalisere alt er følgende eksempel jeg har utviklet.
Tenk deg at vår deli har to billettsystemer:
_newestIndex representerer en billett fra et kundes billettsystem._oldestIndex representerer en billett fra en ansatt billettsystem.Her er det vanskeligste konseptet å forstå når det gjelder å ha to billettsystemer: Når tallene i begge systemene er identiske, har hver kunde i køen blitt adressert og køen er tom. Vi vil bruke følgende scenario for å styrke denne logikken:
_newestIndex, er 1. Den neste billetten tilgjengelig i kundesystem er 2. _oldestIndex, som viser nummer 1. Vi har nå en eiendom (_newestIndex) som kan fortelle oss det største nummeret (nøkkelen) tildelt i køen og en eiendom (_oldestIndex) som kan fortelle oss det eldste indeksnummeret (nøkkelen) i køen.
Vi har tilstrekkelig utforsket størrelse(), så la oss nå flytte til Enqueue (data).
Metode 2 av 3: Enqueue (data)
Til Enqueue, vi har to mål:
_newestIndex som en nøkkel til this._storage og bruk alle data som legges til som verdien av den aktuelle nøkkelen._newestIndex med 1.Basert på disse to målene vil vi opprette følgende implementering av Enqueue (data):
Queue.prototype.enqueue = funksjon (data) this._storage [this._newestIndex] = data; this._newestIndex ++; ;
Kroppen til denne metoden inneholder to kodelinjer. På første linje bruker vi this._newestIndex å opprette en ny nøkkel for this._storage og tilordne data til det. this._newestIndex starter alltid med 1. På den andre linjen med kode øker vi this._newestIndex med 1, som oppdaterer verdien til 2.
Det er all koden vi trenger for Enqueue (data). La oss nå gjennomføre dequeue ().
Metode 3 av 3: dequeue ()
Her er målene for denne metoden:
_oldestIndex av en.Queue.prototype.dequeue = function () var oldestIndex = this._oldestIndex, deletedData = this._storage [eldsteIndex]; slett this._storage [oldestIndex]; this._oldestIndex ++; returnere deletedData; ;
I kroppen av dequeue (), Vi erklærer to variabler. Den første variabelen, oldestIndex, Tilordnes en køs nåværende verdi for this._oldestIndex. Den andre variabelen, deletedData, er tilordnet verdien i this._storage [oldestIndex].
Deretter sletter vi den eldste indeksen i køen. Etter at det er slettet, øker vi this._oldestIndex med 1. Endelig returnerer vi dataene vi nettopp slettet.
Ligner på problemet i vår første implementering av pop () med en stabel, vår implementering av dequeue () Håndter ikke situasjoner der data er fjernet før data blir lagt til. Vi må lage en betinget for å håndtere denne brukssaken.
Queue.prototype.dequeue = function () var oldestIndex = this._oldestIndex, newestIndex = this._newestIndex, deletedData; hvis (eldsteIndex! == nyesteIndex) deletedData = this._storage [eldsteIndex]; slett this._storage [oldestIndex]; this._oldestIndex ++; returnere deletedData; ;
Når verdiene til oldestIndex og newestIndex er ikke like, så utfører vi logikken vi hadde før.
Gjennomføringen av en kø er fullført. La oss se hele koden.
funksjonskø () this._oldestIndex = 1; this._newestIndex = 1; this._storage = ; Queue.prototype.size = function () returnér dette._newestIndex - this._oldestIndex; ; Queue.prototype.enqueue = funksjon (data) this._storage [this._newestIndex] = data; this._newestIndex ++; ; Queue.prototype.dequeue = function () var oldestIndex = this._oldestIndex, newestIndex = this._newestIndex, deletedData; hvis (eldsteIndex! == nyesteIndex) deletedData = this._storage [eldsteIndex]; slett this._storage [oldestIndex]; this._oldestIndex ++; returnere deletedData; ;
I denne artikkelen har vi utforsket to lineære datastrukturer: stabler og køer. En stabel lagrer data i sekvensiell rekkefølge og fjerner de sist oppdaterte dataene; en kø lagrer data i sekvensiell rekkefølge, men fjerner de eldste dataene som er lagt til.
Hvis implementeringen av disse datastrukturene virker trivial, minner du om formålet med datastrukturer. De er ikke designet for å være altfor kompliserte; De er laget for å hjelpe oss med å organisere data. I denne sammenheng, hvis du finner deg selv med data som må organiseres i sekvensiell rekkefølge, bør du vurdere å bruke en stabel eller kø.
