FixedSizedQueue.cs

using System.Collections;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Collections.Specialized;

public class FixedSizedQueue<T> : IEnumerable<T>, INotifyCollectionChanged
{
    readonly ConcurrentQueue<T> _innerQueue = new ConcurrentQueue<T>();
    public FixedSizedQueue(int size)
    {
        Size = size;
    }

    public event NotifyCollectionChangedEventHandler CollectionChanged;
    public int Size { get; set; }
    public IEnumerator<T> GetEnumerator()
    {
        return _innerQueue.GetEnumerator();
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    public void Enqueue(T item)
    {
        _innerQueue.Enqueue(item);
        OnCollectionChanged(new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Add, item));
        if (_innerQueue.Count > Size)
        {
            lock (this)
            {
                T overflow;
                while (_innerQueue.Count > Size && _innerQueue.TryDequeue(out overflow))
                {
                    OnCollectionChanged(new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Remove, overflow));
                }
            }
        }
    }
    protected virtual void OnCollectionChanged(NotifyCollectionChangedEventArgs e)
    {
        var handler = CollectionChanged;
        if (handler != null)
        {
            handler(this, e);
        }
    }
}

FixedSizedQueueTests.cs

using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using Common;
using NUnit.Framework;

public class FixedSizedQueueTests
{
    [Test]
    public void FixedSizedQueue()
    {
        var args = new List<NotifyCollectionChangedEventArgs>();
        var queue = new FixedSizedQueue<int>(2);
        queue.CollectionChanged += (_, e) => args.Add(e);
        queue.Enqueue(0);
        CollectionAssert.AreEqual(new[] { 0 }, queue);
        CollectionAssert.AreEqual(new[] { 0 }, args.SelectMany(x => x.NewItems.Cast<int>()));
        CollectionAssert.AreEqual(new[] { NotifyCollectionChangedAction.Add }, args.Select(x => x.Action));

        queue.Enqueue(1);
        CollectionAssert.AreEqual(new[] { 0, 1 }, queue);
        CollectionAssert.AreEqual(new[] { 0, 1 }, args.SelectMany(x => x.NewItems.Cast<int>()));
        CollectionAssert.AreEqual(new[] { NotifyCollectionChangedAction.Add, NotifyCollectionChangedAction.Add }, args.Select(x => x.Action));

        queue.Enqueue(2);
        CollectionAssert.AreEqual(new[] { 1, 2 }, queue);
        CollectionAssert.AreEqual(new[] { 0, 1, 2 }, args.Where(x => x.NewItems != null).SelectMany(x => x.NewItems.Cast<int>()));
        CollectionAssert.AreEqual(new[] { 0 }, args.Where(x => x.OldItems != null).SelectMany(x => x.OldItems.Cast<int>()));
        CollectionAssert.AreEqual(new[] { NotifyCollectionChangedAction.Add, NotifyCollectionChangedAction.Add, NotifyCollectionChangedAction.Add, NotifyCollectionChangedAction.Remove }, args.Select(x => x.Action));
    }
}