Share
Bisher haben wir uns Sammlungen angesehen, die einen sehr einfachen Datenspeicher bieten, im Wesentlichen Abstraktionen über ein Array. In diesem Abschnitt werden wir uns ansehen, was passiert, wenn wir einige grundlegende Verhaltensweisen hinzufügen, die den Nutzen der Sammlungen völlig verändern.
Ein Stack ist eine Sammlung, die Objekte in einem Last-In-First-Out (LIFO) -Muster an den Aufrufer zurückgibt. Dies bedeutet, dass das zuletzt zur Sammlung hinzugefügte Objekt das erste zurückgegebene Objekt ist.
Stapel unterscheiden sich von Listen- und Array-ähnlichen Sammlungen. Sie können nicht direkt indiziert werden, Objekte werden mit unterschiedlichen Methoden hinzugefügt und entfernt, und ihr Inhalt ist undurchsichtiger als Listen und Arrays. Damit meine ich, dass eine auf Listen basierende Auflistung eine Contains-Methode enthält, ein Stack jedoch nicht. Darüber hinaus ist ein Stapel nicht aufgezählt. Um zu verstehen, warum das so ist, schauen wir uns an, was ein Stack ist und wie die Verwendung eines Stacks diese Unterschiede verursacht.
Eine der häufigsten Analogien für einen Stapel ist der Restaurantplattenstapel. Dies ist ein einfaches federbelastetes Gerät, auf das saubere Platten gestapelt werden. Die Feder stellt sicher, dass unabhängig von der Anzahl der Platten im Stapel die obere Platte leicht zugänglich ist. Saubere Platten werden am oberen Rand des Stapels hinzugefügt. Wenn ein Kunde eine Platte entfernt, entfernt er die oberste Platte (die zuletzt hinzugefügte Platte)..
Wir beginnen mit einem leeren Tellergestell.
Ein leerer Plattenstapel (die Feder hält keine Platten) Dann fügen wir dem Rack in dieser Reihenfolge eine rote, eine blaue und eine grüne Platte hinzu.
Der Schlüssel zum Verständnis hier ist, dass beim Hinzufügen neuer Platten diese am oberen Rand des Stapels hinzugefügt werden. Wenn ein Kunde eine Platte abruft, erhält er die zuletzt hinzugefügte Platte (die grüne Platte). Der nächste Kunde würde die blaue Platte bekommen, und schließlich wurde die rote Platte entfernt.
Nun, da wir wissen, wie ein Stapel funktioniert, definieren wir einige neue Begriffe. Wenn ein Artikel zum Stapel hinzugefügt wird, wird er mit der Taste "gedrückt" drücken Methode. Wenn ein Gegenstand aus dem Stapel genommen wird, wird er mit der Taste "abgelegt" Pop Methode. Das oberste Element des Stapels, das zuletzt hinzugefügt wurde, kann bei Verwendung von "gespürt" werden Spähen Methode. Mit Peeking können Sie den Artikel anzeigen, ohne ihn aus dem Stapel zu entfernen (genau wie der Kunde am Plattenregal die Farbe der oberen Platte erkennen kann). Lassen Sie uns mit diesen Begriffen die Implementierung von a betrachten Stapel Klasse.
Das Stapel Klasse definiert drücken, Pop, und Spähen Methoden, a Anzahl Eigenschaft und verwendet die LinkedList Klasse, um die im Stapel enthaltenen Werte zu speichern.
öffentliche Klasse Stack LinkedList _items = new LinkedList (); public void Push (T-Wert) neue NotImplementedException () werfen; public T Pop () throw new NotImplementedException (); public T Peek () throw new NotImplementedException (); public int Count get;
| Verhalten | Fügt ein Element am oberen Rand des Stapels hinzu. |
| Performance | O (1) |
Da wir eine verknüpfte Liste als Hintergrundspeicher verwenden, müssen wir den neuen Artikel nur am Ende der Liste hinzufügen.
public void Push (T-Wert) _items.AddLast (value);
| Verhalten | Entfernt den letzten zum Stapel hinzugefügten Artikel und gibt ihn zurück. Wenn der Stapel leer ist, eine InvalidOperationException ist geworfen. |
| Performance | O (1) |
drücken fügt Elemente an der Rückseite der Liste hinzu, so dass wir sie von hinten "platzieren". Wenn die Liste leer ist, wird eine Ausnahme ausgelöst.
Accentsconagua
public T Pop () if (_items.Count == 0) Neue InvalidOperationException werfen ("Der Stapel ist leer"); T result = _items.Tail.Value; _items.RemoveLast (); Ergebnis zurückgeben; | Verhalten | Gibt den letzten zum Stapel hinzugefügten Artikel zurück, belässt ihn jedoch auf dem Stapel. Wenn der Stapel leer ist, eine InvalidOperationException ist geworfen. |
| Performance | O (1) |
public T Peek () if (_items.Count == 0) Neue InvalidOperationException werfen ("Der Stapel ist leer"); return _items.Tail.Value; | Verhalten | Gibt die Anzahl der Elemente im Stapel zurück. |
| Performance | O (1) |
Da der Stack eine undurchsichtige Datenstruktur sein soll, warum haben wir eine Anzahl Eigentum? Wissen, ob ein Stapel leer ist (Zählen == 0) ist sehr nützlich, vor allem da Pop löst eine Ausnahme aus, wenn der Stapel leer ist.
public int Count get return _items.Count;
Das klassische Beispiel für den Stack ist der Reverse Polish Notation (RPN) -Berechner.
Die RPN-Syntax ist ziemlich einfach. Es verwendet:
anstatt der traditionellen:
Mit anderen Worten, anstatt "4 + 2" zu sagen, würden wir "4 2 +" sagen. Wenn Sie die historische Bedeutung der RPN-Syntax verstehen möchten, sollten Sie die Wikipedia oder Ihre bevorzugte Suchmaschine besuchen.
Die Art und Weise, wie RPN ausgewertet wird, und der Grund, aus dem ein Stack beim Implementieren eines RPN-Rechners so nützlich ist, können Sie dem folgenden Algorithmus entnehmen:
Für jeden Eingabewert, wenn der Wert eine Ganzzahl ist, den Wert auf den Operandenstapel schieben. Andernfalls, wenn der Wert ein Operator ist, den linken und den rechten Wert aus dem Stapel auswerten.
Bei Eingabe der Zeichenfolge "4 2 +" lauten die Operationen:
drücke (4) drücke (2) drücke (pop () + pop ())
Nun enthält der Stack einen einzigen Wert: six (die Antwort).
Das Folgende ist eine vollständige Implementierung eines einfachen Rechners, der eine Gleichung (z. B. „4 2 +“) von der Konsoleneingabe liest und die Eingabe an jedem Leerzeichen aufteilt ([“4”, “2” und “+”]). , und führt den RPN-Algorithmus für die Eingabe aus. Die Schleife wird fortgesetzt, bis die Eingabe das Wort "quit" ist..
void RpnLoop () while (true) Console.Write (">"); Zeichenfolge input = Console.ReadLine (); if (input.Trim (). ToLower () == "quit") break; // Der Stapel von Ganzzahlen, der noch nicht bearbeitet wurde. Stack-Werte = neuer Stack (); foreach (Zeichenfolgen-Token in input.Split (new char [] ")) // Wenn der Wert eine Ganzzahl ist… int-Wert; if (int.TryParse (token, out-Wert)) //… schieben Sie ihn nach Der Stack.Werte.Push (Wert); else // Andernfalls werten Sie den Ausdruck… int rhs = values.Pop (); int lhs = values.Pop (); //… aus und geben Sie das Ergebnis in den Stack zurück. 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: Neue ArgumentException (string.Format ("Unbekanntes Token: 0 ", token)); // Das letzte Element im Stack ist das Ergebnis. Console.WriteLine (values.Pop ()); Warteschlangen sind Stacks sehr ähnlich - sie bieten eine undurchsichtige Sammlung, aus der Objekte hinzugefügt (in die Warteschlange gestellt) oder entfernt (aus der Warteschlange entfernt) werden können, sodass der Wert einer listbasierten Sammlung erhöht wird.
Warteschlangen sind eine FIFO-Sammlung (First-In-First-Out). Dies bedeutet, dass Elemente in der Reihenfolge, in der sie hinzugefügt wurden, aus der Warteschlange entfernt werden. Sie können sich eine Warteschlange wie eine Linie an einer Kasse vorstellen, in der die Mitarbeiter in die Warteschlange eingehen und in der Reihenfolge ihres Eintreffens bedient werden.
Warteschlangen werden häufig in Anwendungen verwendet, um einen Puffer bereitzustellen, um Elemente für die zukünftige Verarbeitung hinzuzufügen oder um ordnungsgemäß auf eine gemeinsam genutzte Ressource zuzugreifen. Wenn eine Datenbank beispielsweise nur eine Verbindung verarbeiten kann, kann eine Warteschlange verwendet werden, damit Threads warten können, bis sie an der Reihe sind, um auf die Datenbank zuzugreifen.
Das Warteschlange, wie Stapel, wird von einem hinterlegt LinkedList. Außerdem werden die Methoden bereitgestellt Enqueue (um Artikel hinzuzufügen), Dequeue (um Artikel zu entfernen), Spähen, und Anzahl. Mögen Stapel, Es wird nicht als allgemeine Sammlung behandelt, dh es wird nicht implementiert ICollection.
öffentliche Klasse Queue LinkedList _items = new LinkedList (); public void Enqueue (T-Wert) throw new NotImplementedException (); public T Dequeue () throw new NotImplementedException (); public T Peek () throw new NotImplementedException (); public int Count get;
| Verhalten | Fügt ein Element am Ende der Warteschlange hinzu. |
| Performance | O (1) |
Diese Implementierung fügt das Element am Anfang der verknüpften Liste hinzu. Das Element kann genauso einfach am Ende der Liste hinzugefügt werden. Alles, was wirklich wichtig ist, ist, dass Elemente an einem Ende der Liste in eine Warteschlange gestellt und vom anderen entfernt werden (FIFO). Beachten Sie, dass dies das Gegenteil der Stack-Klasse ist, bei der Elemente am selben Ende hinzugefügt und entfernt werden (LIFO)..
Public void Enqueue (T-Wert) _items.AddFirst (value);
| Verhalten | Entfernt das älteste Element aus der Warteschlange und gibt es zurück. Ein InvalidOperationException wird ausgelöst, wenn die Warteschlange leer ist. |
| Performance | O (1) |
Schon seit Enqueue fügte das Element am Anfang der Liste hinzu, Dequeue muss das Element am Ende der Liste entfernen. Wenn die Warteschlange keine Elemente enthält, wird eine Ausnahme ausgelöst.
public T Dequeue () if (_items.Count == 0) Neue InvalidOperationException werfen ("Die Warteschlange ist leer"); T last = _items.Tail.Value; _items.RemoveLast (); zuletzt zurückkehren; | Verhalten | Gibt das nächste Element zurück, das zurückgegeben werden würde, wenn Dequeue aufgerufen wurde. Die Warteschlange bleibt unverändert. Eine InvalidOperationException wird ausgelöst, wenn die Warteschlange leer ist. |
| Performance | O (1) |
public T Peek () if (_items.Count == 0) Neue InvalidOperationException werfen ("Die Warteschlange ist leer"); return _items.Tail.Value; | Verhalten | Gibt die Anzahl der Elemente zurück, die sich aktuell in der Warteschlange befinden. Gibt 0 zurück, wenn die Warteschlange leer ist. |
| Performance | O (1) |
public int Count get return _items.Count;
Eine doppelseitige Warteschlange (deque) erweitert das Verhalten der Warteschlange, indem Elemente auf beiden Seiten der Warteschlange hinzugefügt oder entfernt werden können. Dieses neue Verhalten ist in mehreren Problembereichen hilfreich, insbesondere bei der Task- und Thread-Planung. Sie ist im Allgemeinen auch für die Implementierung anderer Datenstrukturen hilfreich. Wir werden ein Beispiel sehen, wie ein Deque später zum Implementieren einer anderen Datenstruktur verwendet wird.
Das Deque Klasse wird durch eine doppelt verknüpfte Liste unterstützt. Dies ermöglicht uns, Elemente von der Vorder - oder Rückseite der Liste hinzuzufügen und zu entfernen und auf die Zuerst und Zuletzt Eigenschaften. Die wichtigsten Änderungen zwischen der Queue-Klasse und der Deque-Klasse sind die der Enqueue, Dequeue, und Spähen Methoden wurden verdoppelt Zuerst und Zuletzt Varianten.
öffentliche Klasse Deque LinkedList _items = new LinkedList (); public void EnqueueFirst (T-Wert) throw new NotImplementedException (); public void EnqueueLast (T-Wert) throw new NotImplementedException (); public T DequeueFirst () throw new NotImplementedException (); public T DequeueLast () throw new NotImplementedException (); public T PeekFirst () throw new NotImplementedException (); public T PeekLast () throw new NotImplementedException (); public int Count get;
| Verhalten | Fügt den angegebenen Wert dem Kopf der Warteschlange hinzu. Dies ist der nächste von DequeueFirst in der Warteschlange stehende Artikel. |
| Performance | O (1) |
public void EnqueueFirst (T-Wert) _items.AddFirst (value);
| Verhalten | Fügt den angegebenen Wert zum Ende der Warteschlange hinzu. Dies ist der nächste von DequeueLast in der Warteschlange stehende Artikel. |
| Performance | O (1) |
public void EnqueueLast (T-Wert) _items.AddLast (value);
| Verhalten | Entfernt den ersten Artikel im Deque und gibt ihn zurück. Eine InvalidOperationException wird ausgelöst, wenn das Deque leer ist. |
| Performance | O (1) |
public T DequeueFirst () if (_items.Count == 0) Neue InvalidOperationException werfen ("DequeueFirst aufgerufen, wenn deque leer ist"); T temp = _items.Head.Value; _items.RemoveFirst (); Rücklauftemp; | Verhalten | Entfernt den letzten Eintrag im Deque und gibt ihn zurück. Eine InvalidOperationException wird ausgelöst, wenn das Deque leer ist. |
| Performance | O (1) |
public T DequeueLast () if (_items.Count == 0) Neue InvalidOperationException werfen ("DequeueLast aufgerufen, wenn deque leer ist"); T temp = _items.Tail.Value; _items.RemoveLast (); Rücklauftemp; | Verhalten | Gibt das erste Element im Deque zurück, die Sammlung bleibt jedoch unverändert. Eine InvalidOperationException wird ausgelöst, wenn das Deque leer ist. |
| Performance | O (1) |
public T PeekFirst () if (_items.Count == 0) Neue InvalidOperationException werfen ("PeekFirst aufgerufen, wenn deque leer ist"); return _items.Head.Value; | Verhalten | Gibt den letzten Eintrag im Deque zurück, die Sammlung bleibt jedoch unverändert. Eine InvalidOperationException wird ausgelöst, wenn das Deque leer ist. |
| Performance | O (1) |
public T PeekLast () if (_items.Count == 0) Neue InvalidOperationException werfen ("PeekLast, wenn deque leer ist"); return _items.Tail.Value; | Verhalten | Gibt die Anzahl der Elemente zurück, die sich aktuell im Deque befinden, oder 0, wenn der Deque leer ist. |
| Performance | O (1) |
public int Count get return _items.Count;
Deques werden häufig verwendet, um andere Datenstrukturen zu implementieren.
Wir haben gesehen, wie ein Stack mit a implementiert wurde LinkedList, Lassen Sie uns nun einen mit a implementierten betrachten Deque.
Sie fragen sich vielleicht, warum ich mich für eine Implementierung entscheiden würde Stapel Verwendung einer Deque eher als ein LinkedList. Der Grund ist die Leistung und die Wiederverwendbarkeit von Code. Eine verknüpfte Liste verursacht die Kosten pro Knoten und reduziert die Datenlokalität. Die Elemente werden im Heapspeicher zugewiesen, und die Speicherplätze befinden sich möglicherweise nicht in der Nähe voneinander. Dies führt zu einer größeren Anzahl von Cache-Fehlern und Seitenfehlern in der CPU- und Speicherhardware Ebenen. Bei einer Implementierung einer Warteschlange mit besserer Leistung wird möglicherweise ein Array als Sicherungsspeicher und nicht als Liste verwendet. Dies würde einen geringeren Aufwand pro Knoten ermöglichen und die Leistung verbessern, indem einige Lokalitätsprobleme behoben werden.
Implementierung eines Stapel oder Warteschlange Ein Array ist jedoch eine komplexere Implementierung. Durch die Implementierung der Deque Auf diese komplexere Weise und als Basis für andere Datenstrukturen können wir die Leistungsvorteile für alle Strukturen realisieren und müssen den Code nur einmal schreiben. Dies beschleunigt die Entwicklungszeit und reduziert die Wartungskosten.
Wir werden uns ein Beispiel von a anschauen Deque als Array später in diesem Abschnitt, aber zunächst ein Beispiel für a Stapel implementiert mit einem Deque.
öffentliche Klasse Stack Deque _items = new Deque (); public void Push (T-Wert) _items.EnqueueFirst (Wert); public T Pop () return _items.DequeueFirst (); public T Peek () return _items.PeekFirst (); public int Count get return _items.Count;
Beachten Sie, dass die gesamte Fehlerprüfung jetzt auf den verschoben wird Deque und jegliche Optimierung oder Fehlerbehebung im Deque gilt automatisch für die Stapel Klasse. Implementierung eines Warteschlange ist genauso einfach und bleibt dem Leser als Übung überlassen.
Wie bereits erwähnt, bietet die Verwendung eines Arrays anstelle einer verknüpften Liste Vorteile als Backing Store für Deque (ein Deque von ganzen Zahlen). Konzeptionell erscheint dies einfach, aber es gibt mehrere Probleme, die angegangen werden müssen, damit dies funktioniert.
Lassen Sie uns einige dieser Probleme grafisch betrachten und dann sehen, wie wir damit umgehen könnten. Berücksichtigen Sie dabei die im Abschnitt ArrayList diskutierten Probleme der Wachstumspolitik und dass diese Probleme hier zutreffen.
Wenn die Sammlung erstellt wird, handelt es sich um ein Array mit einer Länge von 0. Schauen wir uns an, wie sich einige Aktionen auf das interne Array auswirken. Beachten Sie dabei, dass sich das grüne "h" und das rote "t" in den Abbildungen auf "Kopf" bzw. "Schwanz" beziehen. Der Kopf und der Schwanz sind die Arrayindizes, die das erste und letzte Element in der Warteschlange angeben. Wenn Sie Elemente hinzufügen und entfernen, wird die Interaktion zwischen Kopf und Schwanz klarer.
Deque deq = new Deque (); deq.EnqueueFirst (1);
Hinzufügen eines Wertes vor der Deque deq.EnqueueLast (2);
Hinzufügen eines Wertes am Ende des Deque deq.EnqueueFirst (0);
Hinzufügen eines anderen Wertes vor der Deque; der Kopfindex wickelt sich um Beachten Sie, was an dieser Stelle passiert ist. Der Kopfindex wurde bis zum Ende des Arrays umbrochen. Nun der erste Artikel in der Deque, was von zurückgegeben werden würde DequeueFirst, ist der Wert am Array-Index drei (Null).
deq.EnqueueLast (3);
Hinzufügen eines Wertes am Ende des Deque Zu diesem Zeitpunkt ist das Array gefüllt. Wenn ein anderes Element hinzugefügt wird, geschieht Folgendes:
EnqueueFirst - Das Element wird am Index Null hinzugefügt (der Kopiervorgang lässt dies offen)..EnqueueLast - Das Element wird am Ende des Arrays hinzugefügt. deq.EnqueueLast (4);
Hinzufügen eines Wertes am Ende des erweiterten Deque Nun wollen wir sehen, was passiert, wenn Elemente aus dem Deque entfernt werden.
deq.DequeueFirst ();
Das erste Element aus dem erweiterten Deque entfernen deq.DequeueLast ();
Das letzte Element aus dem erweiterten Deque entfernen Der kritische Punkt ist, dass unabhängig von der Kapazität des internen Arrays der logische Inhalt des Deque die Elemente vom Head-Index bis zum Tail-Index sind, wobei die Notwendigkeit berücksichtigt wird, am Ende des Arrays umzukehren. Ein Array, das das Verhalten des Umwickelns vom Kopf bis zum Schwanz bietet, wird häufig als Ringpuffer bezeichnet.
Lassen Sie uns mit diesem Verständnis der Funktionsweise der Array-Logik direkt in den Code eintauchen.
Die Array-basierten Deque-Methoden und -Eigenschaften entsprechen denen der Liste, sodass sie hier nicht wiederholt werden. Die Liste wurde jedoch durch ein Array ersetzt, und es gibt jetzt drei Eigenschaften, die Informationen zu Größe, Kopf und Ende enthalten.
öffentliche Klasse Deque T [] _items = new T [0]; // Die Anzahl der Elemente in der Warteschlange. int _size = 0; // Der Index des ersten (ältesten) Elements in der Warteschlange. int _head = 0; // Der Index des letzten (neuesten) Elements in der Warteschlange. int _tail = -1;…
Wenn das interne Array vergrößert werden muss, muss der Algorithmus zur Vergrößerung des Arrays, zum Kopieren des Arrayinhalts und zum Aktualisieren der internen Indexwerte ausgeführt werden. Das Enqueue Die Methode führt diese Operation aus und wird von beiden aufgerufen EnqueueFirst und EnqueueLast. Das StartingIndex Über den Parameter wird festgelegt, ob der Array-Slot bei Index Null geöffnet bleiben soll (im Fall von EnqueueFirst).
Achten Sie besonders darauf, wie die Daten ausgepackt werden, wenn der Weg vom Kopf zum Schwanz das Ende des Arrays auf Null zurückgehen muss.
private void allocateNewArray (int startingIndex) int newLength = (_size == 0)? 4: _size * 2; T [] newArray = new T [newLength]; if (_size> 0) int targetIndex = startingIndex; // Kopieren Sie den Inhalt… // Wenn das Array nicht umbrochen ist, kopieren Sie einfach den gültigen Bereich. // Sonst, kopiere vom Kopf bis zum Ende des Arrays und dann von 0 bis zum Ende. // Wenn der Schwanz weniger als der Kopf ist, haben wir gewickelt. if (_tail < _head) // Copy the _items[head]… _items[end] -> newArray [0]… newArray [N]. for (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;
| Verhalten | Fügt den angegebenen Wert dem Kopf der Warteschlange hinzu. Dies ist der nächste von DequeueFirst in der Warteschlange stehende Artikel. |
| Performance | O (1) in den meisten Fällen; O (n) wenn Wachstum notwendig ist. |
public void EnqueueFirst (T-Element) // Wenn das Array größer werden muss. if (_items.Length == _size) allocateNewArray (1); // Da wir wissen, dass das Array nicht voll ist und _head größer als 0 ist, // wissen wir, dass der Schlitz vor dem Kopf offen ist. if (_head> 0) _head--; else // Andernfalls müssen wir uns bis zum Ende des Arrays bewegen. _head = _items.Length - 1; _items [_head] = item; _size ++;
| Verhalten | Fügt den angegebenen Wert zum Ende der Warteschlange hinzu. Dies ist der nächste von DequeueLast in der Warteschlange stehende Artikel. |
| Performance | O (1) in den meisten Fällen; O (n) wenn Wachstum notwendig ist. |
public void EnqueueLast (T item) // Wenn das Array größer werden muss. if (_items.Length == _size) allocateNewArray (0); // Jetzt haben wir ein Array mit der richtigen Größe und können uns auf das Umschließen von Problemen konzentrieren. // Wenn sich _tail am Ende des Arrays befindet, müssen wir uns umschließen. if (_tail == _items.Length - 1) _tail = 0; else _tail ++; _items [_tail] = item; _size ++;
| Verhalten | Entfernt den ersten Artikel im Deque und gibt ihn zurück. Eine InvalidOperationException wird ausgelöst, wenn das Deque leer ist. |
| Performance | O (1) |
public T DequeueFirst () if (_size == 0) Neue InvalidOperationException werfen ("Der Deque ist leer"); T value = _items [_head]; if (_head == _items.Length - 1) // Wenn sich der Kopf am letzten Index des Arrays befindet, wickeln Sie ihn um. _head = 0; else // Zum nächsten Slot wechseln. _head ++; _Größe--; Rückgabewert; | Verhalten | Entfernt den letzten Eintrag im Deque und gibt ihn zurück. Eine InvalidOperationException wird ausgelöst, wenn das Deque leer ist. |
| Performance | O (1) |
public T DequeueLast () if (_size == 0) Neue InvalidOperationException werfen ("Der Deque ist leer"); T value = _items [_tail]; if (_tail == 0) // Wenn sich das Ende am ersten Index des Arrays befindet, wickeln Sie es ein. _tail = _items.Length - 1; else // Zum vorherigen Steckplatz wechseln. _Schwanz--; _Größe--; Rückgabewert; | Verhalten | Gibt das erste Element im Deque zurück, die Sammlung bleibt jedoch unverändert. Ein InvalidOperationException wird geworfen, wenn der Deque leer ist. |
| Performance | O (1) |
public T PeekFirst () if (_size == 0) Neue InvalidOperationException werfen ("Der Deque ist leer"); return _items [_head]; | Verhalten | Gibt den letzten Eintrag im Deque zurück, die Sammlung bleibt jedoch unverändert. Ein InvalidOperationException wird geworfen, wenn der Deque leer ist. |
| Performance | O (1) |
public T PeekLast () if (_size == 0) Neue InvalidOperationException werfen ("Der Deque ist leer"); return _items [_tail]; | Verhalten | Gibt die Anzahl der Elemente zurück, die sich aktuell im Deque befinden, oder 0, wenn der Deque leer ist. |
| Performance | O (1) |
public int Count get return _size;
