Share
Wat je gaat creërenTwee van de meest gebruikte datastructuren in webontwikkeling zijn stacks en wachtrijen. Veel gebruikers van internet, inclusief webontwikkelaars, zijn zich niet bewust van dit verbazingwekkende feit. Als u een van deze ontwikkelaars bent, bereid u dan voor op twee verhelderende voorbeelden: de bewerking 'ongedaan maken' van een teksteditor gebruikt een stapel om gegevens te ordenen; de event-lus van een webbrowser, die events verwerkt (clicks, hoovers, etc.), gebruikt een wachtrij om data te verwerken.
Pauzeer nu even en stel je voor hoe vaak we, als gebruiker en ontwikkelaar, stapels en wachtrijen gebruiken. Dat is geweldig, toch? Vanwege hun alomtegenwoordigheid en gelijkenis in ontwerp, heb ik besloten om ze te gebruiken om u kennis te laten maken met datastructuren.
In de informatica is een stapel een lineaire gegevensstructuur. Als dit statement een marginale waarde voor u heeft, zoals het oorspronkelijk met mij deed, overweeg dan dit alternatief: Een stapel organiseert gegevens in een sequentiële volgorde.
Deze volgorde wordt meestal omschreven als een stapel gerechten in een cafetaria. Wanneer een plaat wordt toegevoegd aan een stapel schalen, behoudt de plaat de volgorde waarin deze was toegevoegd; bovendien wordt, wanneer een plaat wordt toegevoegd, deze naar de bodem van een stapel geduwd. Telkens wanneer we een nieuwe plaat toevoegen, wordt de plaat naar de onderkant van de stapel geduwd, maar deze vertegenwoordigt ook de bovenkant van de stapel platen.
Dit proces van het toevoegen van platen zal de volgorde behouden waarin elke plaat in de stapel werd toegevoegd. Als u platen uit een stapel verwijdert, blijft ook de volgorde van alle platen behouden. Als een plaat van de bovenkant van een stapel wordt verwijderd, behoudt elke andere plaat in de stapel nog steeds de juiste volgorde in de stapel. Wat ik beschrijf, mogelijk met te veel woorden, is hoe platen bij de meeste cafetaria's worden toegevoegd en verwijderd!
Laten we, om een meer technisch voorbeeld van een stapel te geven, de 'ongedaan maken'-bewerking van een teksteditor oproepen. Telkens wanneer tekst aan een teksteditor wordt toegevoegd, wordt deze tekst in een stapel geduwd. De eerste toevoeging aan de teksteditor staat voor de onderkant van de stapel; de meest recente wijziging vertegenwoordigt de bovenkant van de stapel. Als een gebruiker de laatste wijziging ongedaan wil maken, wordt de bovenkant van de stapel verwijderd. Dit proces kan worden herhaald totdat er geen toevoegingen meer zijn aan de stapel, wat een blanco bestand is!
Omdat we nu een conceptueel model van een stapel hebben, laten we de twee bewerkingen van een stapel definiëren:
Accentsconagua
push (data) voegt gegevens toe.knal() verwijdert de meest recent toegevoegde gegevens.Laten we nu de code voor een stapel schrijven!
Voor onze implementatie maken we een constructor genaamd stack. Elke instantie van stack zal twee eigenschappen hebben: _grootte en _storage.
function Stack () this._size = 0; this._storage = ;
this._storage activeert elke instantie van stack een eigen container hebben voor het opslaan van gegevens; this._size weerspiegelt het aantal keren dat gegevens werden gepusht naar de huidige versie van a stack. Als een nieuw exemplaar van stack wordt gemaakt en de gegevens worden vervolgens in de opslagruimte gepusht this._size wordt verhoogd naar 1. Als gegevens opnieuw in de stapel worden gedrukt, this._size wordt verhoogd naar 2. Als er gegevens uit de stapel worden verwijderd, dan this._size zal afnemen tot 1.
We moeten methoden definiëren die (stapel) gegevens van een stapel kunnen toevoegen (pushen) en verwijderen. Laten we beginnen met het pushen van gegevens.
Methode 1 van 2: push (data)
(Deze methode kan worden gedeeld tussen alle instanties van stack, dus we zullen het toevoegen aan het prototype van stack.)
We hebben twee vereisten voor deze methode:
Stack.prototype.push = function (data) // vergroot de grootte van onze opslagvar size = this._size ++; // wijst grootte toe als een opslagsleutel // wijst gegevens toe als de waarde van deze sleutel this._storage [size] = data; ;
Onze implementatie van push (data) bevat de volgende logica. Declareer een variabele met de naam grootte en wijs het de waarde toe van this._size++. Toewijzen grootte als een sleutel van this._storage. En toewijzen gegevens als de waarde van een bijbehorende sleutel.
Als onze stack wordt aangeroepen push (data) vijf keer, dan zou de grootte van onze stapel 5 zijn. De eerste druk op de stapel zou die gegevens een sleutel van 1 in toewijzen this._storage. De vijfde aanroep van push (data) zou die gegevens een sleutel van 5 in toewijzen this._storage. We hebben zojuist opdracht aan onze gegevens toegewezen!
Methode 2 van 2: knal()
We kunnen nu gegevens naar een stapel duwen; de volgende logische stap is het verwijderen van gegevens uit een stapel. Popping data van een stack is niet simpelweg het verwijderen van data; het verwijdert alleen de meest recent toegevoegde gegevens.
Dit zijn onze doelen voor deze methode:
_this._size bij een.Stack.prototype.pop = function () var size = this._size, deletedData; deletedData = this._storage [size]; verwijder this._storage [size]; this.size--; return deletedData; ;
knal() ontmoet elk van onze vier doelen. Eerst verklaren we twee variabelen: grootte wordt geïnitialiseerd naar de grootte van een stapel; deletedData wordt toegewezen aan de gegevens die het laatst aan een stapel zijn toegevoegd. Ten tweede verwijderen we het sleutel / waarde-paar van onze meest recent toegevoegde gegevens. Ten derde verlagen we de grootte van een stapel met 1. Ten vierde retourneren we de gegevens die van de stapel zijn verwijderd.
Als we onze huidige implementatie van testen knal(), we vinden dat het werkt voor de volgende use-case. Als wij push (data) gegevens naar een stapel, de grootte van de stapel wordt met één verhoogd. Als wij knal() gegevens van onze stapel, de omvang van onze stapel wordt met één verlaagd.
Er ontstaat echter een probleem wanneer we de volgorde van aanroeping omkeren. Overweeg het volgende scenario: we roepen knal() en dan push (data). De grootte van onze stapel verandert in -1 en vervolgens in 0. Maar de juiste grootte van onze stapel is 1!
Om deze use case te behandelen, voegen we een als verklaring voor knal().
Stack.prototype.pop = function () var size = this._size, deletedData; if (size) deletedData = this._storage [size]; verwijder this._storage [size]; this._size--; return deletedData; ;
Met de toevoeging van onze als statement, de body van onze code wordt alleen uitgevoerd als er gegevens in onze opslag staan.
Onze implementatie van stack is compleet. Ongeacht de volgorde waarin we een van onze methoden inroepen, onze code werkt! Hier is de definitieve versie van onze code:
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]; verwijder this._storage [size]; this._size--; return deletedData; ;
Een stapel is handig wanneer we gegevens in de juiste volgorde willen toevoegen en gegevens willen verwijderen. Op basis van de definitie kan een stapel alleen de meest recent toegevoegde gegevens verwijderen. Wat gebeurt er als we de oudste gegevens willen verwijderen? We willen een gegevensstructuur gebruiken met de naam wachtrij.
Net als bij een stapel is een wachtrij een lineaire gegevensstructuur. In tegenstelling tot een stapel verwijdert een wachtrij alleen de oudste toegevoegde gegevens.
Om je te helpen begrijpen hoe dit zou werken, laten we even een moment nemen om een analogie te gebruiken. Stel je een wachtrij voor die erg lijkt op het ticketingsysteem van een delicatessenwinkel. Elke klant neemt een ticket en wordt geserveerd wanneer hun nummer wordt gebeld. De klant die het eerste ticket neemt, moet eerst worden bediend.
Laten we ons verder voorstellen dat dit kaartje het nummer "één" bevat. Het volgende ticket heeft het nummer "two" weergegeven. De klant die het tweede ticket neemt, wordt tweede. (Als ons ticketsysteem als een stapel zou werken, zou de klant die als eerste de stapel betrad de laatste zijn die werd bediend!)
Een meer praktisch voorbeeld van een wachtrij is de event-loop van een webbrowser. Wanneer verschillende gebeurtenissen worden geactiveerd, zoals de klik op een knop, worden ze toegevoegd aan de wachtrij van een gebeurtenislus en afgehandeld in de volgorde waarin ze in de wachtrij zijn geplaatst.
Omdat we nu een conceptueel model van een wachtrij hebben, laten we de operaties definiëren. Zoals u zult opmerken, lijken de bewerkingen in een wachtrij sterk op een stapel. Het verschil ligt in waar gegevens worden verwijderd.
enqueue (data) voegt gegevens toe aan een wachtrij. dequeue verwijdert de oudste toegevoegde gegevens in een wachtrij. Laten we nu de code voor een wachtrij schrijven!
Voor onze implementatie maken we een constructor genaamd Wachtrij. We voegen dan drie eigenschappen toe: _oldestIndex, _newestIndex, en _storage. De behoefte aan beide _oldestIndex en _newestIndex wordt duidelijker tijdens de volgende sectie.
function Queue () this._oldestIndex = 1; this._newestIndex = 1; this._storage = ;
We maken nu de drie methoden die door alle instanties van een wachtrij worden gedeeld: grootte(), enqueue (data), en dequeue (data). Ik zal de doelstellingen voor elke methode schetsen, de code voor elke methode onthullen en vervolgens de code voor elke methode uitleggen.
Methode 1 van 3: grootte()
We hebben twee doelstellingen voor deze methode:
Queue.prototype.size = function () return this._newestIndex - this._oldestIndex; ;
Implementeren grootte() lijkt misschien triviaal, maar je zult snel merken dat dat niet waar is. Om te begrijpen waarom, moeten we snel opnieuw bekijken hoe grootte werd geïmplementeerd voor een stapel.
Laten we ons met ons conceptuele model van een stapel voorstellen dat we vijf platen op een stapel drukken. De grootte van onze stapel is vijf en elke plaat heeft een bijbehorend nummer van een (eerste toegevoegde plaat) tot vijf (laatst toegevoegde plaat). Als we drie platen verwijderen, hebben we twee platen. We kunnen eenvoudig drie van vijf aftrekken om de juiste maat te krijgen, dat zijn er twee. Dit is het belangrijkste punt over de grootte van een stapel: de huidige grootte vertegenwoordigt de juiste sleutel die is gekoppeld aan de plaat bovenaan de stapel (2) en de andere plaat in de stapel (1). Met andere woorden, het toetsenbereik is altijd van de huidige grootte naar 1.
Laten we nu deze implementatie van stacks toepassen grootte naar onze wachtrij. Stel je voor dat vijf klanten een ticket nemen van ons ticketingsysteem. De eerste klant heeft een ticket met het nummer 1 en de vijfde klant heeft een ticket met het nummer 5. In een wachtrij wordt de klant met het eerste ticket eerst bediend.
Laten we ons nu voorstellen dat de eerste klant wordt bediend en dat dit ticket uit de wachtrij wordt verwijderd. Net als bij een stapel, kunnen we de juiste grootte van onze wachtrij krijgen door 1 af te trekken van 5. Onze wachtrij heeft momenteel vier niet-gereserveerde tickets. Dit is waar een probleem zich voordoet: de grootte vertegenwoordigt niet langer de juiste ticketnummers. Als we er eenvoudig een van vijf aftrekken, hebben we een grootte van 4. We kunnen 4 niet gebruiken om het huidige bereik van de resterende tickets in de wachtrij te bepalen. Hebben we tickets in de wachtrij met de nummers 1 t / m 4 of 2 t / m 5? Het antwoord is onduidelijk.
Dit is het voordeel van het hebben van de volgende twee eigenschappen in een wachtrij: _oldestIndex en _newestIndex. Dit alles lijkt misschien verwarrend - ik ben nog steeds af en toe in de war. Wat me helpt om alles te rationaliseren, is het volgende voorbeeld dat ik heb ontwikkeld.
Stel je voor dat onze deli twee ticketsystemen heeft:
_newestIndex staat voor een ticket van een systeem voor klantenkaartjes._oldestIndex staat voor een ticket van een ticketsysteem voor medewerkers.Dit is het moeilijkste concept om te begrijpen met betrekking tot twee ticketsystemen: wanneer de nummers in beide systemen identiek zijn, is elke klant in de wachtrij geadresseerd en is de wachtrij leeg. We zullen het volgende scenario gebruiken om deze logica te versterken:
_newestIndex, is 1. Het volgende ticket beschikbaar in het systeem voor klantenkaarten is 2. _oldestIndex, welke het nummer 1 toont. We hebben nu een eigendom (_newestIndex) die ons het grootste aantal (sleutel) dat in de wachtrij is toegewezen en een eigenschap (_oldestIndex) die ons het oudste indexnummer (sleutel) in de wachtrij kan vertellen.
We hebben adequaat onderzocht grootte(), dus laten we nu gaan naar enqueue (data).
Methode 2 van 3: enqueue (data)
Voor enqueue, we hebben twee doelen:
_newestIndex als een sleutel van this._storage en gebruik gegevens die worden toegevoegd als de waarde van die sleutel._newestIndex door 1.Op basis van deze twee doelstellingen, zullen we de volgende implementatie van creëren enqueue (data):
Queue.prototype.enqueue = function (data) this._storage [this._newestIndex] = data; this._newestIndex ++; ;
De body van deze methode bevat twee regels code. Op de eerste regel gebruiken we this._newestIndex om een nieuwe sleutel voor te maken this._storage en toewijzen gegevens ernaar toe. this._newestIndex begint altijd bij 1. Op de tweede regel van de code nemen we toe this._newestIndex op 1, die de waarde bijwerkt naar 2.
Dat is alle code die we nodig hebben enqueue (data). Laten we nu implementeren dequeue ().
Methode 3 van 3: dequeue ()
Hier zijn de doelstellingen voor deze methode:
_oldestIndex bij een.Queue.prototype.dequeue = function () var oldestIndex = this._oldestIndex, deletedData = this._storage [oldestIndex]; verwijder this._storage [oldestIndex]; this._oldestIndex ++; return deletedData; ;
In het lichaam van dequeue (), we verklaren twee variabelen. De eerste variabele, oldestIndex, is de huidige waarde van een wachtrij toegewezen voor this._oldestIndex. De tweede variabele, deletedData, krijgt de waarde die is opgenomen in this._storage [oldestIndex].
Vervolgens verwijderen we de oudste index in de wachtrij. Nadat het is verwijderd, verhogen we this._oldestIndex door 1. Ten slotte retourneren we de gegevens die we zojuist hebben verwijderd.
Vergelijkbaar met het probleem bij onze eerste implementatie van knal() met een stapel, onze implementatie van dequeue () kan niet omgaan met situaties waarin gegevens worden verwijderd voordat er gegevens worden toegevoegd. We moeten een voorwaarde maken om deze gebruikscasus af te handelen.
Queue.prototype.dequeue = function () var oldestIndex = this._oldestIndex, newestIndex = this._newestIndex, deletedData; if (oldestIndex! == newestIndex) deletedData = this._storage [oldestIndex]; verwijder this._storage [oldestIndex]; this._oldestIndex ++; return deletedData; ;
Wanneer de waarden van oldestIndex en newestIndex zijn niet gelijk, dan voeren we de logica uit die we eerder hadden.
Onze implementatie van een wachtrij is voltooid. Laten we de volledige code bekijken.
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]; verwijder this._storage [oldestIndex]; this._oldestIndex ++; return deletedData; ;
In dit artikel hebben we twee lineaire gegevensstructuren verkend: stapels en wachtrijen. Een stapel slaat gegevens op in de juiste volgorde en verwijdert de meest recent toegevoegde gegevens; een wachtrij slaat gegevens in de juiste volgorde op, maar verwijdert de oudste toegevoegde gegevens.
Als de implementatie van deze gegevensstructuren triviaal lijkt, herinner jezelf dan aan het doel van gegevensstructuren. Ze zijn niet ontworpen om overdreven ingewikkeld te zijn; ze zijn ontworpen om ons te helpen bij het organiseren van gegevens. Als u zich in deze context bevindt met gegevens die in een sequentiële volgorde moeten worden georganiseerd, overweeg dan om een stapel of wachtrij te gebruiken.
