28

.NET フレームワーク (3.5) で説明されている汎用キュー クラスを使用したいのですが、キューから項目を削除するには Remove(int index) メソッドが必要です。拡張メソッドを使用してこの機能を実現できますか? 誰かが私を正しい方向に向けたいと思っていますか?

4

12 に答える 12

25

必要なのは、からアイテムを取得したいときにList<T>常に呼び出す場所です。他のすべては実際には同じです (を呼び出すと、 の最後に項目が追加されます)。RemoveAt(0)QueueAddQueue

于 2009-02-10T06:21:41.427 に答える
15

casperOne と David Anderson の両方の提案を次のレベルに組み合わせます。次のクラスは、List から継承し、3 つの Queue メソッド (Equeue、Dequeu、Peek) を追加しながら、FIFO の概念に有害なメソッドを非表示にします。

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

    }
}
于 2012-01-28T21:21:58.980 に答える
8

かなり遅い回答ですが、将来の読者のために書きます

List<T>はまさに必要なものですが、 と比較すると大きな欠点がありますQueue<T>。配列で実装されている場合Dequeue()、すべての項目を で 1 ステップ戻す必要があるため、(時間の点で) かなり拡張的Array.Copyです。配列もQueue<T>使用しますが、2 つのインデックス (ヘッドとテール用) と一緒に使用します。

あなたの場合、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>();
}

簡単な比較のために：

           キュー リスト LinkedList
エンキュー O(1)/O(n)* O(1)/O(n)* O(1)
デキュー O(1) O(n) O(1)
削除なし O(n) O(n)

* O(1) は典型的なケースですが、 O(n) になることもあります (内部配列のサイズを変更する必要がある場合)。

もちろん、得たものに対して何かを支払うことになります: メモリ使用量は大きくなります (特に小さなTオーバーヘッドの場合は素晴らしいでしょう)。正しい実装 ( List<T>vs LinkedList<T>) は、使用シナリオに応じて慎重に選択する必要があります。また、そのコードを変換して単一のリンク リストを使用し、メモリ オーバーヘッドを 50% 削減することもできます。

于 2014-07-03T12:12:19.143 に答える
7

おそらく誰かがより良い解決策を開発するでしょうが、私が見た限りでは、Remove メソッドで新しい Queue オブジェクトを返す必要があります。インデックスが範囲外であるかどうかを確認する必要があり、追加されるアイテムの順序が間違っている可能性がありますが、非常に簡単に拡張機能にすることができる簡単で汚い例を次に示します。

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;
    }
}
于 2009-02-10T06:06:53.193 に答える
2

コレクション内のアイテムの順序を保持するためにキューが使用されていて、重複するアイテムがない場合は、SortedSetが探しているものである可能性があります。のSortedSetように動作しList<T>ますが、順序付けられたままです。ドロップダウン選択などに最適です。

于 2012-03-26T18:27:28.447 に答える
2

実際、これはQueueの目的全体を無効にし、最終的に思い付くクラスはFIFOセマンティクスに完全に違反します。

于 2009-02-10T07:22:13.233 に答える
1

David Andersonのソリューションはおそらく最良ですが、いくらかのオーバーヘッドがあります。キューでカスタムオブジェクトを使用していますか？もしそうなら、キャンセルのようなブール値を追加します

そのブール値が設定されているかどうかをキューを処理するワーカーに確認してから、スキップしてください。

于 2009-02-10T08:37:58.790 に答える
-3

queue クラスを理解するのは非常に困難です。代わりに汎用リストを使用してください。

于 2011-11-09T02:42:37.257 に答える