Ответ 1
Вы хотите List<T>, где вы всегда вызываете RemoveAt(0), когда вы хотите получить элемент из Queue. Все остальное одно и то же, действительно (вызов Add добавит элемент в конец Queue).
С# Добавление метода Remove (int index) к классу .NET Queue
Я хотел бы использовать общий класс очереди, как описано в .NET framework (3.5) но мне понадобится метод Remove (int index) для удаления элементов из очереди. Могу ли я реализовать эту функцию с помощью метода расширения? Кто-нибудь хочет указать мне в правильном направлении?
Ответы
Ответ 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
Класс очереди настолько трудно понять. Вместо этого используйте общий список.