Y at-il en C# un conteneur générique déjà défini qui peut être utilisé comme pile et comme file d'attente en même temps? Je veux juste être en mesure d'ajouter des éléments, soit à la fin ou à l'avant de la file d'attenteC# pile pile file d'attente
grâce
Vérifiez la classe LinkedList.
LinkedList<int> list = new LinkedList<int>();
list.AddFirst(1);
list.AddLast(2);
list.AddFirst(0);
Ce que vous voulez est un linked list - il y a un dans le BCL - qui a AddFirst et AddLast méthodes
Voici mon implémentation d'un deque immuable:
Notez que ceci est un immuable amphidrome-file d'attente. Normalement, vous pensez probablement d'une file d'attente comme quelque chose que vous muter:
queue.Enqueue(10);
Une file d'attente immuable reste toujours le même; lorsque vous ajoutez un nouvel élément, il vous redonne une toute nouvelle file d'attente, si vous l'utilisez comme:
queue = queue.Enqueue(10);
si vous ne se soucient plus de la valeur ancienne.
Bon vieux List<T> le fera.
Add() pour mettre en file d'attente, Insert(0,T) pour pousser, Remove(0) pour pop/dequeue.
Insérer et supprimer seront tous les deux des opérations O (n). Une liste chaînée sera O (1) – thecoop
Cool - mon premier downvote. Merci d'avoir signalé l'O (n). Mais pour être pointilleux, ne serait-ce pas seulement O (n) sur les inserts au début de la liste mais pas à la fin (puisque c'est basé sur Array)? –
Cela dépend du coût auquel vous faites référence. Parlez-vous du coût * amorti *, ou du coût * le moins cher *? Le coût amorti de l'insertion de n éléments à la fin d'une liste double-quand-complète est O (1). Le coût le plus défavorable de l'insertion d'un élément dans une liste double-quand-complète de n éléments est O (n). –
est ici une classe pour aider les gens à mettre en œuvre cette facilement:
public class StackQueue<T>
{
private LinkedList<T> linkedList = new LinkedList<T>();
public void Push(T obj)
{
this.linkedList.AddFirst(obj);
}
public void Enqueue(T obj)
{
this.linkedList.AddFirst(obj);
}
public T Pop()
{
var obj = this.linkedList.First.Value;
this.linkedList.RemoveFirst();
return obj;
}
public T Dequeue()
{
var obj = this.linkedList.Last.Value;
this.linkedList.RemoveLast();
return obj;
}
public T PeekStack()
{
return this.linkedList.First.Value;
}
public T PeekQueue()
{
return this.linkedList.Last.Value;
}
public int Count
{
get
{
return this.linkedList.Count;
}
}
}
Avec tout le respect, cela ne semble pas répondre à sa question. – StriplingWarrior
Le lien a une classe qui définit ce que l'OP recherchait. L'exemple donné dans cette réponse ne le montre pas vraiment. –
StriplingWarrior, je n'ai aucune idée de ce dont vous parlez. L'affiche demande un conteneur générique existant qui agit comme une pile ou une file d'attente. Un tel conteneur est appelé "deque", et j'ai fourni un lien vers le code source pour une implémentation de ce type. Exactement quelle partie de la question n'a pas été répondue? –