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

Ответ 1

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

Ответ 2

Объединение предложений casperOne и David Anderson на новый уровень. Следующий класс наследует от 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");

    }
}

Ответ 3

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

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

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

Ответ 4

Кто-то, вероятно, разработает лучшее решение, но из того, что я вижу, вам нужно будет вернуть новый объект 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;
    }
}

Ответ 5

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

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> vs LinkedList<T>) должна быть тщательно выбрана в соответствии с вашим сценарием использования, вы также можете преобразовать этот код для использования одного связанного списка, чтобы уменьшить 50% накладных расходов на память.

Ответ 6

На самом деле, это побеждает всю цель Queue, и класс, который вы в конечном итоге придумаете, полностью нарушит семантику FIFO.

Ответ 7

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

Ответ 8

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

Обратитесь к вашим работникам, которые обрабатывают очередь, если это логическое значение установлено, а затем пропустите его.

Ответ 9

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

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

Вот моя реализация метода расширения 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).

Ответ 10

Хотя нет встроенного способа, вы не должны использовать структуру 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) where T : class
{
    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]);
    }
}

Ответ 11

Обратите внимание, что в списке вы можете сделать процесс удаления более эффективным, если вы фактически не удаляете элемент, а просто "отмечаете" его как "удаленный". Да, вы должны добавить немного кода, чтобы иметь дело с тем, как вы это сделали, но выигрыш - это эффективность.

Как один пример - скажем, у вас есть List<string>. Тогда вы можете, например, просто установить этот конкретный элемент в null и сделать с ним.

Ответ 12

Класс очереди настолько трудно понять. Вместо этого используйте общий список.