c # Добавление метода Remove (int index) в класс .NET Queue

Question

Я хотел бы использовать общий класс очереди, как описано в .NET Framework (3.5) но мне понадобится метод Remove (int index) для удаления элементов из очереди. Могу ли я достичь этой функциональности с помощью метода расширения? Кто-нибудь хочет указать мне правильное направление?

Answer 1

То, что вы хотите, это List<T>, где вы всегда звоните RemoveAt(0), когда хотите получить предмет из Queue. Все остальное на самом деле то же самое (вызов Add добавит элемент в конец Queue).

Answer 2

Объединение предложений casperOne и Дэвида Андерсона на следующий уровень. Следующий класс наследует от List и скрывает методы, которые могут нанести ущерб концепции FIFO, при добавлении трех методов Queue (Equeue, Dequeu, Peek).

public class ListQueue<T> : List<T>
{
    new public void Add(T item) { throw new NotSupportedException(); }
    new public void AddRange(IEnumerable<T> collection) { throw new NotSupportedException(); }
    new public void Insert(int index, T item) { throw new NotSupportedException(); }
    new public void InsertRange(int index, IEnumerable<T> 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<T> comparison) { throw new NotSupportedException(); }
    new public void Sort(IComparer<T> comparer) { throw new NotSupportedException(); }
    new public void Sort(int index, int count, IComparer<T> 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];
    }
}

Код теста:

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

        Console.WriteLine("Item count in 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("Just enqueued: {0}", text);
        }

        Console.WriteLine();
        Console.WriteLine("Item count in ListQueue: {0}", queue.Count);
        Console.WriteLine();

        var peekText = queue.Peek();
        Console.WriteLine("Just peeked at: {0}", peekText);
        Console.WriteLine();

        var textToRemove = "Test5";
        queue.Remove(textToRemove);
        Console.WriteLine("Just removed: {0}", textToRemove);
        Console.WriteLine();

        var queueCount = queue.Count;
        for (int i = 0; i < queueCount; i++)
        {
            var text = queue.Dequeue();
            Console.WriteLine("Just dequeued: {0}", text);
        }

        Console.WriteLine();
        Console.WriteLine("Item count in ListQueue: {0}", queue.Count);

        Console.WriteLine();
        Console.WriteLine("Now try to ADD an item...should cause an exception.");
        queue.Add("shouldFail");

    }
}

Answer 3

Вот как вы удаляете определенный элемент из очереди с одной строкой Linq (это воссоздает очередь, НО из-за отсутствия лучшего метода ...)

//replace "<string>" with your actual underlying type
myqueue = new Queue<string>(myqueue.Where(s => s != itemToBeRemoved));

Я знаю, что он не удаляет по индексу , но все же кто-то может найти это полезным (этот вопрос оценивается в Google как "удалить определенный элемент из очереди ac #", поэтому я решил добавить этот ответ, извините )

Answer 4

Ответ довольно поздний, но я пишу его для будущих читателей

List<T> - это именно то, что вам нужно, но он имеет большой недостаток по сравнению с Queue<T>: он реализован с массивом, тогда Dequeue() довольно дорогой (с точки зрения времени), потому что все элементы должны быть сдвинуты на один шаг обратно с Array.Copy. Даже Queue<T> использует массив, но вместе с двумя индексами (для головы и хвоста).

В вашем случае вам также понадобится Remove / RemoveAt, и его производительность не будет хорошей (по той же причине: если вы не удаляете из хвоста списка, тогда должен быть выделен другой массив и скопированы элементы).

Лучшая структура данных для быстрого Dequeue / Remove времени - это связанный список (вы немного пожертвуете производительностью для Enqueue, но при условии, что ваша очередь имеет равное число Enqueue / Dequeue операций у вас будет большой прирост производительности, особенно когда его размер будет расти).

Давайте рассмотрим простой скелет для его реализации (я пропущу реализацию для IEnumerable<T>, IList<T> и других вспомогательных методов).

class LinkedQueue<T>
{
    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<T> _items = new LinkedList<T>();
}

Для быстрого сравнения:

           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) - это типичный случай, но иногда это будет O (n) (когда необходимо изменить размер внутреннего массива).

Конечно, вы заплатите что-то за то, что получаете: использование памяти больше (особенно для небольших T накладных расходов будет здорово). Правильная реализация (List<T> против LinkedList<T>) должна быть тщательно выбрана в соответствии с вашим сценарием использования, вы также можете преобразовать этот код в единый связанный список, чтобы уменьшить 50% накладных расходов памяти.

Answer 5

Кто-то, вероятно, разработает лучшее решение, но из того, что я вижу, вам нужно будет вернуть новый объект Queue в вашем методе Remove. Возможно, вы захотите проверить, не выходит ли индекс за границы, и я, возможно, неправильно упорядочил добавляемые элементы, но вот быстрый и грязный пример, который можно довольно легко превратить в расширение.

public class MyQueue<T> : Queue<T> {
    public MyQueue() 
        : base() {
        // Default constructor
    }

    public MyQueue(Int32 capacity)
        : base(capacity) {
        // Default constructor
    }

    /// <summary>
    /// Removes the item at the specified index and returns a new Queue
    /// </summary>
    public MyQueue<T> RemoveAt(Int32 index) {
        MyQueue<T> retVal = new MyQueue<T>(Count - 1);

        for (Int32 i = 0; i < this.Count - 1; i++) {
            if (i != index) {
                retVal.Enqueue(this.ElementAt(i));
            }
        }

        return retVal;
    }
}

Answer 6

Хотя встроенного способа нет, вы не должны использовать структуру List или другую структуру, IFF RemoveAt не частая операция.

Если вы обычно ставите в очередь и удаляете из очереди, но удаляете только время от времени, вы можете позволить себе перестроить очередь при удалении.

public static void Remove<T>(this Queue<T> queue, T itemToRemove) where T : class
{
    var list = queue.ToList(); //Needs to be copy, so we can clear the queue
    queue.Clear();
    foreach (var item in list)
    {
        if (item == itemToRemove)
            continue;

        queue.Enqueue(item);
    }
}

public static void RemoveAt<T>(this Queue<T> queue, int itemIndex) 
{
    var list = queue.ToList(); //Needs to be copy, so we can clear the queue
    queue.Clear();

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

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

Следующий подход может быть более эффективным, используя меньше памяти и, следовательно, меньше GC: * ​​1006 *

public static void RemoveAt<T>(this Queue<T> 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);
    }
}

Answer 7

Фактически, это наносит ущерб всей цели Очереди, и класс, который вы в конечном итоге придете, нарушит семантику FIFO.

Answer 8

Я не верю, что мы должны использовать List<T> для эмуляции очереди, для очереди операции enqueue и dequeue должны быть очень высокопроизводительными, чего не было бы при использовании List<T>. Однако для метода RemoveAt допустимо неисполнение, так как это не является основной целью Queue<T>.

Мой подход к реализации RemoveAt - это O (n), но очередь все еще поддерживает в основном O (1) очередь (иногда внутренний массив требует перераспределения, что делает операции O (n)) и всегда O (1) очереди .

Вот моя реализация RemoveAt(int) метода расширения для Queue<T>:

public static void RemoveAt<T>(this Queue<T> queue, int index)
{
    Contract.Requires(queue != null);
    Contract.Requires(index >= 0);
    Contract.Requires(index < queue.Count);

    var i = 0;

    // Move all the items before the one to remove to the back
    for (; i < index; ++i)
    {
        queue.MoveHeadToTail();
    }

    // Remove the item at the index
    queue.Dequeue();

    // Move all subsequent items to the tail end of the queue.
    var queueCount = queue.Count;
    for (; i < queueCount; ++i)
    {
        queue.MoveHeadToTail();
    }
}

Где MoveHeadToTail определяется следующим образом:

private static void MoveHeadToTail<T>(this Queue<T> queue)
{
    Contract.Requires(queue != null);

    var dequed = queue.Dequeue();
    queue.Enqueue(dequed);
}

Эта реализация также изменяет фактический Queue<T>, а не возвращает новый Queue<T> (который, я думаю, больше соответствует другим RemoveAt реализациям).

Answer 9

Если очередь используется для сохранения порядка элементов в коллекции, и если у вас не будет дубликатов, тогда SortedSet может быть тем, что вы ищете. SortedSet действует так же, как List<T>, но остается упорядоченным. Отлично подходит для таких вещей, как выпадающий список.

Answer 10

Решение Дэвида Андерсона , вероятно, лучшее, но имеет некоторые накладные расходы. Вы используете пользовательские объекты в очереди? если это так, добавьте логическое значение, как отмена

Проверьте у своих работников, которые обрабатывают очередь, установлен ли этот логический тип, и пропустите его.