How would you obtain the first and last items in a Queue?

Question

Say I have a rolling collection of values where I specify the size of the collection and any time a new value is added, any old values beyond this specified size are dropped off. Obviously (and I've tested this) the best type of collection to use for this behavior is a Queue:

myQueue.Enqueue(newValue)
If myQueue.Count > specifiedSize Then myQueue.Dequeue()

However, what if I want to calculate the difference between the first and last items in the Queue? Obviously I can't access the items by index. But to switch from a Queue to something implementing IList seems like overkill, as does writing a new Queue-like class. Right now I've got:

Dim firstValue As Integer = myQueue.Peek()
Dim lastValue As Integer = myQueue.ToArray()(myQueue.Count - 1)
Dim diff As Integer = lastValue - firstValue

That call to ToArray() bothers me, but a superior alternative isn't coming to me. Any suggestions?

Answer 1

One thing you could do is have a temporary variable that stores the value that was just enqueued because that will be the last value and so the variable can be accessed to get that value.

Answer 2

Your best bet would be to keep track of the last value added to the Queue, then use the myQueue.Peek() function to see the "first" (meaning next) item in the list without removing it.

Answer 3

You could use a deque (double-ended queue).

I don't think there is one built into System.Collections(.Generic) but here's some info on the data structure. If you implemented something like this you could just use PeekLeft() and PeekRight() to get the first and last values.

Of course, it will be up to you whether or not implementing your own deque is preferable to dealing with the unsexiness of ToArray(). :)

http://www.codeproject.com/KB/recipes/deque.aspx

Answer 4

Seems to me if you need quick access to the first item in the list, then you're using the wrong data structure. Switch a LinkedList instead, which conveniently has First and Last properties.

Be sure you only add and remove items to the linked list using AddLast and RemoveFirst to maintain the Queue property. To prevent yourself from inadvertantly violating the Queue property, consider creating a wrapper class around the linked list and exposing only the properties you need from your queue.

Answer 5

public class LastQ<T> : Queue<T>
{
    public T Last { get; private set; }

    public new void Enqueue(T item)
    {
         Last = item;
         base.Enqueue(item);
    }
}

Edit: Obviously this basic class should be more robust to do things like protect the Last property on an empty queue. But this should be enough for the basic idea.