Datastructuren: algemeen concept, implementatie. De eenvoudigste datastructuren: wachtrij, stapel

Stapel

De stapel is de meest populaire en misschien wel de belangrijkste datastructuur bij het programmeren. Een stapel is een opslagapparaat waaruit elementen worden verwijderd in de omgekeerde volgorde van hun toevoeging. Het is als een onregelmatige wachtrij, waarbij de eerste die wordt bediend degene is die er het laatst in is gekomen. In de programmeerliteratuur worden afkortingen algemeen aanvaard om de discipline van de wachtrij en stapel aan te duiden. De wachtrijdiscipline wordt FIFO genoemd, wat First In First Out betekent. De stapeldiscipline wordt LIFO genoemd, last in first out (Last In First Out).

De stapel kan worden gezien als een buis met een veerbelaste bodem, verticaal geplaatst. Het bovenste uiteinde van de buis is open, er kunnen elementen aan worden toegevoegd of, zoals ze zeggen, erin worden geduwd. Veelgebruikte Engelse termen zijn in dit opzicht erg kleurrijk; de handeling waarbij een element aan de stapel wordt toegevoegd, wordt aangeduid als push, vertaald als ‘push, shove’. Als er een nieuw element wordt toegevoegd, worden eerder op de stapel geplaatste elementen één positie naar beneden geduwd. Wanneer elementen van de stapel worden gehaald, worden ze omhoog geduwd, in het Engels pop ("shoot").

Een voorbeeld van een stapel is een hooiberg, een stapel papieren op een tafel, een stapel borden, enz. Dit is waar de naam stack vandaan komt, wat stack betekent in het Engels. Borden worden van de stapel verwijderd in de omgekeerde volgorde van plaatsing. Alleen de bovenplaat is toegankelijk, d.w.z. bord bovenop de stapel. Een goed voorbeeld is ook een doodlopende spoorlijn waarin auto's kunnen worden gestapeld.

De stapel wordt vrij vaak en in verschillende situaties gebruikt. Ze zijn verenigd door het volgende doel: je moet wat werk opslaan dat nog niet is voltooid, als je naar een andere taak moet overschakelen. De stapel wordt gebruikt om tijdelijk de status op te slaan van een taak die nog niet is voltooid. Na het opslaan van de status schakelt de computer over naar een andere taak. Na voltooiing van de uitvoering wordt de status van de uitgestelde taak hersteld van de stapel en zet de computer de onderbroken bewerking voort.

Waarom wordt de stapel gebruikt om de status van een onderbroken taak op te slaan? Laten we aannemen dat de computer taak A uitvoert. Tijdens de uitvoering ervan ontstaat de behoefte om taak B uit te voeren. De status van taak A wordt onthouden en de computer gaat verder met het uitvoeren van taak B. Maar zelfs tijdens het uitvoeren van taak B kan de computer overschakelen naar een andere taak C, en de status van taak B moet worden opgeslagen voordat verder kan worden gegaan naar C. Later, na voltooiing van C, zal eerst de status van taak B worden hersteld, en vervolgens, na voltooiing van B, de status van taak A. Herstel vindt dus plaats in de omgekeerde volgorde van sparen, wat overeenkomt met stapeldiscipline.

Met de stapel kunt u recursie organiseren, d.w.z. een subroutine roept zichzelf op, rechtstreeks of via een reeks andere oproepen. Laat routine A bijvoorbeeld een algoritme uitvoeren dat afhankelijk is van een invoerparameter X en mogelijk van de toestand van de globale data. Voor de eenvoudigste waarden van X wordt het algoritme direct geïmplementeerd. In het geval van complexere waarden van X wordt het algoritme geïmplementeerd als een reductie van de toepassing van hetzelfde algoritme voor eenvoudigere waarden van X. In dit geval heeft subroutine A toegang tot zichzelf en geeft de eenvoudigere waarde van X door als Met deze toegang worden de vorige waarde van parameter X, evenals alle lokale variabelen van routine A, op de stapel opgeslagen. Vervolgens wordt een nieuwe set lokale variabelen en een variabele gemaakt die de nieuwe (eenvoudigere) waarde van parameter X bevat. De opgeroepen subroutine A werkt op de nieuwe set variabelen zonder de vorige set te vernietigen. Aan het einde van de oproep worden de oude set lokale variabelen en de oude status van de invoerparameter X hersteld van de stapel, en gaat de routine verder waar deze was gebleven.

Sterker nog, je hoeft de waarden van de lokale variabelen van de subroutine niet eens op een speciale manier op de stapel op te slaan. Het is een feit dat de lokale variabelen van een subroutine (dat wil zeggen de interne werkvariabelen, die aan het begin van de uitvoering worden gemaakt en aan het einde worden vernietigd) op een stapel worden geplaatst die is geïmplementeerd in hardware op basis van gewoon RAM. Helemaal aan het begin van zijn werk neemt de subroutine ruimte op de stapel in beslag voor zijn lokale variabelen; dit geheugengebied in de hardwarestapel wordt meestal genoemd lokaal variabel blok of in het Engels kader("kader"). Op het moment dat het werk is voltooid, maakt de subroutine geheugen vrij door het blok met zijn lokale variabelen van de stapel te verwijderen.

Naast lokale variabelen worden retouradressen voor subroutineoproepen opgeslagen op de hardwarestack. Laat op een bepaald punt in programma A een subroutine oproepen B. Voordat subroutine B wordt aangeroepen, wordt het adres van de instructie die volgt op de instructie die B aanroept, op de stapel opgeslagen. Dit is de zgn retouradres naar programma A. Wanneer subroutine B klaar is, haalt hij het retouradres van programma A uit de stapel en geeft de besturing terug aan dat adres. De computer gaat dus door met het uitvoeren van programma A, te beginnen met de instructie die volgt op de oproepinstructie. De meeste processors hebben speciale instructies die het aanroepen van een subroutine ondersteunen door eerst een retouradres op de stapel te duwen en vanuit de subroutine terug te keren naar het adres dat uit de stapel is gehaald. Meestal heet het call-commando call, het return-commando heet return.

De parameters van een subroutine of functie worden ook op de stapel geduwd voordat deze wordt aangeroepen. De volgorde waarin ze op de stapel worden geplaatst, hangt af van de conventies van talen op hoog niveau. In de taal C of C++ bevindt het eerste functieargument zich dus bovenaan de stapel, het tweede eronder, enzovoort. Bij Pascal is het andersom: het laatste argument van de functie staat bovenaan de stapel. (Dit is trouwens de reden waarom functies met een variabel aantal argumenten, zoals printf, wel mogelijk zijn in C, maar niet in Pascal.)

In Fortran-4, een van de oudste en meest succesvolle programmeertalen, worden argumenten doorgegeven via een speciaal geheugengebied, dat zich mogelijk niet op de stapel bevindt, aangezien er tot het einde van de jaren '70 van de 20e eeuw nog steeds computers waren zoals de IBM 360- of ES-computers zonder hardware-implementatiestack. Retouradressen werden ook niet op de stapel opgeslagen, maar in geheugencellen die voor elke subroutine waren vastgelegd. Programmeurs noemen dergelijk geheugen statisch in de zin dat statische variabelen altijd en op elk moment dezelfde plaats in het geheugen innemen tijdens de uitvoering van het programma. Bij gebruik van alleen statisch geheugen is recursie niet mogelijk omdat de eerdere waarden van lokale variabelen worden vernietigd wanneer er een nieuwe aanroep wordt gedaan. De referentie Fortran 4 gebruikte alleen statische variabelen en recursie was verboden. Tot nu toe wordt de Fortran-taal veel gebruikt in wetenschappelijke en technische berekeningen, maar de moderne Fortran-90-standaard introduceert al stapelgeheugen, waardoor de tekortkomingen van eerdere versies van de taal worden geëlimineerd.

Een stapel is een programmeerfenomeen en een natuurlijke oplossing. Stack kwam onmiddellijk in de computerwereld terecht en werd zo ‘native’, alsof het daar was waar het allemaal begon.

Zonder stapel werkt de processor niet, is er geen recursie en is het onmogelijk om efficiënte functieaanroepen te organiseren. Elk algoritme kan zonder een wachtrij, lijst, verzameling, array of systeem van georganiseerde objecten, maar niets werkt zonder geheugen en een stapel, inclusief al het bovenstaande.

Aan het begin van het begin: processor, geheugen en stack

Ideaal geheugen zorgt voor directe adressering van de waarde - dit zijn de machine- en taalniveaus van hoge kwaliteit. In het eerste geval itereert de processor opeenvolgend door geheugenadressen en voert instructies uit. In het tweede geval manipuleert de programmeur arrays. Beide afleveringen bevatten:

• adres = waarde;
• index = waarde.

Het adres kan absoluut en relatief zijn, de index kan digitaal en associatief zijn. Het adres en de index kunnen een ander adres dan een waarde bevatten, maar dit zijn de details van indirecte adressering. Zonder geheugen kan een processor niet werken, en zonder een stapel opdrachten en gegevens is het als een boot zonder roeispanen.

Een stapel borden is een traditioneel verhaal over de essentie van een stapel: het concept van stapel en vertaling in het algemene bewustzijn. Je kunt een bord niet van onderaf pakken, je kunt het alleen van bovenaf pakken, en dan zijn alle platen intact.

Wat als laatste op de stapel komt, gaat als eerste. De perfecte oplossing. In wezen transformeert stapel, als vertaling van de ene actie in de andere, het idee van een algoritme als een reeks bewerkingen.

De essentie en het concept van een stapel

De processor en het geheugen zijn de belangrijkste bouwstenen van een computer. De processor voert instructies uit, manipuleert geheugenadressen en haalt waarden op en wijzigt deze op deze adressen. In een programmeertaal wordt dit allemaal omgezet in variabelen en hun waarden. De essentie van de stapel en het concept van last in first out (LIFO) blijft ongewijzigd.

De afkorting LIFO wordt niet meer zo vaak gebruikt als vroeger. Waarschijnlijk omdat lijsten zijn omgezet in objecten en indien nodig FIFO-wachtrijen (First in First Out) worden gebruikt. De dynamiek van datatypen heeft zijn relevantie verloren in de context van het beschrijven van variabelen, maar heeft zijn betekenis verworven op het moment van uitvoering van expressies: het type data wordt bepaald op het moment dat het wordt gebruikt, en tot dat moment kun je beschrijven alles en elke manier die je maar wilt.

Dus stapel - wat is het? Nu weet je dat dit een ongepaste vraag is. Zonder stack is er immers geen moderne programmering. Elke functieaanroep betekent het doorgeven van parameters en een retouradres. Een functie kan een andere functie aanroepen - dit is opnieuw het doorgeven van parameters en een retouradres. Het opzetten van een mechanisme om waarden op te roepen zonder stapel is extra werk, al is een haalbare oplossing zeker mogelijk.

Veel mensen vragen: "Stapel - wat is het?" In de context van een functieaanroep bestaat deze uit drie acties:

• het retouradres opslaan;
• het opslaan van alle overgedragen variabelen of adressen;
• functie oproep.

Zodra de opgeroepen functie zijn missie heeft voltooid, zal deze eenvoudigweg de controle teruggeven aan het retouradres. Een functie kan een willekeurig aantal andere functies aanroepen, aangezien de limiet alleen de grootte van de stapel is.

Stapel eigenschappen

Een stapel is geen abstract gegevenstype, maar een echt mechanisme. Op processorniveau is het een ‘motor’ die het werk van de hoofdprocessorcyclus verfijnt en aanvult. Net als bitrekenkunde legt de stapel eenvoudige en voor de hand liggende bedieningsregels vast. Het is betrouwbaar en veilig.

De karakteristieke eigenschappen van een stapel zijn de grootte en de lengte van de elementen. Op processorniveau wordt alles bepaald door de bitcapaciteit, geheugenadressering en de fysica van toegang daartoe. Een interessant kenmerk en traditie: de stapel groeit naar beneden, dat wil zeggen naar afnemende geheugenadressen, en naar programma- en datageheugen naar boven. Dit is gebruikelijk, maar niet vereist. De betekenis hier is belangrijk: hij kwam als laatste en vertrok als eerste. Met deze verrassend eenvoudige regel kun je interessante algoritmen bouwen, voornamelijk in talen op hoog niveau. Nu zul je niet vragen: wat is een stapel?

Onberispelijke hardwareprestaties zijn lange tijd de norm geweest, maar op het snijvlak van de informatietechnologie krijgt het idee van een stapel nieuwe en opwindende toepassingen.

In wezen maakt het niet uit wat de stapel is op processorniveau. Het is een natuurlijk onderdeel van de computerarchitectuur. Maar bij het programmeren hangt de stapel af van de specifieke toepassing en het vermogen van de programmeur.

Arrays, verzamelingen, lijsten, wachtrijen... Stapel!

Mensen stellen vaak de vraag: "Stack - wat is het?" ‘Programmeren’ en ‘systematiseren’ zijn interessante concepten: het zijn geen synoniemen, maar ze zijn zo nauw verwant. De programmering is zo snel gegaan dat de bereikte pieken ideaal lijken. Hoogstwaarschijnlijk is dit niet het geval. Maar uiteraard iets anders.

Het idee van een stapel is niet alleen bekend geworden op het niveau van verschillende programmeertalen, maar ook op het niveau van hun ontwerpen en mogelijkheden voor het creëren van gegevenstypen. Elke array heeft push en pop, en de concepten van “de eerste en laatste elementen van de array” zijn traditioneel geworden. Vroeger waren er alleen array-elementen, maar tegenwoordig zijn er:

• array-elementen;
• eerste element van de array;
• het laatste element van de array.

De handeling waarbij een element in een array wordt geplaatst, verplaatst de aanwijzer, en het ophalen van een element vanaf het begin of vanaf het einde van de array maakt een verschil. In wezen is dit dezelfde stapel, maar toegepast op andere gegevenstypen.

Het is vooral opmerkelijk dat populaire programmeertalen geen stapelconstructie hebben. Maar ze geven zijn idee volledig door aan de ontwikkelaar.

Een stapel is een verzameling waarvan de elementen op last-in, first-out-basis worden verkregen. (Last-In-First-Out of LIFO). Dit betekent dat we alleen toegang hebben tot het laatst toegevoegde element.

In tegenstelling tot lijsten hebben we geen toegang tot een willekeurig element van de stapel. We kunnen alleen elementen toevoegen of verwijderen met behulp van speciale methoden. Stapels hebben ook geen methode Bevat, zoals lijsten dat wel hebben. Bovendien heeft de stapel geen iterator. Laten we, om te begrijpen waarom dergelijke beperkingen op de stapel worden geplaatst, eens kijken hoe het werkt en hoe het wordt gebruikt.

De meest voorkomende analogie om een ​​stapel uit te leggen is een stapel platen. Ongeacht hoeveel borden er in de stapel zitten, we kunnen altijd de bovenste verwijderen. Schone borden worden op dezelfde manier bovenop de stapel gelegd, waarbij we altijd het bord nemen dat als laatste is geplaatst.

Als we bijvoorbeeld een rode plaat plaatsen, dan een blauwe en dan een groene, dan moeten we eerst de groene verwijderen, dan de blauwe en ten slotte de rode. Het belangrijkste om te onthouden is dat borden altijd bovenop de stapel worden geplaatst. Als iemand een bord pakt, halen ze het ook van de bovenkant af. Het blijkt dat de platen worden gedemonteerd in de tegenovergestelde volgorde als waarin ze zijn geplaatst.

Nu we begrijpen hoe een stapel werkt, gaan we een paar termen introduceren. De handeling waarbij een element aan de stapel wordt toegevoegd, wordt “push” genoemd, en het verwijderen ervan wordt “pop” genoemd. Het laatst toegevoegde element wordt de bovenkant van de stapel of "top" genoemd en kan worden bekeken met behulp van de "peek" -bewerking. Laten we nu naar de sjabloon kijken van een klasse die een stapel implementeert.

Stapel klasse

De klasse Stack definieert de methoden Push, Pop en Peek voor toegang tot elementen, en een veld Count. In de implementatie zullen we LinkedList gebruiken voor het opbergen van elementen.

Openbare klasse Stack ( LinkedList _items = new LinkedList(); public void Push(T-waarde) ( gooi nieuwe NotImplementedException(); ) public T Pop() ( gooi nieuwe NotImplementedException(); ) public T Peek() ( gooi nieuw NotImplementedException( ) public int Count (get;) )

Push-methode

• Gedrag: Voegt een element toe aan de bovenkant van de stapel.
• Complexiteit: O(1).

Omdat we een gekoppelde lijst gebruiken om elementen op te slaan, kunnen we eenvoudigweg een nieuwe aan het einde van de lijst toevoegen.

Publieke leegte Push(T-waarde) ( _items.AddLast(waarde); )

Pop-methode

• Gedrag: Verwijdert een element van de bovenkant van de stapel en geeft het terug. Als de stapel leeg is, wordt InvalidOperationException gegenereerd.
• Complexiteit: O(1).

Push voegt elementen toe aan het einde van de lijst, zodat deze ook aan het einde worden geplaatst. Als de lijst leeg is, wordt er een uitzondering gegenereerd.

Public T Pop() ( if (_items.Count == 0) ( throw new InvalidOperationException("De stapel is leeg"); ) T resultaat = _items.Tail.Value; _items.RemoveLast(); retourneert resultaat; )

Peek-methode

• Gedrag: Geeft het bovenste element van de stapel terug, maar verwijdert het niet. Als de stapel leeg is, wordt InvalidOperationException gegenereerd.
• Complexiteit: O(1).

Telmethode

• Gedrag: Geeft het aantal elementen in de stapel terug.
• Complexiteit: O(1).

Waarom moeten we weten hoeveel elementen er op de stapel staan ​​als we er toch geen toegang toe hebben? Met dit veld kunnen we controleren of er elementen op de stapel staan ​​of dat deze leeg is. Dit is erg handig gezien het feit dat de Pop-methode een uitzondering genereert.

Voorbeeld: rekenmachine in omgekeerde Poolse notatie.

Een klassiek voorbeeld van het gebruik van een stapel is een rekenmachine in omgekeerde Poolse of postfix-notatie. De operator staat erin geschreven na hun operanden. Dat wil zeggen, we schrijven:

<операнд> <операнд> <оператор>

in plaats van de traditionele:

<операнд> <оператор> <операнд>

Met andere woorden, in plaats van “4 + 2” zullen we “4 2 +” schrijven. Als u geïnteresseerd bent in de oorsprong van de omgekeerde Poolse notatie en de naam ervan, kunt u hierover meer te weten komen op Wikipedia of in een zoekmachine.

Hoe de omgekeerde Poolse notatie wordt berekend en waarom de stapel zo handig is bij het gebruik ervan, blijkt duidelijk uit het volgende algoritme:

Voor elke invoerwaarde, als de waarde een geheel getal is, duwt u de waarde naar de operandstapel, anders als de waarde een operator is, popt u de linker- en rechterwaarden van de stapel, evalueert u de operator, duwt het resultaat naar de stapel, popt het antwoord van de stapel .

Dat wil zeggen, voor de uitdrukking "4 2 +" zullen de acties als volgt zijn:

Duwen(4) duwen(2) duwen(knallen() + knallen())

Aan het einde zal er één waarde op de stapel staan: 6.

Het volgende is de volledige code voor een eenvoudige rekenmachine die een uitdrukking (bijvoorbeeld 4 2 +) van de console leest, de invoer opsplitst in spaties ("4", "2", "+"]) en de berekening uitvoert algoritme. De evaluatie gaat door totdat het woord quit wordt aangetroffen.

Void RpnLoop() ( while (true) ( ​​Console.Write("> "); string input = Console.ReadLine(); if (input.Trim().ToLower() == "quit") ( break; ) / / Stapel waarden nog niet verwerkt. Stapelwaarden = new Stack(); int value; if (int. TryParse(token, out value)) ( // ... zet het op de stapel. waarden.Push(waarde); ) else ( // voer anders de bewerking uit... int rhs = waarden .Pop(); int lhs = waarden.Pop(); // ... en plaats de resultaatschakelaar (token) ( case "+": waarden.Push(lhs + rhs); break; case "-" : waarden.Push(lhs - rhs); waarden.Push(lhs * rhs); Als de bewerking niet +, -, * of / throw new ArgumentException(string.Format("Unrecognized token: (0)", token) ) ) // Het laatste element op de stapel is het resultaat Console.WriteLine(values .Knal()); ))

Wachtrij

Wachtrijen lijken sterk op stapels. Ook geven ze geen toegang tot een willekeurig element, maar zijn de elementen, in tegenstelling tot een stapel, gestapeld (in de rij staan) en klimmen (uit de wachtrij) van verschillende kanten. Deze methode heet ‘first in, first out’ (First-In-First-Out of FIFO). Dat wil zeggen dat we elementen uit de wachtrij halen in dezelfde volgorde als waarin we ze hebben geplaatst. Als een echte wachtrij of lopende band.

Wachtrijen worden vaak in programma's gebruikt om een ​​buffer te bieden waarin items kunnen worden geplaatst voor latere verwerking, terwijl de volgorde waarin ze aankomen behouden blijft. Als de database bijvoorbeeld slechts één verbinding ondersteunt, kunt u een wachtrij met threads gebruiken die, vreemd genoeg, op hun beurt wachten om toegang te krijgen tot de database.

Wachtrij klasse

De klasse Queue zal, net als de stapel, worden geïmplementeerd met behulp van een gekoppelde lijst. Het biedt Enqueue om een ​​element toe te voegen, Dequeue om te verwijderen, Peek en Count-methoden. Net als de klasse Stack zal deze de ICollection-interface niet implementeren , aangezien dit collecties voor speciale doeleinden zijn.

Openbare klasse wachtrij ( LinkedList _items = nieuwe LinkedList(); public void Enqueue(T-waarde) ( nieuwe NotImplementedException(); ) openbare T Dequeue() ( nieuwe NotImplementedException(); ) openbare T Peek() ( nieuwe NotImplementedException( ) public int Count (get;) )

Enqueue-methode

• Gedrag: Voegt een element toe aan de wachtrij.
• Complexiteit: O(1).

Nieuwe wachtrij-elementen kunnen aan het begin van de lijst of aan het einde worden toegevoegd. Het is alleen belangrijk dat de elementen vanaf de tegenoverliggende rand worden bereikt. In deze implementatie zullen we nieuwe elementen toevoegen aan het begin van de interne lijst.

Publieke leegte Enqueue(T-waarde) ( ​​_items.AddFirst(waarde); )

Dequeue-methode

• Gedrag: Verwijdert het eerst geplaatste element uit de wachtrij en retourneert het. Als de wachtrij leeg is, wordt InvalidOperationException gegenereerd.
• Complexiteit: O(1).

Omdat we elementen aan het begin van de lijst invoegen, zullen we ze aan het einde verwijderen. Als de lijst leeg is, wordt er een uitzondering gegenereerd.

Public T Dequeue() ( if (_items.Count == 0) ( throw new InvalidOperationException("De wachtrij is leeg"); ) T last = _items.Tail.Value; _items.RemoveLast(); return laatste; )

Peek-methode

• Gedrag: Retourneert het element dat wordt geretourneerd door de volgende aanroep van de Dequeue-methode. De wachtrij blijft ongewijzigd. Als de wachtrij leeg is, wordt InvalidOperationException gegenereerd.
• Complexiteit: O(1).

Telmethode

• Gedrag:
• Complexiteit: O(1).

Wachtrij in twee richtingen

Wachtrij in twee richtingen (Dubbele wachtrij), of december (Deque), breidt het gedrag van de wachtrij uit. In een deque kun je zowel aan het begin als aan het einde van de wachtrij elementen toevoegen of verwijderen. Dit gedrag is nuttig bij veel taken, zoals het plannen van threads of het implementeren van andere gegevensstructuren. Later zullen we kijken naar het implementeren van een stapel met behulp van een deque.

Deque klasse

De klasse Deque is het gemakkelijkst te implementeren met behulp van een dubbel gekoppelde lijst. Hiermee kunt u elementen aan het begin en einde van de lijst bekijken, verwijderen en toevoegen. Het belangrijkste verschil tussen een tweerichtingswachtrij en een gewone wachtrij is dat de methoden Enqueue , Dequeue en Peek in paren zijn opgesplitst om aan beide uiteinden van de lijst te werken.

Openbare klasse Deque ( LinkedList _items = new LinkedList(); public void EnqueueFirst(T-waarde) ( gooi nieuwe NotImplementedException(); ) public void EnqueueLast(T-waarde) ( gooi nieuwe NotImplementedException(); ) public T DequeueFirst( ) (gooi nieuwe NotImplementedException(); ) public T DequeueLast() (gooi nieuwe NotImplementedException(); ) public T PeekFirst() (gooi nieuwe NotImplementedException(); ) public T PeekLast() (gooi nieuwe NotImplementedException(); ) public int Tel (krijg; ) )

EnqueueFirst-methode

• Gedrag:
• Complexiteit: O(1).

EnqueueLast-methode

• Gedrag:
• Complexiteit: O(1).

DequeueFirst-methode

• Gedrag: Verwijdert een element van de voorkant van de wachtrij en retourneert het. Als de wachtrij leeg is, wordt InvalidOperationException gegenereerd.
• Complexiteit: O(1).

DequeueLast-methode

• Gedrag:
• Complexiteit: O(1).

PeekFirst-methode

• Gedrag: Retourneert een element vanaf het begin van de wachtrij zonder dit te wijzigen. Als de wachtrij leeg is, wordt InvalidOperationException gegenereerd.
• Complexiteit: O(1).

PeekLast-methode

• Gedrag:
• Complexiteit: O(1).

Telmethode

• Gedrag: Retourneert het aantal elementen in de wachtrij, of 0 als de wachtrij leeg is.
• Complexiteit: O(1).

Voorbeeld: Stack-implementatie

Een deque wordt vaak gebruikt om andere datastructuren te implementeren. Laten we eens kijken naar een voorbeeld van het implementeren van een stapel die deze gebruikt.

U vraagt ​​zich misschien af ​​waarom u een stapel implementeert op basis van een wachtrij in plaats van een gekoppelde lijst. Er zijn twee redenen: prestaties en hergebruik van code. Een gekoppelde lijst heeft overhead voor het maken van knooppunten en geen garantie voor de locatie van de gegevens: elementen kunnen zich overal in het geheugen bevinden, wat een groot aantal fouten en prestatieverlies op processorniveau veroorzaakt. Een meer performante implementatie van een deque vereist een array om de elementen op te slaan.

Het implementeren van een stapel of wachtrij met behulp van een array is echter geen gemakkelijke taak, maar het implementeren van een deque en het gebruiken ervan als basis voor andere datastructuren zal ons serieuze prestatievoordelen opleveren en ons in staat stellen code te hergebruiken. Hierdoor worden de ondersteuningskosten verlaagd.

We zullen later kijken naar een variant van een wachtrij met behulp van een array, maar laten we eerst eens kijken naar de stapelklasse met behulp van een dequeue:

Openbare klasse Stack ( Deque _items = new Deque(); public void Push(T-waarde) ( _items.EnqueueFirst(value); ) public T Pop() ( return _items.DequeueFirst(); ) public T Peek() ( return _items.PeekFirst(); public int Count (get (retourneer _items.Count; ) ))

Houd er rekening mee dat alle foutafhandeling nu wordt afgehandeld door de klasse Deque, en dat bovendien elke wachtrijoptimalisatie ook op de stapel wordt weerspiegeld. Het implementeren van een reguliere retourwachtrij is zo eenvoudig dat we het als een oefening voor de lezer laten.

Elementen opslaan in een array

Zoals eerder vermeld heeft het implementeren van een wachtrij met behulp van een array zijn voordelen. Het lijkt eenvoudig, maar in feite zijn er een aantal nuances waarmee rekening moet worden gehouden.

Laten we eens kijken naar de problemen die zich kunnen voordoen en hoe we deze kunnen oplossen. Daarnaast hebben we informatie nodig over het vergroten van de interne array uit het vorige artikel over dynamische arrays.

Wanneer een wachtrij wordt gemaakt, wordt daarin een array met lengte nul gemaakt. De rode letters "h" en "t" staan ​​respectievelijk voor de _head- en _tail-aanwijzers.

Deque deq = nieuwe Deque(); deq.EnqueueFirst(1);

Deq.EnqueueLast(2);

Deq.EnqueueFirst(0);

Let op: de index van de “kop” van de wachtrij is naar het begin van de lijst gesprongen. Het eerste element dat wordt geretourneerd bij het aanroepen van de DequeueFirst-methode is nu 0 (index 3).

Deq.EnqueueLast(3);

De array is vol, dus bij het toevoegen van een element gebeurt het volgende:

• Het groeialgoritme bepaalt de grootte van de nieuwe array.
• De elementen worden van kop tot staart naar een nieuwe array gekopieerd.
• Er zal een nieuw element worden toegevoegd.

Laten we nu eens kijken wat er gebeurt als een element wordt verwijderd:

Deq.DequeueFirst();

Deq.DequeueLast();

Belangrijk punt: ongeacht de capaciteit of volheid van de interne array, is de inhoud van de wachtrij logischerwijs elementen van de “kop” tot de “staart”, rekening houdend met de “circulariteit”. Dit gedrag wordt ook wel een "ringbuffer" genoemd.

Laten we nu eens kijken naar de implementatie.

Deque klasse (met behulp van een array)

De interface van een array-gebaseerde wachtrij is hetzelfde als in het geval van een gekoppelde lijstimplementatie. Wij zullen het niet herhalen. Omdat de lijst echter werd vervangen door een array, hebben we nieuwe velden toegevoegd: de array zelf, de grootte ervan en verwijzingen naar de "staart" en "kop" van de wachtrij.

Publieke klasse Deque ( T _items = new T; // Aantal elementen in de wachtrij. int _size = 0; // Index van het eerste (oudste) element. int _head = 0; // Index van het laatste (nieuwste) element . int_staart = -1;

Groei-algoritme

Wanneer de interne array geen vrije ruimte meer heeft, moet deze worden vergroot, de elementen worden gekopieerd en de staart- en hoofdaanwijzers worden bijgewerkt. Deze handeling wordt indien nodig uitgevoerd tijdens het toevoegen van een element. De parameter StartingIndex wordt gebruikt om aan te geven hoeveel velden aan het begin leeg moeten blijven (in het geval van toevoegen aan het begin).

Merk op hoe de gegevens worden opgehaald wanneer u naar het begin van de array moet springen wanneer u van kop naar staart gaat.

Private void allocateNewArray(int startIndex) ( int newLength = (_size == 0) ? 4: _size * 2; T newArray = nieuwe T; if (_size > 0) ( int targetIndex = startIndex; // Kopieer de inhoud... // Als de array geen lus heeft, kopieer dan gewoon de elementen. // Kopieer anders van de kop naar het einde en dan van het begin van de array naar de staart. // Als de staart kleiner is dan de kop, ga dan naar het begin (_staart.< _head) { // Копируем _items.._items в newArray..newArray[N]. for (int index = _head; index < _items.Length; index++) { newArray = _items; targetIndex++; } // Копируем _items.._items в newArray.. for (int index = 0; index <= _tail; index++) { newArray = _items; targetIndex++; } } else { // Копируем _items.._items в newArray..newArray[N] for (int index = _head; index <= _tail; index++) { newArray = _items; targetIndex++; } } _head = startingIndex; _tail = targetIndex - 1; } else { // Массив пуст. _head = 0; _tail = -1; } _items = newArray; }

EnqueueFirst-methode

• Gedrag: Voegt een element toe aan het begin van de wachtrij. Dit element wordt vervolgens uit de wachtrij gehaald wanneer de DequeueFirst-methode wordt aangeroepen.
• Complexiteit:

EnqueueLast-methode

• Gedrag: Voegt een element toe aan het einde van de wachtrij. Dit element wordt vervolgens uit de wachtrij gehaald wanneer de DequeueLast-methode wordt aangeroepen.
• Complexiteit: O(1) in de meeste gevallen; O(n) wanneer array-uitbreiding nodig is.

DequeueFirst-methode

• Gedrag: Verwijdert een element uit het begin van de wachtrij en retourneert het. Als de wachtrij leeg is, wordt InvalidOperationException gegenereerd.
• Complexiteit: O(1).

DequeueLast-methode

• Gedrag: Verwijdert een element van het einde van de wachtrij en retourneert het. Als de wachtrij leeg is, wordt InvalidOperationException gegenereerd.
• Complexiteit: O(1).

PeekFirst-methode

• Gedrag: Retourneert het element vanaf het begin van de wachtrij zonder het te wijzigen. Als de wachtrij leeg is, wordt InvalidOperationException gegenereerd.
• Complexiteit: O(1).

PeekLast-methode

• Gedrag: Retourneert een element vanaf het einde van de wachtrij zonder het te wijzigen. Als de wachtrij leeg is, wordt InvalidOperationException gegenereerd.
• Complexiteit: O(1).

Telmethode

• Gedrag: Retourneert het aantal elementen in de wachtrij, of 0 als de wachtrij leeg is.
• Complexiteit: O(1).

Wordt vervolgd

Inmiddels hebben wij het vierde deel van onze artikelenreeks afgerond. Daarin keken we naar stapels en wachtrijen. De volgende keer gaan we verder met binaire zoekbomen.

Een stapel is een algemene gegevensstructuur voor het weergeven van gegevens die in een specifieke volgorde moeten worden verwerkt. Wanneer een functie bijvoorbeeld een andere functie aanroept, die op zijn beurt een derde functie aanroept, is het belangrijk dat de derde functie terugkeert naar de tweede functie, en niet naar de eerste.

Eén manier om deze gegevensverwerkingsvolgorde te implementeren is door een soort wachtrij met functieaanroepen te organiseren. De laatst aan de stapel toegevoegde functie wordt als eerste voltooid en omgekeerd wordt de eerste functie die aan de stapel wordt toegevoegd als laatste voltooid. De datastructuur zelf zorgt dus voor de juiste volgorde van oproepen.

Conceptueel gezien is de stapelgegevensstructuur heel eenvoudig: u kunt er elementen in een specifieke volgorde aan toevoegen of verwijderen. Elke keer dat een element wordt toegevoegd, komt het bovenaan de stapel te staan. Het enige element dat van de stapel kan worden verwijderd, is het element dat zich bovenaan de stapel bevindt. De stapel is dus, zoals we zeggen, “first in, last out - FILO” of “last in, first out – LIFO”. Het eerste element dat aan de stapel wordt toegevoegd, is het laatste element dat ervan wordt verwijderd.

Dus wat is er aan de hand? Waarom hebben we stapels nodig? Zoals we al zeiden, zijn stapels een handige manier om functieaanroepen te organiseren. In feite is "call stack" een term die vaak wordt gebruikt om te verwijzen naar een lijst met functies die momenteel worden uitgevoerd of wachten op de retourwaarde van andere functies.

In zekere zin maken stapels deel uit van de fundamentele taal van de informatica. Wanneer u een first-in, last-out-wachtrij wilt implementeren, is het zinvol om over stapels te praten met behulp van algemene terminologie. Bovendien zijn dergelijke wachtrijen betrokken bij veel processen, variërend van theoretische informatica, zoals push-down-functies en nog veel meer.

Stapels hebben een aantal bijbehorende methoden:

• Duw— voeg een element toe aan de stapel;
• Knal— verwijder een element van de stapel;
• Kijkje— stapelelementen bekijken;
• LIFO— stapelgedrag,
• FILO Gelijk aan LIFO

Deze stapel is geïmplementeerd met sjablonen, zodat deze voor vrijwel elk gegevenstype kan worden gebruikt. Bovendien wordt de stapelgrootte dynamisch bepaald tijdens de uitvoering van het programma. Er is ook een extra functie aan de stapel toegevoegd: peek(), die het n-de element vanaf de bovenkant van de stapel laat zien.