Я использовал тот же подход, что и Крис Уэнам. Под нагрузкой снижается производительность, потому что новые NotifyCollectionChangedEventArgs должны быть выделены для каждого Enqueue / Dequeue.
Независимо от этого, в Enqueue отправьте аргументы с NotifyCollectionChangedAction.Add, добавленным элементом и Count-1 в качестве индекса. В очереди отправьте аргументы с помощью NotifyCollectionChangedAction.Remove, элемент будет удален и индекс 0.