CODEWITHSUNDEEP
.netlinqqueueienumerablepeek
user3685285
user3685285

Reputation: 6606

How efficient is IEnumerable.First and IEnumerable.Last?

I want to use a System.Collections.Generic.Queue, but with one difference: I want Queue.Peek to return the last item put in rather than the first. I still want items to enter and exit in the same manner.

I was thinking of using Queue.Last() as an alternative to Queue.Peek() (which I assume is basically the same as Queue.First()) But I'm wondering if this means an enumerator will literally enumerator over the entire queue before reaching the last element. Since my queues will be very large, this can be a problem.

EDIT:

To put into perspective what I'm trying to do: Say I want to keep a minute by minute database of the price of a stock for the last 20 years. This would be many data points. In order to do this, I would like to enqueue the lastest price at every minute, and dequeue the earliest price when the size of the queue gets above 20 years. However, I also want a convenient way to get the most recent price from the queue. I know about Queue.Last(), which will do the trick, but I just want to know if it will be terribly inefficient.

Upvotes: 0

Views: 478

Answers (3)

Alex
Alex

Reputation: 13234

It sounds like you don't want to use a queue but a deque.

Doing a Last call will create an Enumerator instance, a private internal class for Queue<T> that will be used to enumerate start to end, because Queue<T> does not implement the IList<T> interface. Thus Last would be an O(n) operation.

Upvotes: 1

Theodoros Chatzigiannakis
Theodoros Chatzigiannakis

Reputation: 29223

If the collection implements IList<T>, then the indexer property is used in both First() and Last() (which is usually O(1), though it's not required to be).

Otherwise, a call to First() will only take the first element (and exit immediately, if the enumerator supports deferred execution), but a call to Last() will have to enumerate the whole collection.

IQueue<T> does not implement IList<T>.

Upvotes: 2

roomaroo
roomaroo

Reputation: 5871

You're right - for Queues, Last will iterate over every element. Enumerable.Last has a shortcut for ILists, but not for Queues.

It sounds like you just want a queue that remembers the last item added. You could just create a simple wrapper around Queue that can efficiently return the last item...

public class StockQueue<T>
{
    private readonly queue; 

    public StockQueue(Queue<T> source)
    {
        this.queue = source;
    }

    public T LastAdded {get; private set;}

    public Enqueue(T item)
    {
        // Remember the last item added
        this.lastAdded = item;
        this.queue.Enqueue(item);
    }

    // Implement any other Queue members you need, passing the calls through
    // to the internal queue.
    public T Dequeue()
    {
        return this.queue.Dequeue();
    }

    public T Peek()
    {
        return this.queue.Peek();
    }
}

Upvotes: 0

Related Questions