```html <p>c# Ajout d'une méthode Remove(int index) à la classe Queue .NET</p> ```

Question

Je voudrais utiliser la classe de file d'attente générique telle que décrite dans le framework .NET (3.5) mais j'aurai besoin d'une méthode Remove(int index) pour supprimer des éléments de la file d'attente. Est-ce que je peux obtenir cette fonctionnalité avec une méthode d'extension? Quelqu'un pourrait-il me guider dans la bonne direction?

Answer 1

Ce que vous voulez, c'est une List où vous appelez toujours RemoveAt(0) lorsque vous voulez obtenir l'élément de la Queue. Tout le reste est pareil, vraiment (appeler Add ajouterait un élément à la fin de la Queue).

Answer 2

Voici comment supprimer un élément spécifique de la file d'attente avec une seule ligne de Linq (cela recrée la file d'attente, MAIS faute d'une meilleure méthode...)

//remplacez "" par votre véritable type sous-jacent
myqueue = new Queue(myqueue.Where(s => s != itemToBeRemoved));

Je sais que ce n'est pas enlevant par index, mais quelqu'un pourrait trouver cela utile (cette question se classe dans Google pour "enlever un élément spécifique d'une file d'attente c#" donc j'ai décidé d'ajouter cette réponse, désolé)

Answer 3

En combinant les suggestions de casperOne et David Anderson au niveau suivant. La classe suivante hérite de List et masque les méthodes qui seraient préjudiciables au concept FIFO tout en ajoutant les trois méthodes de Queue (Equeue, Dequeu, Peek).

public class ListQueue : List
{
    new public void Add(T item) { throw new NotSupportedException(); }
    new public void AddRange(IEnumerable collection) { throw new NotSupportedException(); }
    new public void Insert(int index, T item) { throw new NotSupportedException(); }
    new public void InsertRange(int index, IEnumerable collection) { throw new NotSupportedException(); }
    new public void Reverse() { throw new NotSupportedException(); }
    new public void Reverse(int index, int count) { throw new NotSupportedException(); }
    new public void Sort() { throw new NotSupportedException(); }
    new public void Sort(Comparison comparison) { throw new NotSupportedException(); }
    new public void Sort(IComparer comparer) { throw new NotSupportedException(); }
    new public void Sort(int index, int count, IComparer comparer) { throw new NotSupportedException(); }

    public void Enqueue(T item)
    {
        base.Add(item);
    }

    public T Dequeue()
    {
        var t = base[0]; 
        base.RemoveAt(0);
        return t;
    }

    public T Peek()
    {
        return base[0];
    }
}

Code de test:

class Program
{
    static void Main(string[] args)
    {
        ListQueue queue = new ListQueue();

        Console.WriteLine("Nombre d'éléments dans ListQueue : {0}", queue.Count);
        Console.WriteLine();

        for (int i = 1; i <= 10; i++)
        {
            var text = String.Format("Test{0}", i);
            queue.Enqueue(text);
            Console.WriteLine("Juste ajouté à la file d'attente : {0}", text);
        }

        Console.WriteLine();
        Console.WriteLine("Nombre d'éléments dans ListQueue : {0}", queue.Count);
        Console.WriteLine();

        var peekText = queue.Peek();
        Console.WriteLine("Juste jeté un œil à : {0}", peekText);
        Console.WriteLine();

        var textToRemove = "Test5";
        queue.Remove(textToRemove);
        Console.WriteLine("Juste supprimé : {0}", textToRemove);
        Console.WriteLine();

        var queueCount = queue.Count;
        for (int i = 0; i < queueCount; i++)
        {
            var text = queue.Dequeue();
            Console.WriteLine("Juste retiré de la file d'attente : {0}", text);
        }

        Console.WriteLine();
        Console.WriteLine("Nombre d'éléments dans ListQueue : {0}", queue.Count);

        Console.WriteLine();
        Console.WriteLine("Maintenant essayez d'AJOUTER un élément...devrait provoquer une exception.");
        queue.Add("doitÉchouer");

    }
}

Answer 4

C'est une réponse assez tardive mais je l'écris pour les lecteurs futurs

List est exactement ce dont vous avez besoin mais il a un gros inconvénient par rapport à Queue : il est implémenté avec un tableau, donc Dequeue() est assez coûteux (en termes de temps) car tous les éléments doivent être décalés d'un pas avec Array.Copy. Même Queue utilise un tableau mais avec deux indices (pour la tête et la queue).

Dans votre cas, vous avez également besoin de Remove/RemoveAt et ses performances ne seront pas bonnes (pour la même raison : si vous ne retirez pas de la queue de la liste, un autre tableau doit être alloué et les éléments copiés).

Une meilleure structure de données pour avoir un temps de Dequeue/Remove rapide est une liste chaînée (vous sacrifierez - un peu - les performances pour Enqueue mais en supposant que votre queue a un nombre égal d'opérations Enqueue/Dequeue, vous obtiendrez un gain important en performances, surtout lorsque sa taille augmentera).

Voici un squelette simple pour son implémentation (je vais passer sous silence l'implémentation pour IEnumerable, IList et d'autres méthodes d'aide).

class LinkedQueue
{
    public int Count
    {
        get { return _items.Count; }
    }

    public void Enqueue(T item)
    {
        _items.AddLast(item);
    }

    public T Dequeue()
    {
        if (_items.First == null)
           throw new InvalidOperationException("...");

        var item = _items.First.Value;
        _items.RemoveFirst();

        return item;
    }

    public void Remove(T item)
    {
        _items.Remove(item);
    }

    public void RemoveAt(int index)
    {
        Remove(_items.Skip(index).First());
    }

    private LinkedList _items = new LinkedList();
}

Pour une comparaison rapide :

Queue            List              LinkedList
Enqueue    O(1)/O(n)\*       O(1)/O(n)\*        O(1)
Dequeue    O(1)             O(n)              O(1)
Remove     n/a              O(n)              O(n)

* O(1) est le cas typique mais parfois il sera O(n) (lorsque le tableau interne doit être redimensionné).

Bien sûr, vous paierez quelque chose pour ce que vous gagnez : l'utilisation de la mémoire est plus importante (surtout pour un petit T le surcoût sera important). Le bon choix d'implémentation (List vs LinkedList) doit être choisi judicieusement en fonction de votre scénario d'utilisation, vous pouvez également convertir ce code pour utiliser une liste chaînée simple pour réduire de 50% le surcoût de mémoire.

Answer 5

Bien qu'il n'y ait pas de méthode intégrée, vous ne devriez pas utiliser une structure de liste ou une autre structure, IFF RemoveAt n'est pas une opération fréquente.

Si vous ajoutez et retirez normalement mais que vous supprimez seulement de temps en temps, alors vous devriez pouvoir vous permettre de reconstruire la file d'attente lors de la suppression.

public static void Remove(this Queue queue, T itemToRemove) where T : class
{
    var list = queue.ToList(); // Besoin de faire une copie, pour pouvoir vider la file
    queue.Clear();
    foreach (var item in list)
    {
        if (item == itemToRemove)
            continue;

        queue.Enqueue(item);
    }
}

public static void RemoveAt(this Queue queue, int itemIndex) 
{
    var list = queue.ToList(); // Besoin de faire une copie, pour pouvoir vider la file
    queue.Clear();

    for (int i = 0; i < list.Count; i++)
    {
        if (i == itemIndex)
            continue;

        queue.Enqueue(list[i]);
    }
}

L'approche suivante pourrait être plus efficace, utilisant moins de mémoire et donc moins de GC :

public static void RemoveAt(this Queue queue, int itemIndex)
{
    var cycleAmount = queue.Count;

    for (int i = 0; i < cycleAmount; i++)
    {
        T item = queue.Dequeue();
        if (i == itemIndex)
            continue;

        queue.Enqueue(item);
    }
}