6

我需要一个数据结构，它是一种特殊类型的队列。我想要这样，如果我的队列的一个实例曾经包含一个对象 X，那么在这个实例中应该不可能再次将 X 加入队列。如果用 X 调用，入队方法应该什么都不做，比如尝试向 HashSet 添加重复值。

示例用法：

MyQueue<int> queue = new MyQueue<int>(); 
queue.Enqueue(5); 
queue.Enqueue(17); 
queue.Enqueue(28); 
queue.Enqueue(17); 
int firstNumber = queue.Dequeue(); 
queue.Enqueue(5); 
queue.Enqueue(3); 

List<int> queueContents = queue.ToList(); //this list should contain {17, 28, 3}

我在 MSDN 上四处寻找，但找不到这样的课程。它是否存在，或者我必须自己实现它？

我想我也可以使用不同的数据结构，但访问总是先进先出，所以我认为队列将是最有效的。另外，我不知道有任何其他结构可以提供这种“实例生命周期的唯一性”功能。

4

4 回答 4

5

你必须自己实现。

一个想法是在将元素加入HashSet队列时将其添加到 a 中。

然后，当您要入队时，只需检查该HashSet项目，如果它存在，请不要入队。

由于您想防止在队列的剩余生命周期内排队，您可能不想从HashSet.

于 2013-11-13T14:28:51.560 回答
5

我会做类似的事情：

class UniqueQueue<T>
{
    private readonly Queue<T> queue = new Queue<T>();
    private HashSet<T> alreadyAdded = new HashSet<T>();

    public virtual void Enqueue(T item)
    {
        if (alreadyAdded.Add(item)) { queue.Enqueue(item); }
    }
    public int Count { get { return queue.Count; } }

    public virtual T Dequeue()
    {
        T item = queue.Dequeue();
        return item;
    }
}

请注意，大部分代码都是从This Thread借来的。

于 2013-11-13T14:34:51.763 回答
4

这只是韦恩答案的扩展版本，只是更加充实并支持更多接口。（模仿Queue<T>的界面）

sealed class UniqueQueue<T> : IEnumerable<T>, ICollection, IEnumerable
{
    private readonly Queue<T> queue;
    private readonly HashSet<T> alreadyAdded;

    public UniqueQueue(IEqualityComparer<T> comparer)
    {
        queue = new Queue<T>();
        alreadyAdded = new HashSet<T>(comparer);
    }

    public UniqueQueue(IEnumerable<T> collection, IEqualityComparer<T> comparer)
    {
        //Do this so the enumeration does not happen twice in case the enumerator behaves differently each enumeration.
        var localCopy = collection.ToList();

        queue = new Queue<T>(localCopy);
        alreadyAdded = new HashSet<T>(localCopy, comparer);
    }

    public UniqueQueue(int capacity, IEqualityComparer<T> comparer)
    {
        queue = new Queue<T>(capacity);
        alreadyAdded = new HashSet<T>(comparer);
    }

    //Here are the constructors that use the default comparer. By passing null in for the comparer it will just use the default one for the type.
    public UniqueQueue() : this((IEqualityComparer<T>) null) { }
    public UniqueQueue(IEnumerable<T> collection) : this(collection, null) { }
    public UniqueQueue(int capacity) : this(capacity, null) { }

    /// <summary>
    /// Attempts to enqueue a object, returns false if the object was ever added to the queue in the past.
    /// </summary>
    /// <param name="item">The item to enqueue</param>
    /// <returns>True if the object was successfully added, false if it was not</returns>
    public bool Enqueue(T item)
    {
        if (!alreadyAdded.Add(item))
            return false;

        queue.Enqueue(item);
        return true;
    }

    public int Count
    {
        get { return queue.Count; }
    }

    public T Dequeue()
    {
        return queue.Dequeue();
    }

    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    {
        return ((IEnumerable<T>)queue).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return ((IEnumerable)queue).GetEnumerator();
    }

    void ICollection.CopyTo(Array array, int index)
    {
        ((ICollection)queue).CopyTo(array, index);
    }

    bool ICollection.IsSynchronized
    {
        get { return ((ICollection)queue).IsSynchronized; }
    }

    object ICollection.SyncRoot
    {
        get { return ((ICollection)queue).SyncRoot; }
    }
}
于 2013-11-13T15:37:25.000 回答
0

您可以使用基本队列，但修改 Enqueue 方法以验证先前输入的值。在这里，我使用了一个哈希集来包含那些以前的值：

public class UniqueValueQueue<T> : Queue<T>
{
    private readonly HashSet<T> pastValues = new HashSet<T>();

    public new void Enqueue(T item)
    {
        if (!pastValues.Contains(item))
        {
            pastValues.Add(item);

            base.Enqueue(item);
        }
    }
}

用你的测试用例

UniqueValueQueue<int> queue = new UniqueValueQueue<int>();
queue.Enqueue(5);
queue.Enqueue(17);
queue.Enqueue(28);
queue.Enqueue(17);
int firstNumber = queue.Dequeue();
queue.Enqueue(5);
queue.Enqueue(3);

List<int> queueContents = queue.ToList();

queueContents 包含 17、28 和 3。

于 2013-11-13T14:44:56.203 回答