Stack est un type de données abstrait (ADT) et il est censé avoir une liste scellée d'opérations comme Push (), Pop (), Peek (), ... pour appliquer le principe du dernier entré, premier sorti (LIFO).

Mais il a ElementAt (index) qui me permet d'accéder à n'importe quel élément de la pile. À ma connaissance, Stack devrait avoir moins de visibilité sur les éléments qui ne sont pas dans la surface. N'est-ce pas?

2
Ashokan Sivapragasam 23 mai 2018 à 10:44

3 réponses

Meilleure réponse

La pile est un type de données abstrait (ADT)

C'est vrai pour le concept général de Stack, mais System.Collections.Generic.Stack<T> ne promet jamais d'être (juste) un ADT.

Il doit fournir au minimum la fonctionnalité ADT (pour être à la hauteur de son nom) mais est libre d'en offrir davantage.

Il ne tente donc pas de masquer Contains (), Count, TryPeek (), etc.

4
bommelding 23 mai 2018 à 07:52

En pseudo-code, voici un ElementAt qui est externe à Stack et n'utilise que les opérations ADT:

T ElementAt<T>(Stack<T> items, int index)
{
    var tmp = new Stack<T>();
    while(!items.Empty && index > 0)
    {
       tmp.Push(items.Peek());
       items.Pop();
       index --
    }
    try {
        return items.Peek(); //Presumed to throw an appropriate exception if empty
    }
    finally {
       while(!tmp.Empty)
       {
          items.Push(tmp.Peek());
          tmp.Pop();
       }
    }
}

(Ce qui précède suppose la mutation des Stack s - une implémentation légèrement différente fonctionnerait pour les piles immuables et n'aurait pas besoin de l'action d'annulation maladroite)

Bien sûr, le fait est que le type Stack dans .NET est construit pour la résolution de problèmes pratiques , pas pour une certaine pureté abstraite, et (à force de {{X1} } offre d'autoriser l'énumération), une implémentation plus efficace est actuellement disponible ici. Et nous ne forçons pas les gens à copier de telles méthodes dans une bibliothèque "utils".

3
Damien_The_Unbeliever 23 mai 2018 à 08:02

ElementAt() est fourni via {{ X1}}, pas via l'interface Stack<T>.

Cela fonctionne parce que Stack<T> implémente IEnumerable<T> qui est tout ce qui est nécessaire pour implémenter ElementAt() puisque tout ce qu'il fait est d'itérer à travers tous les éléments fournis via IEnumerable<T> jusqu'à ce que N d'entre eux aient été consulté.

Pour un Stack<T>, c'est une opération O (N). Si vous utilisez ElementAt() avec, par exemple, un List<T>, alors une optimisation interne le transforme en une opération O (1).

Quant à savoir pourquoi Stack<T> implémente IEnumerable<T> - un seul des concepteurs peut vraiment répondre à cette question. Puisqu'il s'agit d'une opération sans mutation, cela ne viole vraiment rien de fondamental à propos de la pile. Je suppose qu'il a été fourni par commodité.

Comme le souligne / u / Damien_The_Unbeliever dans sa réponse, le code pourrait déterminer le Nième élément sans l'interface IEnumerable en faisant apparaître N éléments dans une autre pile, puis en les repoussant tous dans l'ordre inverse de sorte que la pile d'origine reste inchangée.

Le problème ici est que Microsoft ne documente pas l'ordre dans lequel Stack's IEnumerable renvoie ses éléments. Vous pouvez inspecter le code source pour voir qu'il renvoie effectivement les éléments dans l'ordre LIFO - mais cela n'est tout simplement pas documenté.

Cette question est abordée dans les réponses à cette question.

Dans tous les cas, où l'interface ADT est-elle définie pour la pile abstraite dont vous parlez? Je ne pense pas qu'il y ait de réponse définitive à cela. À proprement parler, on pourrait dire qu'une pile n'a que Push() et Pop(). Et pourtant, la plupart des implémentations fournissent également Count.

Comme l'article sur Stack sur Wikipedia déclare:

Dans de nombreuses implémentations, une pile a plus d'opérations que "push" et "pop". Un exemple est "top of stack", ou "peek", qui observe l'élément le plus haut sans le retirer de la pile.

Puisque cela peut être fait avec un "pop" et un "push" avec les mêmes données, ce n'est pas indispensable. Une condition de sous-dépassement peut se produire dans l'opération "stack top" si la pile est vide, identique à "pop". De plus, les implémentations ont souvent une fonction qui renvoie simplement si la pile est vide.

Donc, fondamentalement, la réponse à votre question est:

Les concepteurs de la bibliothèque ont décidé d'ajouter des méthodes pratiques sans mutation en plus des méthodes de mutation Push() et Pop().

6
Matthew Watson 23 mai 2018 à 08:16