c#将Remove(int index)方法添加到.NET Queue类

我想使用.NET框架(3.5)中描述的通用队列类,但我需要一个Remove(int index)方法来从队列中删除项目.我可以使用扩展方法实现此功能吗？有人关心我指向正确的方向吗？

1> casperOne..：

---

你想要的是你想要从中获取物品时List总是打电话的地方.其他一切都是一样的,真​​的(调用会添加一个项目到最后).RemoveAt(0)QueueAddQueue

---

这样做的缺点是使'Dequeue`s O(n)代替O(1)

---

@CodeInChaos:当然,如果你使用的是Queue,那么假设你首先不需要随机访问.它似乎是错误的数据结构.

2> 小智..：

---

将casperOne和David Anderson的建议结合到一个新的水平.以下类继承自List并隐藏了在添加三个Queue方法(Equeue,Dequeu,Peek)时对FIFO概念有害的方法.

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];
    }
}

测试代码:

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

        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> Alex..：

---

以下是如何使用一行Linq从队列中删除特定项目(它正在重新创建队列,但缺少更好的方法......)

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

我知道它不是通过索引删除,但仍然有人可能会觉得这很有用(这个问题在Google中排名"从ac#queue中删除特定项目"所以我决定添加这个答案,抱歉)

4> David Anders..：

---

有人可能会开发出更好的解决方案,但从我看到你需要在Remove方法中返回一个新的Queue对象.你需要检查索引是否超出范围,我可能已经错误地添加了项目的顺序,但这是一个快速而肮脏的例子,可以很容易地成为扩展.

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

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

    /// 

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

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

        return retVal;
    }
}

---

你*不得*在RemoveAt中调用ElementAt.您已经将O(n)操作复制队列(已经很糟糕)更改为O(n ^ 2)操作,因为ElementAt遍历所有元素直到传递的索引,以找到它的元素 - 每次迭代时*循环*.最好使用foreach并在O(n)时间内通过循环计数器跳过违规元素.

5> Adriano Repe..：

---

这是一个很晚的答案,但我为未来的读者写了它

List正是你所需要的,但与以下相比它有一个很大的缺点Queue:它用数组实现然后Dequeue()非常广泛(就时间而言)因为所有项目都必须向后移动一步Array.Copy.甚至Queue使用数组但与两个索引(头部和尾部)一起使用.

在你的情况下你也需要Remove/ RemoveAt并且它的性能不会很好(出于同样的原因:如果你没有从列表尾部删除那么必须分配另一个数组并复制项目).

一个更好的数据结构,有快速Dequeue/ Remove时间是一个链表(你会牺牲 - 一点点 - 性能,Enqueue但假设你的队列具有相同数量的Enqueue/ Dequeue操作,你会有很大的性能提升,特别是当它的大小会增长).

让我们看一下它的实现的简单框架(我将跳过实现IEnumerable,IList以及其他帮助器方法).

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();
}

为了快速比较:

           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开销会很好).必须根据您的使用场景仔细选择正确的实现(Listvs LinkedList),您也可以将该代码转换为使用单个链表来减少50%的内存开销.

6> Todd..：

---

尽管没有内置方法，但您不应使用List结构或其他结构，IFF RemoveAt并不是经常使用的操作。

如果您通常在排队和出队，但只是偶尔删除，则删除时应该能够进行队列重建。

public static void Remove(this Queue 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(this Queue 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：

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);
    }
}