Share
Jusqu'ici, nous avons examiné les collections qui fournissent un stockage de données très basique, essentiellement des abstractions sur un tableau. Dans cette section, nous allons examiner ce qui se passe lorsque nous ajoutons quelques comportements très fondamentaux qui modifient entièrement l'utilité des collections..
Une pile est une collection qui renvoie des objets à l'appelant selon un modèle LIFO (dernier entré, premier sorti). Cela signifie que le dernier objet ajouté à la collection sera le premier objet renvoyé..
Les piles diffèrent des collections list et array. Ils ne peuvent pas être indexés directement, les objets sont ajoutés et supprimés à l'aide de méthodes différentes et leur contenu est plus opaque que les listes et les tableaux. Ce que je veux dire par là, c'est qu'une collection basée sur des listes fournit une méthode Contains, mais pas une pile. En outre, une pile n'est pas énumérable. Pour comprendre pourquoi, voyons ce qu'est une pile et comment l'utilisation d'une pile entraîne ces différences.
L'une des analogies les plus courantes pour une pile est la pile de plaques de restaurant. Il s’agit d’un simple dispositif à ressort sur lequel sont empilées des plaques propres. Le ressort garantit que, quel que soit le nombre de plaques dans la pile, la plaque supérieure est facilement accessible. Des assiettes propres sont ajoutées en haut de la pile et lorsqu'un client retire une assiette, il enlève l'assiette la plus haute (l'ajout le plus récent)..
Nous commençons avec un porte-assiettes vide.
Une pile d'assiettes vide (le ressort ne contient pas d'assiettes) Et puis nous ajoutons une plaque rouge, une plaque bleue et une plaque verte au support dans cet ordre..
Le point clé à comprendre ici est que lorsque de nouvelles plaques sont ajoutées, elles s’ajoutent au sommet de la pile. Si un client récupère une plaque, il obtiendra la dernière plaque ajoutée (la plaque verte). Le prochain client obtiendrait la plaque bleue et finalement la plaque rouge serait retirée..
Maintenant que nous savons comment fonctionne une pile, définissons quelques nouveaux termes. Lorsqu'un élément est ajouté à la pile, il est «poussé» à l'aide du bouton Pousser méthode. Lorsqu'un élément est retiré de la pile, il est «extrait» à l'aide du bouton Pop méthode. Le dernier élément de la pile, le plus récemment ajouté, peut être visualisé à l'aide de la Peek méthode. Le coup d'oeil vous permet de voir l'article sans le retirer de la pile (tout comme le client du rack à assiettes serait en mesure de voir la couleur de la plaque supérieure). Avec ces termes à l’esprit, examinons la mise en œuvre d’un système Empiler classe.
le Empiler classe définit Pousser, Pop, et Peek méthodes, un Compter propriété, et utilise le LinkedList classe pour stocker les valeurs contenues dans la pile.
Classe publique Stack LinkedList _items = new LinkedList (); public void Push (valeur T) jette new NotImplementedException (); public T Pop () lance new NotImplementedException (); public T Peek () lance new NotImplementedException (); public int Count get;
| Comportement | Ajoute un objet en haut de la pile. |
| Performance | O (1) |
Puisque nous utilisons une liste chaînée comme magasin de support, il suffit d’ajouter le nouvel élément à la fin de la liste..
public void Push (valeur T) _items.AddLast (valeur);
| Comportement | Supprime et renvoie le dernier élément ajouté à la pile. Si la pile est vide, un InvalidOperationException Est lancé. |
| Performance | O (1) |
Pousser ajoute des éléments au dos de la liste, nous allons donc les «extraire» du dos. Si la liste est vide, une exception est levée.
Accentsconagua
public T Pop () if (_items.Count == 0) jette new InvalidOperationException ("La pile est vide"); T resultat = _items.Tail.Value; _items.RemoveLast (); retourne le résultat; | Comportement | Retourne le dernier élément ajouté à la pile mais laisse celui-ci dans la pile. Si la pile est vide, un InvalidOperationException Est lancé. |
| Performance | O (1) |
public T Peek () if (_items.Count == 0) jette new InvalidOperationException ("La pile est vide"); return _items.Tail.Value; | Comportement | Retourne le nombre d'éléments dans la pile. |
| Performance | O (1) |
Puisque la pile est supposée être une structure de données opaque, pourquoi avons-nous un Compter propriété? Savoir si une pile est vide (Compter == 0) est très utile, surtout depuis Pop lève une exception lorsque la pile est vide.
public int Count get return _items.Count;
L’exemple classique de pile est le calculateur Reverse Polish Notation (RPN).
La syntaxe RPN est assez simple. Il utilise:
plutôt que le traditionnel:
En d'autres termes, au lieu de dire «4 + 2», nous dirions «4 2 +». Si vous voulez comprendre la signification historique de la syntaxe RPN, je vous encourage à vous rendre sur Wikipedia ou sur votre moteur de recherche préféré..
La façon dont RPN est évalué, et la raison pour laquelle une pile est si utile lors de l'implémentation d'un calculateur RPN, peuvent être vues dans l'algorithme suivant:
pour chaque valeur d'entrée si la valeur est un entier, insérez la valeur dans la pile de l'opérande, sinon, si la valeur est un opérateur, affichez les valeurs gauche et droite de la pile, puis évaluez l'opérateur, insérez le résultat dans la pile..
Donc, étant donné la chaîne d'entrée «4 2 +», les opérations seraient:
pousser (4) pousser (2) pousser (pop () + pop ())
Maintenant, la pile contient une seule valeur: six (la réponse).
Ce qui suit est une implémentation complète d’une calculatrice simple qui lit une équation (par exemple, «4 2 +») à partir d’une entrée de console, divise l’entrée à chaque espace ([«4», «2» et «+»]). et exécute l’algorithme RPN sur l’entrée. La boucle continue jusqu'à ce que l'entrée soit le mot "quitter".
void RpnLoop () while (true) Console.Write (">"); chaîne d'entrée = Console.ReadLine (); if (input.Trim (). ToLower () == "quit") break; // La pile d'entiers non encore exploitée. Valeurs de pile = new Stack (); foreach (jeton de chaîne dans input.Split (new char [] ")) // Si la valeur est un entier… int valeur; if (int.TryParse (jeton, valeur de sortie)) //… le pousser à la pile. values.Push (valeur); else // Sinon, évaluez l'expression… int rhs = values.Pop (); int lhs = values.Pop (); //… et insérez le résultat dans la pile. switch (jeton) case "+": valeurs.Push (lhs + rhs); pause; case "-": valeurs.Push (lhs - rhs); break; cas "*": valeurs.Push (lhs * rhs) ; break; case "/": values.Push (lhs / rhs); break; case "%": valeurs.Push (lhs% rhs); break; défaut: lancer un nouvel ArgumentException (string.Format ("Jeton non reconnu: 0 ", jeton)); // Le dernier élément de la pile est le résultat. Console.WriteLine (values.Pop ()); Les files d'attente ressemblent beaucoup aux piles. Elles fournissent une collection opaque à partir de laquelle des objets peuvent être ajoutés (mis en file d'attente) ou supprimés (mis en file d'attente) de manière à ajouter de la valeur à une collection basée sur une liste..
Les files d'attente sont une collection FIFO (First-In-First-Out). Cela signifie que les éléments sont supprimés de la file d'attente dans l'ordre où ils ont été ajoutés. Vous pouvez penser à une file d'attente comme une ligne à un comptoir de caisse de magasin: des personnes entrent dans la ligne et sont traitées dans l'ordre d'arrivée..
Les files d'attente sont couramment utilisées dans les applications pour fournir un tampon permettant d'ajouter des éléments pour un traitement ultérieur ou pour fournir un accès ordonné à une ressource partagée. Par exemple, si une base de données est capable de gérer une seule connexion, une file d'attente peut être utilisée pour permettre aux threads d'attendre leur tour (dans l'ordre) pour accéder à la base de données..
le Queue, comme le Empiler, est soutenu par un LinkedList. En outre, il fournit les méthodes En file d'attente (pour ajouter des articles), Dequeue (pour enlever des articles), Peek, et Compter. Comme Empiler, il ne sera pas traité comme une collection à usage général, ce qui signifie qu'il ne sera pas mis en œuvre ICollection.
Classe publique Queue LinkedList _items = new LinkedList (); public void Enqueue (valeur T) lance la nouvelle NotImplementedException (); public T Dequeue () lance new NotImplementedException (); public T Peek () lance new NotImplementedException (); public int Count get;
| Comportement | Ajoute un élément à la fin de la file d'attente. |
| Performance | O (1) |
Cette implémentation ajoute l'élément au début de la liste liée. L'élément pourrait tout aussi bien être ajouté à la fin de la liste. Ce qui compte vraiment, c'est que les éléments soient mis en file d'attente à une extrémité de la liste et retirés de la file d'attente (FIFO). Notez qu'il s'agit du contraire de la classe Stack où des éléments sont ajoutés et supprimés de la même fin (LIFO).
Public Void Enqueue (valeur T) _items.AddFirst (valeur);
| Comportement | Supprime et renvoie l'élément le plus ancien de la file d'attente. Un InvalidOperationException est jeté si la file est vide. |
| Performance | O (1) |
Puisque En file d'attente ajouté l'article au début de la liste, Dequeue doit supprimer l'élément à la fin de la liste. Si la file d'attente ne contient aucun élément, une exception est levée..
public T Dequeue () if (_items.Count == 0) lance le nouvel InvalidOperationException ("La file d'attente est vide"); T last = _items.Tail.Value; _items.RemoveLast (); retourne en dernier; | Comportement | Renvoie le prochain élément qui serait renvoyé si Dequeue était appelé. La file d'attente est laissée inchangée. Une exception InvalidOperationException est levée si la file d'attente est vide. |
| Performance | O (1) |
public T Peek () if (_items.Count == 0) jette new InvalidOperationException ("La file d'attente est vide"); return _items.Tail.Value; | Comportement | Renvoie le nombre d'éléments actuellement dans la file d'attente. Renvoie 0 si la file est vide. |
| Performance | O (1) |
public int Count get return _items.Count;
Une file d'attente à deux extrémités, ou deque, étend le comportement de la file d'attente en permettant l'ajout ou la suppression d'éléments de part et d'autre de la file d'attente. Ce nouveau comportement est utile dans plusieurs domaines problématiques, en particulier la planification de tâches et de threads. C'est aussi généralement utile pour implémenter d'autres structures de données. Nous verrons un exemple d'utilisation d'un deque pour implémenter une autre structure de données plus tard.
le Deque La classe est soutenue par une liste doublement liée. Cela nous permet d’ajouter et de supprimer des éléments au début ou à la fin de la liste et d’accéder au Premier et Dernier Propriétés. Les principaux changements entre la classe Queue et la classe Deque sont que le En file d'attente, Dequeue, et Peek les méthodes ont été doublées dans Premier et Dernier variantes.
Classe publique Deque LinkedList _items = new LinkedList (); public void EnqueueFirst (valeur T) lance new NotImplementedException (); public void EnqueueLast (valeur T) lance new NotImplementedException (); public T DequeueFirst () lance new NotImplementedException (); public T DequeueLast () lance new NotImplementedException (); public T PeekFirst () lance un nouveau NotImplementedException (); public T PeekLast () lance new NotImplementedException (); public int Count get;
| Comportement | Ajoute la valeur fournie à l'en-tête de la file d'attente. Ce sera le prochain élément retiré de la liste par DequeueFirst. |
| Performance | O (1) |
public void EnqueueFirst (valeur T) _items.AddFirst (valeur);
| Comportement | Ajoute la valeur fournie à la queue de la file d'attente. Ce sera le prochain élément retiré de la liste par DequeueLast. |
| Performance | O (1) |
public void EnqueueLast (valeur T) _items.AddLast (valeur);
| Comportement | Supprime et retourne le premier élément de la deque. Une exception InvalidOperationException est levée si le deque est vide. |
| Performance | O (1) |
public T DequeueFirst () if (_items.Count == 0) lance le nouvel InvalidOperationException ("DequeueFirst appelé lorsque deque est vide"); T temp = _items.Head.Value; _items.RemoveFirst (); retour temp; | Comportement | Supprime et renvoie le dernier élément de la deque. Une exception InvalidOperationException est levée si le deque est vide. |
| Performance | O (1) |
public T DequeueLast () if (_items.Count == 0) lance le nouvel InvalidOperationException ("DequeueLast a appelé lorsque deque est vide"); T temp = _items.Tail.Value; _items.RemoveLast (); retour temp; | Comportement | Retourne le premier élément de la deque mais laisse la collection inchangée. Une exception InvalidOperationException est levée si le deque est vide. |
| Performance | O (1) |
public T PeekFirst () if (_items.Count == 0) lance le nouvel InvalidOperationException ("PeekFirst appelé lorsque deque est vide"); return _items.Head.Value; | Comportement | Retourne le dernier élément de la deque mais laisse la collection inchangée. Une exception InvalidOperationException est levée si le deque est vide. |
| Performance | O (1) |
public T PeekLast () if (_items.Count == 0) lance le nouvel InvalidOperationException ("PeekLast appelé lorsque deque est vide"); return _items.Tail.Value; | Comportement | Retourne le nombre d'éléments actuellement dans le deque, ou 0 si le deque est vide. |
| Performance | O (1) |
public int Count get return _items.Count;
Les Deques sont souvent utilisés pour implémenter d'autres structures de données.
Nous avons vu une pile mise en œuvre en utilisant un LinkedList, Alors maintenant, regardons l'un mis en œuvre en utilisant un Deque.
Vous pourriez vous demander pourquoi je choisirais de mettre en œuvre un Empiler utilisant un Deque Plutôt qu'un LinkedList. La raison en est une de la performance et de la réutilisation du code. Une liste chaînée a le coût de la surcharge par nœud et de la localisation réduite des données. Les éléments sont alloués dans le segment de mémoire et les emplacements mémoire peuvent ne pas être proches les uns des autres, ce qui entraîne un plus grand nombre d'erreurs de cache et de défauts de page au niveau du processeur et de la mémoire niveaux. Une implémentation plus performante d'une file d'attente pourrait utiliser un tableau comme magasin de sauvegarde plutôt qu'une liste. Cela permettrait de réduire les frais généraux par nœud et pourrait améliorer les performances en résolvant certains problèmes de localité..
Mise en place d'un Empiler ou Queue comme un tableau est une mise en œuvre plus complexe, cependant. En mettant en œuvre le Deque De cette manière plus complexe et en utilisant cette base pour d’autres structures de données, nous pouvons réaliser les avantages en termes de performances pour toutes les structures tout en n’écrivant que le code une seule fois. Cela accélère le temps de développement et réduit les coûts de maintenance.
Nous allons examiner un exemple de Deque comme un tableau plus tard dans cette section, mais d'abord, regardons un exemple d'un Empiler mis en œuvre à l'aide d'un Deque.
public class Stack Deque _items = new Deque (); public void Push (valeur T) _items.EnqueueFirst (valeur); public T Pop () return _items.DequeueFirst (); public T Peek () return _items.PeekFirst (); public int Count get return _items.Count;
Notez que toute la vérification des erreurs est maintenant reportée à la Deque et toute optimisation ou correction de bogue apportée à la Deque s'appliquera automatiquement à la Empiler classe. Mise en place d'un Queue est tout aussi facile et reste comme un exercice pour le lecteur.
Comme mentionné précédemment, l’utilisation d’un tableau plutôt que d’une liste chaînée en tant que magasin de support pour le système présente des avantages. Deque (un deque de nombres entiers). Conceptuellement, cela semble simple, mais plusieurs problèmes doivent être résolus pour que cela fonctionne..
Examinons graphiquement certaines de ces questions, puis voyons comment nous pourrions les traiter. En cours de route, gardez à l'esprit les problèmes de politique de croissance abordés dans la section ArrayList et les mêmes problèmes qui s'appliquent ici..
Lorsque la collection est créée, il s'agit d'un tableau de longueur 0. Voyons comment certaines actions affectent le tableau interne. Au fur et à mesure, notez que le «h» vert et le «t» rouge dans les figures désignent respectivement «la tête» et «la queue». L'en-tête et la fin sont les index de tableau qui indiquent les premier et dernier éléments de la file d'attente. Au fur et à mesure que nous ajoutons et retirons des objets, l’interaction entre la tête et la queue deviendra plus claire..
Deque deq = new Deque (); deq.EnqueueFirst (1);
Ajouter une valeur à l'avant de la deque deq.EnqueueLast (2);
Ajouter une valeur à la fin de la deque deq.EnqueueFirst (0);
Ajout d'une autre valeur à l'avant de la deque; l'index de tête s'enroule Remarquez ce qui s'est passé à ce stade. L'index de tête est renvoyé à la fin du tableau. Maintenant, le premier article de la deque, ce qui serait retourné par DequeueFirst, est la valeur à l'index de tableau trois (zéro).
deq.EnqueueLast (3);
Ajouter une valeur à la fin de la deque À ce stade, le tableau est rempli. Lorsqu'un autre élément est ajouté, les événements suivants se produisent:
EnqueueFirst - L'élément est ajouté à l'indice zéro (l'opération de copie laisse cet élément ouvert).EnqueueLast - L'élément est ajouté à la fin du tableau. deq.EnqueueLast (4);
Ajouter une valeur à la fin de la deque développée Voyons maintenant ce qui se passe lorsque des objets sont retirés de la Deque.
deq.DequeueFirst ();
Retrait du premier article de la deque développée deq.DequeueLast ();
Retrait du dernier article de la deque développée Le point critique à noter est que, quelle que soit la capacité du tableau interne, le contenu logique du Deque correspond aux éléments allant de l’index de tête à l’index de queue, en tenant compte de la nécessité de boucler la boucle à la fin du tableau. Un tableau offrant le comportement de bouclage de la tête à la queue est souvent appelé tampon circulaire..
Avec cette compréhension du fonctionnement de la logique de tableau, passons directement au code.
Les méthodes et propriétés Deque basées sur des tableaux sont les mêmes que celles basées sur des listes, elles ne seront donc pas répétées ici. Cependant, la liste a été remplacée par un tableau et il existe maintenant trois propriétés pour contenir la taille, la tête et la fin..
classe publique Deque T [] _items = new T [0]; // Le nombre d'éléments dans la file d'attente. int _size = 0; // L'index du premier (le plus ancien) élément de la file d'attente. int _head = 0; // L'index du dernier élément (le plus récent) de la file d'attente. int _tail = -1;…
Lorsque le tableau interne doit être agrandi, l'algorithme augmente la taille du tableau, copie le contenu du tableau et met à jour les valeurs d'index interne à exécuter. le En file d'attente méthode effectue cette opération et est appelée par les deux EnqueueFirst et EnqueueLast. le startIndex Le paramètre est utilisé pour déterminer s’il faut laisser l’emplacement de tableau à l’indice zéro ouvert (dans le cas de EnqueueFirst).
Portez une attention particulière à la manière dont les données sont déroulées dans les cas où la marche de bout en bout nécessite de retourner à zéro à la fin du tableau.
Void privé allocateNewArray (int startingIndex) int newLength = (_size == 0)? 4: _size * 2; T [] newArray = new T [newLength]; if (_size> 0) int targetIndex = startIndex; // Copier le contenu… // Si le tableau n'a pas d'habillage, copiez simplement la plage valide. // Sinon, copie de haut en bas du tableau, puis de 0 à la fin. // Si la queue est inférieure à la tête, nous l'avons emballé. si (_tail < _head) // Copy the _items[head]… _items[end] -> newArray [0]… newArray [N]. pour (int index = _head; index < _items.Length; index++) newArray[targetIndex] = _items[index]; targetIndex++; // Copy _items[0]… _items[tail] -> newArray [N + 1]… pour (int index = 0; index <= _tail; index++) newArray[targetIndex] = _items[index]; targetIndex++; else // Copy the _items[head]… _items[tail] -> newArray [0]… newArray [N] pour (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;
| Comportement | Ajoute la valeur fournie à l'en-tête de la file d'attente. Ce sera le prochain élément retiré de la liste par DequeueFirst. |
| Performance | O (1) dans la plupart des cas; O (n) quand la croissance est nécessaire. |
public void EnqueueFirst (élément T) // Si le tableau doit être agrandi. if (_items.Length == _size) allocateNewArray (1); // Puisque nous savons que le tableau n'est pas plein et que _head est supérieur à 0, // nous savons que la fente devant la tête est ouverte. si (_head> 0) _head--; else // Sinon, nous devons revenir à la fin du tableau. _head = _items.Length - 1; _items [_head] = item; _size ++;
| Comportement | Ajoute la valeur fournie à la queue de la file d'attente. Ce sera le prochain élément retiré de la liste par DequeueLast. |
| Performance | O (1) dans la plupart des cas; O (n) quand la croissance est nécessaire. |
public void EnqueueLast (T item) // Si le tableau doit s'agrandir. if (_items.Length == _size) allocateNewArray (0); // Nous avons maintenant un tableau correctement dimensionné et nous pouvons nous concentrer sur les problèmes d'encapsulation. // Si _tail est à la fin du tableau, nous devons envelopper. if (_tail == _items.Length - 1) _tail = 0; else _tail ++; _items [_tail] = item; _size ++;
| Comportement | Supprime et retourne le premier élément de la deque. Une exception InvalidOperationException est levée si le deque est vide. |
| Performance | O (1) |
public T DequeueFirst () if (_size == 0) jette new InvalidOperationException ("Le deque est vide"); T valeur = _items [_head]; if (_head == _items.Length - 1) // Si la tête est au dernier index du tableau, retournez-la. _head = 0; else // Déplace le curseur vers le prochain emplacement. _head ++; _Taille--; valeur de retour; | Comportement | Supprime et renvoie le dernier élément de la deque. Une exception InvalidOperationException est levée si le deque est vide. |
| Performance | O (1) |
public T DequeueLast () if (_size == 0) lance le nouvel InvalidOperationException ("Le deque est vide"); T valeur = _items [_tail]; if (_tail == 0) // Si la queue est au premier index du tableau, retournez-la. _tail = _items.Length - 1; else // Aller à la case précédente. _queue--; _Taille--; valeur de retour; | Comportement | Retourne le premier élément de la deque mais laisse la collection inchangée. Un InvalidOperationException est jeté si le deque est vide. |
| Performance | O (1) |
public T PeekFirst () if (_size == 0) jette new InvalidOperationException ("The deque est vide"); return _items [_head]; | Comportement | Retourne le dernier élément de la deque mais laisse la collection inchangée. Un InvalidOperationException est jeté si le deque est vide. |
| Performance | O (1) |
public T PeekLast () if (_size == 0) jette new InvalidOperationException ("Le deque est vide"); return _items [_tail]; | Comportement | Retourne le nombre d'éléments actuellement dans le deque ou 0 si le deque est vide. |
| Performance | O (1) |
public int Count get return _size;
