Share
Så langt har vi sett på samlinger som gir svært grunnleggende datalagring, i hovedsak abstraksjoner over en matrise. I denne delen skal vi se på hva som skjer når vi legger til noen svært grunnleggende atferd som helt forandrer bruken av samlingene.
En stabel er en samling som returnerer objekter til den som ringer i et siste-i-første-ut-format (LIFO). Hva dette betyr er at det siste objektet i samlingen blir det første objektet som returneres.
Stabler er forskjellige fra liste- og array-lignende samlinger. De kan ikke indekseres direkte, objekter blir lagt til og fjernet ved hjelp av forskjellige metoder, og innholdet er mer ugjennomsiktig enn lister og arrays. Hva jeg mener med dette er at mens en listebasert samling inneholder en Inneholder-metode, gjør en stabel ikke. I tillegg er en stabel ikke enumerable. For å forstå hvorfor dette er, la oss se på hva en stabel er og hvordan bruken av en stabel driver disse forskjellene.
En av de vanligste analogiene for en stabel er restaurantplaten. Dette er en enkel fjærbelastet enhet på hvilken rene plater er stablet. Våren sikrer at uansett hvor mange tallerkener som ligger i stakken, kan toppplaten lett nås. Rene plater legges til toppen av bunken, og når en kunde fjerner en plate, fjerner han eller hun den øverste platen (den sist lagt platen).
Vi starter med en tom plateholder.
En tom plate stabel (fjæren holder ingen plater) Og så legger vi til en rød, en blå og en grønn plate til hyllen i den rekkefølgen.
Nøkkelpunktet å forstå her er at når nye plater legges til, legges de til toppen av stabelen. Hvis en kunde henter en tallerken, vil han eller hun få den nylig lagt platen (den grønne platen). Neste kunde ville få den blå platen, og til slutt ble den røde platen fjernet.
Nå som vi forstår hvordan en stabling fungerer, la oss definere noen nye vilkår. Når et element legges til stabelen, blir det "pushed" på å bruke Trykk metode. Når et element fjernes fra stakken, blir det "poppet" av ved hjelp av Pop metode. Det øverste elementet i stabelen, sist lagt til, kan "kikkes" ved bruk av Peek metode. Peeking gjør at du kan se varen uten å fjerne den fra stakken (akkurat som kunden på tallerkenet ville se fargen på toppplaten). Med disse betingelsene i tankene, la oss se på implementeringen av a Stable klasse.
De Stable klassen definerer Trykk, Pop, og Peek metoder, a Telle eiendom, og bruker Linked klassen for å lagre verdiene i stakken.
offentlig klasse Stack LinkedList _items = new LinkedList (); Offentlig tomrom Push (T-verdi) kaste ny NotImplementedException (); offentlig T Pop () kaste ny NotImplementedException (); offentlig T Peek () kaste ny NotImplementedException (); offentlig int count get;
| Oppførsel | Legger til et element øverst i stabelen. |
| Opptreden | O (1) |
Siden vi bruker en koblet liste som vår backing-butikk, er alt vi trenger å gjøre, å legge til det nye elementet til slutten av listen.
offentlig tomrom Push (T-verdi) _items.AddLast (verdi);
| Oppførsel | Fjerner og returnerer det siste elementet lagt til stakken. Hvis stakken er tom, an InvalidOperationException er kastet. |
| Opptreden | O (1) |
Trykk legger til elementer på baksiden av listen, så vi vil "pop" dem fra baksiden. Hvis listen er tom, kastes et unntak.
Accentsconagua
offentlig T Pop () if (_items.Count == 0) kaste ny InvalidOperationException ("Stakken er tom"); T resultat = _items.Tail.Value; _items.RemoveLast (); returresultat; | Oppførsel | Returnerer det siste elementet lagt til stakken, men legger elementet på stakken. Hvis stakken er tom, an InvalidOperationException er kastet. |
| Opptreden | O (1) |
offentlig T Peek () if (_items.Count == 0) kaste ny InvalidOperationException ("Stakken er tom"); returnere _items.Tail.Value; | Oppførsel | Returnerer antall elementer i stabelen. |
| Opptreden | O (1) |
Siden stakken skal være en ugjennomsiktig datastruktur, hvorfor har vi en Telle eiendom? Å vite om en stabel er tom (Count == 0) er veldig nyttig, spesielt siden Pop kaster et unntak når stakken er tom.
offentlig int Count get return _items.Count;
Det klassiske stakkeksemplet er RPN-kalkulatoren (Reverse Polish Notation).
RPN-syntaks er ganske enkelt. Det bruker:
heller enn den tradisjonelle:
Med andre ord, i stedet for å si "4 + 2", ville vi si "4 2 +." Hvis du vil forstå den historiske betydningen av RPN-syntaks, oppfordrer jeg deg til å lede til Wikipedia eller din favoritt søkemotor.
Måten RPN vurderes på, og årsaken til at en stabel er så nyttig når man implementerer en RPN-kalkulator, kan ses i følgende algoritme:
for hver inngangsverdi dersom verdien er et heltall, trykk verdien til operandstakken ellers hvis verdien er en operatørpopp, vender venstre og høyre verdier fra stakken, vurderer operatøren å trykke resultatet til stakpopsvaret fra stakken.
Så gitt inntastingsstrengen "4 2 +" vil operasjonene være:
trykk (4) trykk (2) trykk (pop () + pop ())
Nå inneholder stabelen en enkelt verdi: seks (svaret).
Følgende er en fullstendig implementering av en enkel kalkulator som leser en ligning (for eksempel "4 2 +") fra konsollinngangen, deler innspillingen i hvert mellomrom (["4", "2" og "+")) , og utfører RPN-algoritmen på inngangen. Sløyfen fortsetter inntil inngangen er ordet "avslutte".
void RpnLoop () while (true) Console.Write (">"); strenginngang = Console.ReadLine (); hvis (input.Trim (). ToLower () == "avslutte") break; // Stakken med heltall som ennå ikke er aktivert. Stack values = new Stack (); foreach (streng token i input.Split (nytt char [] ")) // Hvis verdien er et heltall ... int verdi, hvis (int.TryParse (token, out value)) // ... skyv den til stakken. values.Push (verdi); else // Ellers evaluerer uttrykket ... int rhs = values.Pop (); int lhs = values.Pop (); // ... og pop resultatet tilbake til stakken. bryter (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; default: kaste nye ArgumentException (string.Format ("Ukjent token: 0 ", token)); // Det siste elementet på stakken er resultatet. Console.WriteLine (values.Pop ()); Køer ligner veldig stabler - de gir en ugjennomsiktig samling hvorfra objekter kan legges til (enqueued) eller fjernes (dequeued) på en måte som gir verdi over en listebasert samling.
Køer er en første-i-første-ut-samling (FIFO). Dette betyr at elementer fjernes fra køen i samme rekkefølge som de ble lagt til. Du kan tenke på en kø som en linje i en butikk for kassen, mot-folk går inn i linjen og blir betjent i den rekkefølgen de ankommer.
Køer brukes ofte i applikasjoner for å gi en buffer for å legge til elementer for fremtidig behandling eller for å gi ordnet tilgang til en delt ressurs. Hvis en database for eksempel bare kan håndtere bare en tilkobling, kan en kø brukes til å la tråder vente på sin tur (i rekkefølge) for å få tilgang til databasen.
De Kø, som Stable, støttes av a Linked. I tillegg gir det metodene Enqueue (for å legge til elementer), dequeue (for å fjerne elementer), Peek, og Telle. Som Stable, Det vil ikke bli behandlet som en generell samling, noe som betyr at den ikke vil implementere ICollection.
offentlig klasse Queue LinkedList _items = new LinkedList (); offentlig tomrom Enqueue (T-verdi) kaste ny NotImplementedException (); offentlig T Dequeue () kaste ny NotImplementedException (); offentlig T Peek () kaste ny NotImplementedException (); offentlig int count get;
| Oppførsel | Legger til et element til slutten av køen. |
| Opptreden | O (1) |
Denne implementeringen legger til elementet til starten av den koblede listen. Elementet kan like enkelt legges til slutten av listen. Alt som virkelig betyr noe er at elementene er enqueued til den ene enden av listen og dequeued fra den andre (FIFO). Legg merke til at dette er motsatt av Stack-klassen der elementer blir lagt til og fjernet fra samme ende (LIFO).
Offentlig tomrom Enqueue (T-verdi) _items.AddFirst (verdi);
| Oppførsel | Fjerner og returnerer det eldste elementet fra køen. en InvalidOperationException kastes hvis køen er tom. |
| Opptreden | O (1) |
Siden Enqueue lagt elementet til begynnelsen av listen, dequeue må fjerne elementet på slutten av listen. Hvis køen ikke inneholder noen elementer, kastes et unntak.
offentlig T Dequeue () if (_items.Count == 0) kaste ny InvalidOperationException ("Køen er tom"); T sist = _items.Tail.Value; _items.RemoveLast (); tilbake sist; | Oppførsel | Returnerer neste gjenstand som ville bli returnert dersom Dequeue ble kalt. Køen er uendret. En InvalidOperationException kastes hvis køen er tom. |
| Opptreden | O (1) |
offentlig T Peek () if (_items.Count == 0) kaste ny InvalidOperationException ("Køen er tom"); returnere _items.Tail.Value; | Oppførsel | Returnerer antall gjenstander som er i køen. Returnerer 0 hvis køen er tom. |
| Opptreden | O (1) |
offentlig int Count get return _items.Count;
En dobbel-endret kø, eller dekke, utvider køenes adferd ved å tillate at elementer legges til eller fjernes fra begge sider av køen. Denne nye virkemåten er nyttig i flere problemdomener, spesielt oppgave- og trådplanlegging. Det er også generelt nyttig for å implementere andre datastrukturer. Vi ser et eksempel på bruk av en deque for å implementere en annen datastruktur senere.
De Deque Klassen er støttet av en dobbeltkoblet liste. Dette tillater oss å legge til og fjerne elementer fra forsiden eller baksiden av listen og få tilgang til Først og Siste eiendommer. De viktigste endringene mellom køklassen og deque-klassen er at Enqueue, dequeue, og Peek metoder har blitt doblet inn i Først og Siste varianter.
offentlig klasse Deque LinkedList _items = new LinkedList (); offentlig tomrom EnqueueFirst (T-verdi) kaste ny NotImplementedException (); offentlig tomrom EnqueueLast (T-verdi) kaste ny NotImplementedException (); offentlig T DequeueFirst () kaste ny NotImplementedException (); offentlig T DequeueLast () kaste ny NotImplementedException (); offentlig T PeekFirst () kaste ny NotImplementedException (); offentlig T PeekLast () kaste ny NotImplementedException (); offentlig int count get;
| Oppførsel | Legger til den angitte verdien til køenes hode. Dette blir neste punkt dequeued av DequeueFirst. |
| Opptreden | O (1) |
offentlig tomrom EnqueueFirst (T-verdi) _items.AddFirst (verdi);
| Oppførsel | Legger til den angitte verdien til halen av køen. Dette blir neste punkt dequeued av DequeueLast. |
| Opptreden | O (1) |
offentlig tomrom EnqueueLast (T-verdi) _items.AddLast (verdi);
| Oppførsel | Fjerner og returnerer det første elementet i dekningen. En InvalidOperationException kastes hvis dekselet er tomt. |
| Opptreden | O (1) |
offentlig T DequeueFirst () if (_items.Count == 0) kaste ny InvalidOperationException ("DequeueFirst kalles når dekselet er tomt"); T temp = _items.Head.Value; _items.RemoveFirst (); retur temp; | Oppførsel | Fjerner og returnerer det siste elementet i dekningen. En InvalidOperationException kastes hvis dekselet er tomt. |
| Opptreden | O (1) |
offentlig T DequeueLast () if (_items.Count == 0) kaster ny InvalidOperationException ("DequeueLast kalles når dekselet er tomt"); T temp = _items.Tail.Value; _items.RemoveLast (); retur temp; | Oppførsel | Returnerer det første elementet i dekningen, men etterlater samlingen uendret. En InvalidOperationException kastes hvis dekselet er tomt. |
| Opptreden | O (1) |
offentlig T PeekFirst () if (_items.Count == 0) kaste ny InvalidOperationException ("PeekFirst kalles når dekselet er tomt"); returnere _items.Head.Value; | Oppførsel | Returnerer det siste elementet i dekningen, men etterlater samlingen uendret. En InvalidOperationException kastes hvis dekselet er tomt. |
| Opptreden | O (1) |
offentlig T PeekLast () if (_items.Count == 0) kaste ny InvalidOperationException ("PeekLast ringte når dekselet er tomt"); returnere _items.Tail.Value; | Oppførsel | Returnerer antall elementer som for øyeblikket befinner seg i dekningen, eller 0 hvis dekningen er tom. |
| Opptreden | O (1) |
offentlig int Count get return _items.Count;
Deques brukes ofte til å implementere andre datastrukturer.
Vi har sett en stabel implementert ved hjelp av en Linked, så nå la oss se på en implementert ved hjelp av en Deque.
Du lurer kanskje på hvorfor jeg ville velge å implementere en Stable bruker en Deque snarere enn a Linked. Årsaken er en av ytelse og kodegenbruk. En koblet liste har kostnaden for pernoder-overhead og redusert datalokalitet - elementene er allokert i bunken, og minnestederne kan ikke være nær hverandre, noe som forårsaker et større antall hurtigbuffer og sidefeil ved CPU og minnehardware nivåer. En bedre utførelse av en kø kan bruke en array som backing-butikken i stedet for en liste. Dette ville tillate mindre pernode overhead og kunne forbedre ytelsen ved å ta opp noen lokalitetsproblemer.
Implementere a Stable eller Kø som en matrise er imidlertid en mer komplisert implementering. Ved å implementere Deque på denne mer komplekse måten og bruke den som grunnlag for andre datastrukturer, kan vi innse ytelsesfordelene for alle strukturer mens bare å skrive koden en gang. Dette akselererer utviklingstiden og reduserer vedlikeholdskostnadene.
Vi vil se på et eksempel på a Deque som en matrise senere i denne delen, men først la oss se på et eksempel på a Stable implementert ved hjelp av en Deque.
offentlig klasse Stack Deque _items = new Deque (); offentlig tomrom Push (T-verdi) _items.EnqueueFirst (verdi); offentlig T Pop () return _items.DequeueFirst (); offentlig T Peek () return _items.PeekFirst (); offentlig inntekt get return _items.Count;
Legg merke til at all feilkontroll er nå utsatt til Deque og eventuelle optimalisering eller feilrettinger gjort på Deque vil automatisk søke på Stable klasse. Implementere a Kø er like enkelt og som sådan er igjen som en øvelse for leseren.
Som nevnt tidligere, er det fordeler å bruke en matrise i stedet for en koblet liste som backing-butikken for Deque (en dekke av heltall). Konseptuelt virker dette enkelt, men det er faktisk flere problemer som må tas opp for at dette skal fungere.
La oss se på noen av disse problemene grafisk og se hvordan vi kan håndtere dem. Underveis, vær oppmerksom på de vekstpolitiske problemene som diskuteres i ArrayList-seksjonen, og at de samme problemene gjelder her.
Når samlingen er opprettet, er den en 0-lengde rekkefølge. La oss se på hvordan noen handlinger påvirker den interne gruppen. Når vi går gjennom dette, merk at den grønne "h" og den røde "t" i figurene refererer til henholdsvis "hode" og "hale". Hodet og halen er arrayindeksene som angir de første og siste elementene i køen. Når vi legger til og fjerner elementer, blir samspillet mellom hode og hale tydeligere.
Deque deq = new Deque (); deq.EnqueueFirst (1);
Legge til en verdi på forsiden av dekselet deq.EnqueueLast (2);
Legge til en verdi til slutten av dekselet deq.EnqueueFirst (0);
Legge til en annen verdi på forsiden av dekselet; hodet indekser rundt Legg merke til hva som har skjedd på dette punktet. Hodetindeksen har viklet rundt til enden av arrayet. Nå er det første elementet i dekaken, hva ville bli returnert av DequeueFirst, er verdien på arrayindeks tre (null).
deq.EnqueueLast (3);
Legge til en verdi til slutten av dekselet På dette punktet er matrisen fylt. Når et annet element er lagt til, vil følgende oppstå:
EnqueueFirst - Elementet legges til ved indeks null (kopifunksjonen etterlater dette åpent).EnqueueLast - Elementet legges til slutten av arrayet. deq.EnqueueLast (4);
Legge til en verdi på slutten av den utvidede dekningen La oss nå se hva som skjer når ting blir fjernet fra Deque.
deq.DequeueFirst ();
Fjerner det første elementet fra den utvidede dekningen deq.DequeueLast ();
Fjerner det siste elementet fra den utvidede dekningen Det kritiske poenget å merke seg er at uansett kapasiteten til det interne arrayet, er det logiske innholdet i Deque elementene fra hovedsindeksen til haleindeksen, idet det tas hensyn til behovet for å vikle rundt i enden av arrayet. En matrise som gir atferden til å pakke rundt fra hodet til halen, kalles ofte som en sirkulær buffer.
Med denne forståelsen av hvordan array logikken fungerer, la oss dykke rett inn i koden.
De array-baserte Deque-metodene og egenskapene er de samme som listebaserte, så de vil ikke bli gjentatt her. Listen er imidlertid erstattet med en matrise, og det er nå tre egenskaper som inneholder størrelsen, hodet og halen.
offentlig klasse Deque T [] _items = new T [0]; // Antall gjenstander i køen. int _size = 0; // Indeksen for det første (eldste) elementet i køen. int _head = 0; // Indeksen for det siste (nyeste) elementet i køen. int _tail = -1; ...
Når den interne gruppen trenger å vokse, algoritmen for å øke størrelsen på arrayet, kopiere arrayinnholdet, og oppdatere de interne indeksverdiene må kjøre. De Enqueue Metoden utfører den operasjonen og kalles av begge EnqueueFirst og EnqueueLast. De startingIndex parameter brukes til å bestemme om du vil forlate array-sporet ved indeks null åpen (i tilfelle av EnqueueFirst).
Vær spesielt oppmerksom på hvordan dataene er utpakket i tilfeller der turen fra hod til hale krever at du går rundt enden av arrayet tilbake til null.
private void allocateNewArray (int startIndex) int newLength = (_size == 0)? 4: _size * 2; T [] newArray = ny T [newLength]; hvis (_size> 0) int targetIndex = startIndex; // Kopier innholdet ... // Hvis arrayet ikke har innpakning, kopier du bare gyldig rekkevidde. // Else, kopi fra hodet til enden av matrisen og deretter fra 0 til halen. // Hvis halen er mindre enn hodet, har vi pakket inn. hvis (_tail < _head) // Copy the _items[head]… _items[end] -> newArray [0] ... newArray [N]. for (int indeks = _head; indeks < _items.Length; index++) newArray[targetIndex] = _items[index]; targetIndex++; // Copy _items[0]… _items[tail] -> newArray [N + 1] ... for (int index = 0; index <= _tail; index++) newArray[targetIndex] = _items[index]; targetIndex++; else // Copy the _items[head]… _items[tail] -> newArray [0] ... newArray [N] for (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;
| Oppførsel | Legger til den angitte verdien til køenes hode. Dette blir neste punkt dequeued av DequeueFirst. |
| Opptreden | O (1) i de fleste tilfeller; O (n) når vekst er nødvendig. |
offentlig tomrom EnqueueFirst (T element) // Hvis arrayet må vokse. hvis (_items.Length == _size) allocateNewArray (1); // Siden vi vet at arrayet ikke er fullt og _head er større enn 0, // vi vet at sporet foran hodet er åpent. hvis (_head> 0) _head--; else // Ellers må vi vikle rundt til slutten av arrayet. _head = _items.Length - 1; _items [_head] = item; _size ++;
| Oppførsel | Legger til den angitte verdien til halen av køen. Dette blir neste punkt dequeued av DequeueLast. |
| Opptreden | O (1) i de fleste tilfeller; O (n) når vekst er nødvendig. |
offentlig tomrom EnqueueLast (T element) // Hvis arrayet må vokse. hvis (_items.Length == _size) allocateNewArray (0); // Nå har vi en riktig størrelse array og kan fokusere på innpakningsproblemer. // Hvis _tail er på slutten av gruppen må vi vikle rundt. hvis (_tail == _items.Length - 1) _tail = 0; ellers _tail ++; _items [_tail] = element; _size ++;
| Oppførsel | Fjerner og returnerer det første elementet i dekningen. En InvalidOperationException kastes hvis dekselet er tomt. |
| Opptreden | O (1) |
offentlig T DequeueFirst () if (_size == 0) kaste ny InvalidOperationException ("The deque er tom"); T verdi = _items [_head]; hvis (_head == _items.Length - 1) // Hvis hodet er på siste indeks i arrayet, pakk det rundt. _head = 0; ellers // Flytt til neste spor. _head ++; _size--; returverdi; | Oppførsel | Fjerner og returnerer det siste elementet i dekningen. En InvalidOperationException kastes hvis dekselet er tomt. |
| Opptreden | O (1) |
offentlig T DequeueLast () if (_size == 0) kaste ny InvalidOperationException ("Dekselet er tomt"); T verdi = _items [_tail]; hvis (_tail == 0) // Hvis halen er på den første indeksen i arrayet, pakk den rundt. _tail = _items.Length - 1; ellers // Flytt til forrige spor. _hale--; _size--; returverdi; | Oppførsel | Returnerer det første elementet i dekningen, men etterlater samlingen uendret. en InvalidOperationException kastes hvis dekselet er tomt. |
| Opptreden | O (1) |
offentlig T PeekFirst () if (_size == 0) kaste ny InvalidOperationException ("The deque er tom"); returner _items [_head]; | Oppførsel | Returnerer det siste elementet i dekningen, men etterlater samlingen uendret. en InvalidOperationException kastes hvis dekselet er tomt. |
| Opptreden | O (1) |
offentlig T PeekLast () hvis (_size == 0) kaste ny InvalidOperationException ("Dekken er tom"); returnere _items [_tail]; | Oppførsel | Returnerer antall gjenstander som for øyeblikket befinner seg i dekningen, eller 0 hvis dekningen er tom. |
| Opptreden | O (1) |
offentlig intall Count get return _size;
