Share
Hittills har vi tittat på samlingar som ger mycket grundläggande datalagring, i huvudsak abstraktioner över en array. I det här avsnittet ska vi titta på vad som händer när vi lägger till några väldigt grundläggande beteenden som helt ändrar användningsområdena för samlingarna.
En stapel är en samling som returnerar objekt till den som ringer i ett LIFO-mönster (Last In In First Out). Vad det här betyder är att det sista objektet till samlingen blir det första objektet som returneras.
Staplar skiljer sig från list- och array-liknande samlingar. De kan inte indexeras direkt, objekt läggs till och tas bort med olika metoder, och deras innehåll är mer ogenomskinligt än listor och arrays. Vad jag menar med detta är att medan en listbaserad samling innehåller en Innehåll-metod, gör en stack inte. Dessutom är en stapel inte uppräknad. För att förstå varför det här är, låt oss titta på vad en stack är och hur användningen av en stack driver dessa skillnader.
En av de vanligaste analogierna för en stack är restaurangplattformen. Detta är en enkel fjäderbelastad enhet på vilken rena plattor staplas. Fjädern säkerställer att oavsett hur många tallrikar som finns i stapeln, kan topplattan lätt nås. Rena plattor läggs till toppen av stapeln och när en kund tar bort en skylt tar han bort den högsta plattan (den senast lagda plattan).
Vi börjar med en tom plåtställ.
En tom platta stack (fjädern håller inga plattor) Och sedan lägger vi till en röd, en blå och en grön tallrik till hyllan i den ordningen.
Nyckeln till att förstå här är att när nya plattor läggs till läggs de till toppen av stapeln. Om en kund hämtar en platta kommer han eller hon att få den senast lagda plattan (den gröna plattan). Nästa kund skulle få den blå plattan, och till sist skulle den röda plattan avlägsnas.
Nu när vi förstår hur en stack fungerar, låt oss definiera några nya villkor. När ett objekt läggs till i stapeln, är det "tryckt" på att använda Tryck metod. När ett objekt tas bort från stapeln, "poppas" av det med Pop metod. Det översta objektet i stapeln, senast tillagd, kan "tittas" vid användning av Titt metod. Peeking tillåter dig att se objektet utan att ta bort det från stapeln (precis som kunden på tallerkenet skulle kunna se färgen på topplattan). Med dessa villkor i åtanke, låt oss titta på implementeringen av a Stack klass.
De Stack klass definierar Tryck, Pop, och Titt metoder, a Räkna egendom, och använder Länkad lista klass för att lagra värdena i stapeln.
public class Stack LinkedList _items = new LinkedList (); public void Push (T-värde) kasta ny NotImplementedException (); public T Pop () kasta ny NotImplementedException (); public T Peek () kasta ny NotImplementedException (); public int count get;
| Beteende | Lägger till ett objekt överst i stapeln. |
| Prestanda | O (1) |
Eftersom vi använder en länkad lista som vår backing-butik är allt vi behöver göra att lägga till det nya objektet i slutet av listan.
public void Push (T-värde) _items.AddLast (värde);
| Beteende | Tar bort och returnerar det sista objektet till stapeln. Om stacken är tom, an InvalidOperationException kastas. |
| Prestanda | O (1) |
Tryck lägger till objekt på baksidan av listan, så vi kommer "pop" dem från baksidan. Om listan är tom kastas ett undantag.
Accentsconagua
public T Pop () if (_items.Count == 0) släng nytt InvalidOperationException ("Stacken är tom"); T result = _items.Tail.Value; _items.RemoveLast (); returresultat; | Beteende | Returnerar det sista objektet till stapeln men lämnar objektet på stapeln. Om stacken är tom, an InvalidOperationException kastas. |
| Prestanda | O (1) |
public T Peek () if (_items.Count == 0) släng nytt InvalidOperationException ("stacken är tom"); returnera _items.Tail.Value; | Beteende | Returnerar antalet poster i stapeln. |
| Prestanda | O (1) |
Eftersom stacken är tänkt att vara en opak data struktur, varför har vi en Räkna fast egendom? Att veta om en stack är tom (Räkna == 0) är mycket användbar, särskilt sedan Pop kastar ett undantag när stacken är tom.
public int Count get return _items.Count;
Det klassiska stackexemplet är RPN-räknaren (Reverse Polish Notation).
RPN-syntaxen är ganska enkel. Det använder:
snarare än den traditionella:
Med andra ord, istället för att säga "4 + 2", skulle vi säga "4 2 +." Om du vill förstå den historiska betydelsen av RPN-syntaxen uppmuntrar jag dig att gå till Wikipedia eller din favorit sökmotor.
Det sätt på vilket RPN utvärderas och orsaken till att en stapel är så användbar när man implementerar en RPN-kalkylator kan ses i följande algoritm:
för varje ingångsvärde om värdet är ett heltal tryck på värdet på operandstacken annars om värdet är en operatörspop, vänster och högervärdena från stacken utvärderar operatören tryck på resultatet till stackpop svaret från stapeln.
Så given ingångssnitten "4 2 +" skulle operationerna vara:
tryck (4) tryck (2) tryck (pop () + pop ())
Stacken innehåller nu ett enda värde: sex (svaret).
Följande är ett komplett genomförande av en enkel kalkylator som läser en ekvation (till exempel "4 2 +") från konsolinmatningen, splittrar inmatningen vid varje utrymme (["4", "2" och "+"]) , och utför RPN-algoritmen på ingången. Slingan fortsätter tills ingången är ordet "avsluta".
void RpnLoop () while (true) Console.Write (">"); stränginmatning = Console.ReadLine (); om (input.Trim (). ToLower () == "avsluta") break; // Stacken av heltal som ännu inte aktiverats. Stack values = new Stack (); foreach (strängtoken i input.Split (nytt char [] ")) // Om värdet är ett heltal ... int värde, om (int.TryParse (token, out value)) stacken .värden.Push (värde); else // Annars utvärdera uttrycket ... int rhs = values.Pop (); int lhs = values.Pop (); // ... och pop resultatet till stacken. 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; default: kasta nytt ArgumentException (string.Format ("Okänd token: 0 ", token)); // Det sista objektet på stapeln är resultatet. Console.WriteLine (values.Pop ()); Köerna är väldigt lik stackar. De ger en ogenomskinlig samling, från vilken objekt kan läggas till (enkodas) eller tas bort (avkodas) på ett sätt som ger värde över en listbaserad samling.
Köer är en först-in-först-ut (FIFO) samling. Det innebär att objekt tas bort från kön i samma ordning som de lagts till. Du kan tänka på en kö som en linje i en butikskassa, mot-folk skriver in linjen och servas i den ordning de anländer.
Köer används vanligtvis i applikationer för att tillhandahålla en buffert för att lägga till objekt för framtida bearbetning eller för att ge ordnad tillgång till en delad resurs. Om en databas exempelvis kan hantera endast en anslutning, kan en kö användas för att tillåta trådar att vänta på sin tur (i ordning) för att komma åt databasen.
De Kö, som Stack, backas av a Länkad lista. Dessutom ger det metoderna enqueue (för att lägga till objekt), dequeue (för att ta bort objekt), Titt, och Räkna. Tycka om Stack, Det kommer inte att behandlas som en samling med allmänt syfte, vilket betyder att den inte kommer att genomföras iCollection.
offentlig klass Queue LinkedList _items = new LinkedList (); public void Enqueue (T-värde) kasta ny NotImplementedException (); public T Dequeue () kasta ny NotImplementedException (); public T Peek () kasta ny NotImplementedException (); public int count get;
| Beteende | Lägger till ett objekt i slutet av kön. |
| Prestanda | O (1) |
Denna implementering lägger till objektet till början av den länkade listan. Objektet kan lika enkelt läggas till i slutet av listan. Allt som verkligen betyder är att artiklarna är enqueued till ena änden av listan och dequeued från den andra (FIFO). Observera att detta är motsatt av klassklassen där artiklar läggs till och tas bort från samma ända (LIFO).
Offentligt tomrum Enqueue (T-värde) _items.AddFirst (värde);
| Beteende | Tar bort och returnerar det äldsta objektet från köen. En InvalidOperationException kastas om köen är tom. |
| Prestanda | O (1) |
Eftersom enqueue lagt till objektet till början av listan, dequeue måste ta bort objektet i slutet av listan. Om köen inte innehåller några objekt kastas ett undantag.
public T Dequeue () if (_items.Count == 0) släng nytt InvalidOperationException ("Kön är tom"); T sist = _items.Tail.Value; _items.RemoveLast (); återvända sist; | Beteende | Returnerar nästa objekt som skulle returneras om Dequeue kallades. Kön lämnas oförändrad. En InvalidOperationException kastas om köen är tom. |
| Prestanda | O (1) |
public T Peek () if (_items.Count == 0) släng nytt InvalidOperationException ("Kön är tom"); returnera _items.Tail.Value; | Beteende | Returnerar antalet objekt som finns i köen. Returnerar 0 om köen är tom. |
| Prestanda | O (1) |
public int Count get return _items.Count;
En dubbelsidig kö, eller deck, utökar köbeteendet genom att låta objekt läggas till eller tas bort från båda sidor av köen. Detta nya beteende är användbart i flera problemområden, specifikt uppgift och trådschemaläggning. Det är också allmänt användbart för att implementera andra datastrukturer. Vi får se ett exempel på att använda en däck för att implementera en annan datastruktur senare.
De Deque klassen stöds av en dubbelt länkad lista. Detta gör det möjligt för oss att lägga till och ta bort objekt från framsidan eller baksidan av listan och få åtkomst till Först och Sista egenskaper. De viktigaste förändringarna mellan köklassen och deckklassen är att enqueue, dequeue, och Titt metoder har fördubblats in i Först och Sista varianter.
public class Deque LinkedList _items = new LinkedList (); public void EnqueueFirst (T-värde) kasta ny NotImplementedException (); Offentligt ogiltigt EnqueueLast (T-värde) släng nytt NotImplementedException (); public T DequeueFirst () släng ny NotImplementedException (); offentliga T DequeueLast () släng nya NotImplementedException (); public T PeekFirst () släng ny NotImplementedException (); public T PeekLast () släng ny NotImplementedException (); public int count get;
| Beteende | Lägger till det angivna värdet i köens huvud. Detta kommer att bli nästa punkt avkrävs av DequeueFirst. |
| Prestanda | O (1) |
public void EnqueueFirst (T-värde) _items.AddFirst (värde);
| Beteende | Lägger till det angivna värdet i köens svans. Detta kommer att bli nästa punkt avkrävs av DequeueLast. |
| Prestanda | O (1) |
public void EnqueueLast (T-värde) _items.AddLast (värde);
| Beteende | Tar bort och returnerar det första objektet i deckningen. En InvalidOperationException kastas om decket är tomt. |
| Prestanda | O (1) |
public T DequeueFirst () if (_items.Count == 0) släng nytt InvalidOperationException ("DequeueFirst kallas när decket är tomt"); T temp = _items.Head.Value; _items.RemoveFirst (); returtemperatur | Beteende | Tar bort och returnerar det sista föremålet i dekretet. En InvalidOperationException kastas om decket är tomt. |
| Prestanda | O (1) |
public T DequeueLast () if (_items.Count == 0) slänga nytt InvalidOperationException ("DequeueLast kallas när decket är tomt"); T temp = _items.Tail.Value; _items.RemoveLast (); returtemperatur | Beteende | Returnerar det första föremålet i dekalet men lämnar samlingen oförändrad. En InvalidOperationException kastas om decket är tomt. |
| Prestanda | O (1) |
public T PeekFirst () if (_items.Count == 0) släng nytt InvalidOperationException ("PeekFirst kallas när dekakten är tom"); returnera _items.Head.Value; | Beteende | Returnerar sista föremålet i dekalet men lämnar samlingen oförändrad. En InvalidOperationException kastas om decket är tomt. |
| Prestanda | O (1) |
public T PeekLast () if (_items.Count == 0) slänga nytt InvalidOperationException ("PeekLast kallas när dekakten är tom"); returnera _items.Tail.Value; | Beteende | Returnerar antalet objekt som för närvarande finns i dekretet, eller 0 om decket är tomt. |
| Prestanda | O (1) |
public int Count get return _items.Count;
Deques används ofta för att genomföra andra datastrukturer.
Vi har sett en stack implementerad med en Länkad lista, så nu ska vi titta på en som implementeras med hjälp av en Deque.
Du kanske undrar varför jag skulle välja att implementera en Stack använder en Deque snarare än a Länkad lista. Anledningen är en av prestanda och kodåteranvändning. En länkad lista har kostnaden för per-nod-överhuvud och minskad datalägenhet-objekten tilldelas i högen och minnesplatserna kan inte vara nära varandra, vilket orsakar ett större antal cachemissningar och sidfel på CPU och minnes hårdvara nivåer. En bättre utförande av en kö kan använda en array som backing-butiken istället för en lista. Detta skulle möjliggöra mindre per-nod överhead och kan förbättra prestanda genom att ta itu med några lokala problem.
Genomföra a Stack eller Kö som en matris är dock en mer komplex implementering. Genom att genomföra Deque på detta mer komplicerade sätt och använder det som grund för andra datastrukturer kan vi inse prestandafördelarna för alla strukturer, samtidigt som det bara behöver skrivas koden en gång. Detta accelererar utvecklingstiden och minskar underhållskostnaderna.
Vi kommer att titta på ett exempel på a Deque som en array senare i det här avsnittet, men först låt oss titta på ett exempel på a Stack implementeras med hjälp av a Deque.
offentlig klass Stack Deque _items = new Deque (); public void Push (T-värde) _items.EnqueueFirst (värde); public T Pop () return _items.DequeueFirst (); public T Peek () return _items.PeekFirst (); public int Count get return _items.Count;
Observera att all felkontroll är nu uppskjuten till Deque och eventuell optimering eller buggfixering till Deque kommer automatiskt att gälla för Stack klass. Genomföra a Kö är lika lätt och som sådan lämnas som en övning för läsaren.
Som tidigare nämnts finns det fördelar med att använda en array i stället för en länkad lista som backingstore för Deque (en helhet av heltal). Konceptuellt verkar det enkelt, men det finns faktiskt flera problem som måste åtgärdas för att detta ska fungera.
Låt oss titta på några av dessa problem grafiskt och se hur vi kan hantera dem. Längs vägen, kom ihåg de tillväxtpolitiska frågorna som diskuteras i avsnittet ArrayList och att samma problem gäller här.
När samlingen är skapad är den en 0-längd array. Låt oss titta på hur vissa åtgärder påverkar den interna gruppen. När vi går igenom detta märker vi att den gröna "h" och den röda "t" i figurerna hänvisar till "huvud" respektive "svans". Huvud och svans är de arrayindex som anger de första och sista föremålen i kön. När vi lägger till och tar bort objekt blir samspelet mellan huvud och svans tydligare.
Deque deq = New Deque (); deq.EnqueueFirst (1);
Lägger till ett värde på framsidan av deckningen deq.EnqueueLast (2);
Lägger till ett värde i slutet av dekalet deq.EnqueueFirst (0);
Lägger till ett annat värde på framsidan av dequeen; huvudindex wraps runt Lägg märke till vad som hänt på denna punkt. Huvudindexet har lindats runt i slutet av matrisen. Nu är det första föremålet i dekaken, vad skulle returneras av DequeueFirst, är värdet vid matrisindex tre (noll).
deq.EnqueueLast (3);
Lägger till ett värde i slutet av dekalet Vid denna tidpunkt är matrisen fylld. När ett annat objekt läggs till kommer följande att inträffa:
EnqueueFirst - Föremålet läggs till i index noll (kopieringsoperationen lämnar denna öppen).EnqueueLast - Objektet läggs till i slutet av arrayen. deq.EnqueueLast (4);
Lägger till ett värde i slutet av det expanderade dekretet Låt oss nu se vad som händer när objekt tas bort från Deque.
deq.DequeueFirst ();
Ta bort det första objektet från det expanderade dekretet deq.DequeueLast ();
Ta bort sista objektet från den expanderade dekretet Den kritiska punkten att notera är att oavsett kapaciteten hos den interna matrisen är deckens logiska innehåll föremålen från huvudindex till svansindex, med hänsyn tagen till behovet att vikla runt i slutet av matrisen. En matris som ger beteendet att sätta in runt från huvudet till svansen är ofta känt som en cirkulär buffert.
Med denna förståelse av hur matrislogiken fungerar, låt oss dyka rätt in i koden.
De arraybaserade Deque-metoderna och egenskaperna är desamma som listbaserade, så de kommer inte att upprepas här. Listan har dock ersatts med en array och det finns nu tre egenskaper som innehåller storlek, huvud och svansinformation.
public class Deque T [] _items = new T [0]; // Antalet objekt i kön. int _size = 0; // Indexet för det första (äldsta) objektet i kön. int _head = 0; // Indexet för det senaste (nyaste) objektet i kön. int _tail = -1; ...
När den interna gruppen behöver växa, algoritmen för att öka storleken på arrayen, kopiera arrayinnehållet och uppdatera de interna indexvärdena måste köras. De enqueue Metoden utför den operationen och kallas av båda EnqueueFirst och EnqueueLast. De startingIndex Parametern används för att bestämma om du vill lämna matrisluckan vid index noll öppen (i fallet med EnqueueFirst).
Var särskilt uppmärksam på hur dataen är oöppnade i fall där gången från huvud till svans kräver att man går runt om slutet av arrayen tillbaka till noll.
private void allocateNewArray (int startIndex) int newLength = (_size == 0)? 4: _size * 2; T [] newArray = ny T [newLength]; om (_size> 0) int targetIndex = startIndex; // Kopiera innehållet ... // Om arrayen inte har någon omslag, kopiera bara det giltiga intervallet. // Annars, kopiera från huvud till slutet av matrisen och sedan från 0 till svansen. // Om svansen är mindre än huvudet har vi blivit inslagna. om (_tail < _head) // Copy the _items[head]… _items[end] -> newArray [0] ... newArray [N]. för (int index = _head; index < _items.Length; index++) newArray[targetIndex] = _items[index]; targetIndex++; // Copy _items[0]… _items[tail] -> newArray [N + 1] ... för (int index = 0; index <= _tail; index++) newArray[targetIndex] = _items[index]; targetIndex++; else // Copy the _items[head]… _items[tail] -> newArray [0] ... newArray [N] för (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;
| Beteende | Lägger till det angivna värdet i köens huvud. Detta kommer att bli nästa punkt avkrävs av DequeueFirst. |
| Prestanda | O (1) i de flesta fall; O (n) när tillväxt är nödvändig. |
public void EnqueueFirst (T item) // Om matrisen behöver växa. om (_items.Length == _size) allocateNewArray (1); // Eftersom vi vet att matrisen inte är full och _head är större än 0, // vi vet att spåret framför huvudet är öppet. om (_head> 0) _head--; else // Annars måste vi vikla runt till slutet av arrayen. _head = _items.Length - 1; _items [_head] = item; _size ++;
| Beteende | Lägger till det angivna värdet i köens svans. Detta kommer att bli nästa punkt avkrävs av DequeueLast. |
| Prestanda | O (1) i de flesta fall; O (n) när tillväxt är nödvändig. |
public void EnqueueLast (T item) // Om matrisen behöver växa. om (_items.Length == _size) allocateNewArray (0); // Nu har vi en ordentlig storlek och kan fokusera på omslagsproblem. // Om _tail är i slutet av arrayen måste vi vikla runt. om (_tail == _items.Length - 1) _tail = 0; annars _tail ++; _items [_tail] = item; _size ++;
| Beteende | Tar bort och returnerar det första objektet i deckningen. En InvalidOperationException kastas om decket är tomt. |
| Prestanda | O (1) |
public T DequeueFirst () if (_size == 0) släng nytt InvalidOperationException ("Deque är tomt"); T-värde = _items [_head]; om (_head == _items.Length - 1) // Om huvudet ligger vid det sista indexet i arrayen, vänd det runt. _head = 0; else // Flytta till nästa spår. _head ++; _size--; returvärde; | Beteende | Tar bort och returnerar det sista föremålet i dekretet. En InvalidOperationException kastas om decket är tomt. |
| Prestanda | O (1) |
public T DequeueLast () if (_size == 0) släng nytt InvalidOperationException ("Deck är tomt"); T-värde = _items [_tail]; om (_tail == 0) // Om svansen är vid det första indexet i matrisen, linda den om. _tail = _items.Length - 1; else // Flytta till föregående kortplats. _svans--; _size--; returvärde; | Beteende | Returnerar det första föremålet i dekalet men lämnar samlingen oförändrad. En InvalidOperationException kastas om decket är tomt. |
| Prestanda | O (1) |
public T PeekFirst () if (_size == 0) släng nytt InvalidOperationException ("Deque är tomt"); returnera _items [_head]; | Beteende | Returnerar sista föremålet i dekalet men lämnar samlingen oförändrad. En InvalidOperationException kastas om decket är tomt. |
| Prestanda | O (1) |
public T PeekLast () if (_size == 0) släng nytt InvalidOperationException ("Decket är tomt"); returnera _items [_tail]; | Beteende | Returnerar antalet objekt som för närvarande finns i deketet eller 0 om decket är tomt. |
| Prestanda | O (1) |
public int Count get return _size;
