Share
Tot dusver hebben we gekeken naar collecties die een zeer eenvoudige gegevensopslag bieden, in wezen abstracties over een array. In dit gedeelte gaan we kijken naar wat er gebeurt als we enkele zeer basale gedragingen toevoegen die het nut van de collecties volledig veranderen.
Een stapel is een verzameling die objecten terugstuurt naar de beller in een Last-in-First-Out (LIFO) -patroon. Wat dit betekent is dat het laatste object dat aan de verzameling is toegevoegd, het eerste object is dat wordt geretourneerd.
Stacks verschillen van lijst en array-achtige collecties. Ze kunnen niet rechtstreeks worden geïndexeerd, objecten worden op verschillende manieren toegevoegd en verwijderd en de inhoud ervan is ondoorzichtiger dan lijsten en matrices. Wat ik hiermee bedoel is dat hoewel een lijst-gebaseerde verzameling een Bevat-methode biedt, een stapel dat niet doet. Bovendien is een stapel niet opsombaar. Om te begrijpen waarom dit is, laten we eens kijken naar wat een stapel is en hoe het gebruik van een stapel deze verschillen stuurt.
Een van de meest voorkomende analogieën voor een stapel is de restaurantbordenstapel. Dit is een eenvoudig veerbelast apparaat waarop schone platen worden gestapeld. De veer zorgt ervoor dat, ongeacht het aantal platen in de stapel, de bovenplaat gemakkelijk toegankelijk is. Schone platen worden toegevoegd aan de bovenkant van de stapel en wanneer een klant een plaat verwijdert, verwijdert hij of zij de bovenste plaat (de laatst toegevoegde plaat).
We beginnen met een leeg bordenrek.
Een lege platenstapel (de veer houdt geen platen vast) En dan voegen we een rode, een blauwe en een groene plaat toe aan het rek in die volgorde.
Het belangrijkste punt om te begrijpen is dat wanneer nieuwe platen worden toegevoegd, deze aan de bovenkant van de stapel worden toegevoegd. Als een klant een bord ophaalt, krijgt hij of zij de laatst toegevoegde plaat (de groene plaat). De volgende klant krijgt de blauwe plaat en uiteindelijk wordt de rode plaat verwijderd.
Nu we begrijpen hoe een stapel werkt, laten we een paar nieuwe termen definiëren. Wanneer een item aan de stapel wordt toegevoegd, wordt het "ingedrukt" bij het gebruik van de Duwen methode. Wanneer een item uit de stapel wordt verwijderd, wordt het "weggekropen" met behulp van de Knal methode. Het bovenste item in de stapel, het meest recent toegevoegd, kan worden "gekeken" bij het gebruik van de Kijkje methode. Met Gluren kunt u het item bekijken zonder het van de stapel te verwijderen (net zoals de klant bij het bordenrek de kleur van de bovenplaat zou kunnen zien). Laten we met deze voorwaarden in ons achterhoofd kijken naar de implementatie van een stack klasse.
De stack klasse definieert Duwen, Knal, en Kijkje methoden, a tellen eigendom, en gebruikt de LinkedList klasse om de waarden in de stapel op te slaan.
public class Stack LinkedList _items = new LinkedList (); public void Push (T-waarde) gooi nieuwe NotImplementedException (); public T Pop () gooi new NotImplementedException (); public T Peek () gooi nieuwe NotImplementedException (); openbare int Graaf krijgen;
| Gedrag | Voegt een item toe aan de bovenkant van de stapel. |
| Prestatie | O (1) |
Omdat we een gekoppelde lijst gebruiken als onze back-upwinkel, hoeven we alleen maar het nieuwe item aan het einde van de lijst toe te voegen.
public void Push (T-waarde) _items.AddLast (waarde);
| Gedrag | Verwijdert en retourneert het laatste item dat aan de stapel is toegevoegd. Als de stapel leeg is, InvalidOperationException wordt gegooid. |
| Prestatie | O (1) |
Duwen voegt items toe aan de achterkant van de lijst, dus we "poppen" ze vanaf de achterkant. Als de lijst leeg is, wordt een uitzondering gegenereerd.
Accentsconagua
public T Pop () if (_items.Count == 0) gooi new InvalidOperationException ("De stapel is leeg"); T result = _items.Tail.Value; _items.RemoveLast (); terugkeer resultaat; | Gedrag | Retourneert het laatste item dat aan de stapel is toegevoegd maar laat het item op de stapel. Als de stapel leeg is, InvalidOperationException wordt gegooid. |
| Prestatie | O (1) |
public T Peek () if (_items.Count == 0) gooi new InvalidOperationException ("De stapel is leeg"); return _items.Tail.Value; | Gedrag | Retourneert het aantal items in de stapel. |
| Prestatie | O (1) |
Aangezien de stack een ondoorzichtige gegevensstructuur moet zijn, waarom hebben we dan een tellen eigendom? Weten of een stapel leeg is (Graaf == 0) is erg handig, vooral sindsdien Knal werpt een uitzondering wanneer de stapel leeg is.
public int Count krijg return _items.Count;
Het klassieke stack-voorbeeld is de Reverse Polish Notation (RPN) -calculator.
RPN-syntaxis is vrij eenvoudig. Het gebruikt:
in plaats van de traditionele:
Met andere woorden, in plaats van '4 + 2' te zeggen, zouden we '4 2 +' zeggen. Als u de historische betekenis van de syntaxis van RPN wilt begrijpen, raad ik u aan naar Wikipedia of uw favoriete zoekmachine te gaan..
De manier waarop RPN wordt geëvalueerd en de reden dat een stapel zo handig is bij het implementeren van een RPN-rekenmachine, is te zien in het volgende algoritme:
voor elke invoerwaarde als de waarde een geheel getal is, duwt u de waarde aan naar de operandstapel anders als de waarde een operator is pop de linker- en rechterwaarden van de stapel evalueren de operator duwt het resultaat naar de stapel pop antwoord van stapel.
Dus gezien de invoertekenreeks "4 2 +", zouden de bewerkingen zijn:
druk (4) druk (2) druk (pop () + pop ())
De stapel bevat nu een enkele waarde: zes (het antwoord).
Het volgende is een volledige implementatie van een eenvoudige rekenmachine die een vergelijking (bijvoorbeeld "4 2 +") van de console-invoer leest, de invoer op elke spatie splitst (["4", "2" en "+"]) , en voert het RPN-algoritme op de invoer uit. De lus gaat door totdat de invoer het woord "quit" is.
void RpnLoop () while (true) Console.Write (">"); string input = Console.ReadLine (); if (input.Trim (). ToLower () == "quit") break; // De stapel gehele getallen die nog niet zijn geopereerd. Stapelwaarden = nieuwe stapel (); foreach (string token in input.Split (new char [] ")) // Als de waarde een geheel getal is ... int value; if (int.TryParse (token, out value)) // ... push it to de stack. values.Push (waarde); else // Anders evalueren de expressie ... int rhs = values.Pop (); int lhs = values.Pop (); // ... en laat het resultaat terug naar de stapel. switch (token) case "+": values.Push (lhs + rhs); break; case "-": values.Push (lhs - rhs); break; case "*": values.Push (lhs * rhs) ; break; case "/": values.Push (lhs / rhs); break; case "%": values.Push (lhs% rhs); break; standaard: throw new ArgumentException (string.Format ("Unrecognized token: 0 ", token)); // Het laatste item op de stapel is het resultaat. Console.WriteLine (values.Pop ()); Wachtrijen lijken veel op stacks: ze bieden een ondoorzichtige verzameling waaruit objecten kunnen worden toegevoegd (in de wachtrij worden geplaatst) of verwijderd (verwijderd) op een manier die waarde toevoegt aan een op lijsten gebaseerde verzameling.
Wachtrijen zijn een First-in-First-Out (FIFO) -collectie. Dit betekent dat items uit de wachtrij worden verwijderd in dezelfde volgorde waarin ze zijn toegevoegd. U kunt een wachtrij zoals een lijn bij een kassa in de winkel zien. Tegenstanders komen in de rij en worden gerepareerd in de volgorde waarin ze aankomen.
Wachtrijen worden vaak gebruikt in toepassingen om een buffer te bieden om items toe te voegen voor toekomstige verwerking of om ordelijke toegang tot een gedeelde bron te bieden. Als een database bijvoorbeeld slechts één verbinding kan verwerken, kan een wachtrij worden gebruikt om te zorgen dat threads hun beurt (in volgorde) wachten om toegang te krijgen tot de database.
De Wachtrij, zoals de stack, wordt ondersteund door een LinkedList. Bovendien biedt het de methoden enqueue (om items toe te voegen), dequeue (om items te verwijderen), Kijkje, en tellen. Net zoals stack, het zal niet worden behandeld als een verzameling voor algemene doeleinden, wat betekent dat het niet wordt uitgevoerd ICollection.
openbare klassenwachtrij LinkedList _items = nieuwe LinkedList (); public void Enqueue (T-waarde) gooi nieuwe NotImplementedException (); public T Dequeue () gooi new NotImplementedException (); public T Peek () gooi nieuwe NotImplementedException (); openbare int Graaf krijgen;
| Gedrag | Voegt een item toe aan het einde van de wachtrij. |
| Prestatie | O (1) |
Met deze implementatie wordt het item toegevoegd aan het begin van de gekoppelde lijst. Het item kan net zo goed aan het einde van de lijst worden toegevoegd. Het enige dat er echt toe doet, is dat items aan het einde van de lijst worden geplaatst en uit de andere worden verwijderd (FIFO). Merk op dat dit het tegenovergestelde is van de Stack-klasse waar items worden toegevoegd en verwijderd van hetzelfde uiteinde (LIFO).
Public void Enqueue (T-waarde) _items.AddFirst (waarde);
| Gedrag | Verwijdert en retourneert het oudste item uit de wachtrij. Een InvalidOperationException wordt weggegooid als de wachtrij leeg is. |
| Prestatie | O (1) |
Sinds enqueue heeft het item toegevoegd aan het begin van de lijst, dequeue moet het item aan het einde van de lijst verwijderen. Als de wachtrij geen items bevat, wordt een uitzondering gegenereerd.
public T Dequeue () if (_items.Count == 0) gooi new InvalidOperationException ("De wachtrij is leeg"); T last = _items.Tail.Value; _items.RemoveLast (); terugkeer laatste; | Gedrag | Retourneert het volgende item dat zou worden geretourneerd als Dequeue werd aangeroepen. De wachtrij blijft ongewijzigd. Een ongeldige bewerkingsexception wordt gegenereerd als de wachtrij leeg is. |
| Prestatie | O (1) |
public T Peek () if (_items.Count == 0) gooi new InvalidOperationException ("De wachtrij is leeg"); return _items.Tail.Value; | Gedrag | Retourneert het aantal items dat momenteel in de wachtrij staat. Retourneert 0 als de wachtrij leeg is. |
| Prestatie | O (1) |
public int Count krijg return _items.Count;
Een wachtrij met twee einden, of deque, breidt het gedrag van de wachtrij uit door toe te staan dat items aan beide zijden van de wachtrij worden toegevoegd of verwijderd. Dit nieuwe gedrag is nuttig in verschillende probleemdomeinen, met name taak- en threadplanning. Het is ook over het algemeen nuttig voor het implementeren van andere datastructuren. We zullen een voorbeeld zien van het gebruik van een deque om later een andere datastructuur te implementeren.
De Deque klasse wordt ondersteund door een dubbel gelinkte lijst. Dit stelt ons in staat om items aan de voor- of achterkant van de lijst toe te voegen en te verwijderen en toegang te krijgen tot de Eerste en Laatste eigenschappen. De belangrijkste wijzigingen tussen de klasse Wachtrij en de klasse Deque zijn dat de enqueue, dequeue, en Kijkje methoden zijn verdubbeld Eerste en Laatste varianten.
public class Deque LinkedList _items = new LinkedList (); public void EnqueueFirst (T-waarde) gooi new 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 new NotImplementedException (); openbare int Graaf krijgen;
| Gedrag | Voegt de opgegeven waarde toe aan de kop van de wachtrij. Dit is het volgende item dat wordt uitgeleend door DequeueFirst. |
| Prestatie | O (1) |
public void EnqueueFirst (T-waarde) _items.AddFirst (waarde);
| Gedrag | Voegt de opgegeven waarde toe aan de staart van de wachtrij. Dit is het volgende item dat wordt uitgeleend door DequeueLast. |
| Prestatie | O (1) |
public void EnqueueLast (T-waarde) _items.AddLast (value);
| Gedrag | Verwijdert en retourneert het eerste item in de deque. Een ongeldige bewerkingsexception wordt gegenereerd als de deque leeg is. |
| Prestatie | O (1) |
public T DequeueFirst () if (_items.Count == 0) gooi new InvalidOperationException ("DequeueFirst called when deque empty is"); T temp = _items.Head.Value; _items.RemoveFirst (); terugkeer temp; | Gedrag | Verwijdert en retourneert het laatste item in de deque. Een ongeldige bewerkingsexception wordt gegenereerd als de deque leeg is. |
| Prestatie | O (1) |
public T DequeueLast () if (_items.Count == 0) gooi new InvalidOperationException ("DequeueLast called when deque empty is"); T temp = _items.Tail.Value; _items.RemoveLast (); terugkeer temp; | Gedrag | Retourneert het eerste item in de deque maar laat de verzameling ongewijzigd. Een ongeldige bewerkingsexception wordt gegenereerd als de deque leeg is. |
| Prestatie | O (1) |
public T PeekFirst () if (_items.Count == 0) gooi new InvalidOperationException ("PeekFirst called when deque empty is"); return _items.Head.Value; | Gedrag | Retourneert het laatste item in de deque maar laat de verzameling ongewijzigd. Een ongeldige bewerkingsexception wordt gegenereerd als de deque leeg is. |
| Prestatie | O (1) |
public T PeekLast () if (_items.Count == 0) gooi new InvalidOperationException ("PeekLast called when deque empty is"); return _items.Tail.Value; | Gedrag | Retourneert het aantal items dat zich momenteel in de deque bevindt, of 0 als de deque leeg is. |
| Prestatie | O (1) |
public int Count krijg return _items.Count;
Deques worden vaak gebruikt om andere datastructuren te implementeren.
We hebben een stapel geïmplementeerd met een LinkedList, dus laten we nu kijken naar een geïmplementeerd met een Deque.
Je vraagt je misschien af waarom ik ervoor zou kiezen om een te implementeren stack met behulp van een Deque liever dan een LinkedList. De reden is een van de prestaties en hergebruik van code. Een gelinkte lijst heeft de kosten van per-node overhead en verminderde datalocatie - de items worden in de heap toegewezen en de geheugenlocaties zijn mogelijk niet in de buurt van elkaar, waardoor er meer cache-missers en paginafouten optreden bij de CPU en geheugenhardware levels. Een beter presterende implementatie van een wachtrij gebruikt mogelijk een array als het back-uparchief in plaats van een lijst. Dit zou leiden tot minder overheadkosten per knooppunt en zou de prestaties kunnen verbeteren door een aantal problemen met de locatie aan te pakken.
Implementatie van een stack of Wachtrij als een array echter een complexere implementatie is. Door de Deque op deze meer complexe manier en door het te gebruiken als de basis voor andere datastructuren, kunnen we de prestatievoordelen voor alle structuren realiseren, terwijl we de code slechts eenmaal hoeven te schrijven. Dit versnelt de ontwikkelingstijd en verlaagt de onderhoudskosten.
We zullen kijken naar een voorbeeld van een Deque als een array verderop in dit gedeelte, maar laten we eerst eens kijken naar een voorbeeld van een stack geïmplementeerd met behulp van een Deque.
public class Stack Deque _items = new Deque (); public void Push (T-waarde) _items.EnqueueFirst (waarde); public T Pop () return _items.DequeueFirst (); public T Peek () return _items.PeekFirst (); public int Count krijg return _items.Count;
Merk op dat alle foutcontroles nu worden uitgesteld naar de Deque en elke optimalisatie of bugfix die is gemaakt naar de Deque zal automatisch van toepassing zijn op de stack klasse. Implementatie van een Wachtrij is net zo eenvoudig en als zodanig overblijft als een oefening voor de lezer.
Zoals eerder vermeld, zijn er voordelen verbonden aan het gebruik van een array in plaats van een gekoppelde lijst als de back-upopslag voor de Deque (een deque van gehele getallen). Conceptueel lijkt dit eenvoudig, maar er zijn eigenlijk verschillende zaken die moeten worden aangepakt om dit te laten werken.
Laten we een aantal van deze problemen grafisch bekijken en dan kijken hoe we ze kunnen aanpakken. Houd daarbij rekening met de problemen van het groeibeleid die zijn besproken in de sectie ArrayList en dat dezelfde problemen hier gelden.
Wanneer de verzameling is gemaakt, is deze een array van 0-lengte. Laten we eens kijken naar hoe sommige acties de interne array beïnvloeden. Let er bij het doorlezen op dat de groene "h" en rode "t" in de figuren respectievelijk verwijzen naar "head" en "tail". De kop en de staart zijn de array-indices die de eerste en laatste items in de wachtrij aangeven. Als we items toevoegen en verwijderen, wordt de interactie tussen hoofd en staart duidelijker.
Deque deq = new Deque (); deq.EnqueueFirst (1);
Een waarde toevoegen aan de voorkant van de deque deq.EnqueueLast (2);
Een waarde toevoegen aan het einde van de deque deq.EnqueueFirst (0);
Een andere waarde toevoegen aan de voorkant van de deque; de hoofdindex wikkelt rond Let op wat er op dit punt is gebeurd. De kopindex is rond het einde van de array gewikkeld. Nu het eerste item in de deque, wat zou worden geretourneerd door DequeueFirst, is de waarde bij reeksindex drie (nul).
deq.EnqueueLast (3);
Een waarde toevoegen aan het einde van de deque Op dit punt is de array gevuld. Wanneer een ander item wordt toegevoegd, gebeurt het volgende:
EnqueueFirst - Het item wordt toegevoegd op index nul (de kopieerbewerking laat dit open).EnqueueLast - Het item wordt toegevoegd aan het einde van de array. deq.EnqueueLast (4);
Een waarde toevoegen aan het einde van de uitgebreide deque Laten we nu eens kijken wat er gebeurt als items uit de Deque worden verwijderd.
deq.DequeueFirst ();
Het eerste item verwijderen uit de uitgebreide deque deq.DequeueLast ();
Het laatste item uit de uitgebreide deque verwijderen Het kritieke punt om op te merken is dat, ongeacht de capaciteit van de interne array, de logische inhoud van de Deque de items zijn van de index van de kop tot de staartindex, rekening houdend met de noodzaak om rond te wikkelen aan het einde van de array. Een array die het gedrag van het omwikkelen van het hoofd naar de staart biedt, staat vaak bekend als een circulaire buffer.
Met dit inzicht in hoe de array-logica werkt, laten we direct de code in duiken.
De array-gebaseerde Deque-methoden en -eigenschappen zijn dezelfde als op basis van de lijst, dus ze worden hier niet herhaald. De lijst is echter vervangen door een array en er zijn nu drie eigenschappen die de grootte, kop en staartinformatie bevatten.
public class Deque T [] _items = new T [0]; // Het aantal items in de wachtrij. int _size = 0; // De index van het eerste (oudste) item in de wachtrij. int _head = 0; // De index van het laatste (nieuwste) item in de wachtrij. int _tail = -1; ...
Wanneer de interne array moet groeien, moet het algoritme om de array te vergroten, de array-inhoud te kopiëren en de interne indexwaarden bij te werken, worden uitgevoerd. De enqueue methode voert die bewerking uit en wordt door beide aangeroepen EnqueueFirst en EnqueueLast. De startingIndex parameter wordt gebruikt om te bepalen of de array-slot op index nul open moet (in geval van EnqueueFirst).
Besteed specifieke aandacht aan de manier waarop de gegevens worden uitgepakt in gevallen waarin de stap van kop naar staart moet worden uitgevoerd rond het einde van de array terug naar nul.
private void allocateNewArray (int startingIndex) int newLength = (_size == 0)? 4: _maat * 2; T [] newArray = nieuwe T [newLength]; if (_size> 0) int targetIndex = startIndex; // Kopieer de inhoud ... // Als de array geen wrapping bevat, kopieert u gewoon het geldige bereik. // Anders kopiëren van kop tot eind van de array en vervolgens van 0 naar de staart. // Als de staart minder is dan het hoofd, hebben we gewikkeld. als (_tail < _head) // Copy the _items[head]… _items[end] -> newArray [0] ... newArray [N]. voor (int index = _head; index < _items.Length; index++) newArray[targetIndex] = _items[index]; targetIndex++; // Copy _items[0]… _items[tail] -> newArray [N + 1] ... voor (int index = 0; index <= _tail; index++) newArray[targetIndex] = _items[index]; targetIndex++; else // Copy the _items[head]… _items[tail] -> newArray [0] ... newArray [N] voor (int index = _head; index <= _tail; index++) newArray[targetIndex] = _items[index]; targetIndex++; _head = startingIndex; _tail = targetIndex - 1; // Compensate for the extra bump. else // Nothing in the array. _head = 0; _tail = -1; _items = newArray;
| Gedrag | Voegt de opgegeven waarde toe aan de kop van de wachtrij. Dit is het volgende item dat wordt uitgeleend door DequeueFirst. |
| Prestatie | O (1) in de meeste gevallen; O (n) wanneer groei nodig is. |
public void EnqueueFirst (T item) // Als de array moet groeien. if (_items.Length == _size) allocateNewArray (1); // Omdat we weten dat de array niet vol is en _head groter is dan 0, // weten we dat de sleuf voor het hoofd open is. if (_head> 0) _head--; else // Anders moeten we ons omdraaien naar het einde van de array. _head = _items.Length - 1; _items [_head] = item; _size ++;
| Gedrag | Voegt de opgegeven waarde toe aan de staart van de wachtrij. Dit is het volgende item dat wordt uitgeleend door DequeueLast. |
| Prestatie | O (1) in de meeste gevallen; O (n) wanneer groei nodig is. |
public void EnqueueLast (T item) // Als de array moet groeien. if (_items.Length == _size) allocateNewArray (0); // Nu hebben we een array van de juiste grootte en kunnen we ons concentreren op wrapping-problemen. // Als _tail aan het einde van de array is, moeten we ons omdraaien. if (_tail == _items.Length - 1) _tail = 0; else _tail ++; _items [_tail] = item; _size ++;
| Gedrag | Verwijdert en retourneert het eerste item in de deque. Een ongeldige bewerkingsexception wordt gegenereerd als de deque leeg is. |
| Prestatie | O (1) |
public T DequeueFirst () if (_size == 0) gooi new InvalidOperationException ("The deque is empty"); T-waarde = _items [_head]; if (_head == _items.Length - 1) // Als de kop op de laatste index van de array staat, wikkel deze dan om. _head = 0; else // Ga naar het volgende slot. _head ++; _size--; winstwaarde; | Gedrag | Verwijdert en retourneert het laatste item in de deque. Een ongeldige bewerkingsexception wordt gegenereerd als de deque leeg is. |
| Prestatie | O (1) |
public T DequeueLast () if (_size == 0) gooi new InvalidOperationException ("De deque is empty"); T-waarde = _items [_tail]; if (_tail == 0) // Als de staart zich bij de eerste index in de array bevindt, wikkel deze dan om. _tail = _items.Length - 1; else // Ga naar het vorige slot. _staart--; _size--; winstwaarde; | Gedrag | Retourneert het eerste item in de deque maar laat de verzameling ongewijzigd. Een InvalidOperationException wordt gegooid als de kaart leeg is. |
| Prestatie | O (1) |
public T PeekFirst () if (_size == 0) gooi new InvalidOperationException ("The deque is empty"); return _items [_head]; | Gedrag | Retourneert het laatste item in de deque maar laat de verzameling ongewijzigd. Een InvalidOperationException wordt gegooid als de kaart leeg is. |
| Prestatie | O (1) |
public T PeekLast () if (_size == 0) gooi new InvalidOperationException ("The deque is empty"); return _items [_tail]; | Gedrag | Retourneert het aantal items dat zich momenteel in de boog bevindt of 0 als de boog leeg is. |
| Prestatie | O (1) |
public int Count krijg return _size;
