CODEWITHSUNDEEP
c#collections
Jan Turoň
Jan Turoň

Reputation: 32912

How to find out if Queue contains last item at another position?

Let's have a Queue and an item which was enqueued last. What is the most efficient way to find out if the item is (not) at another position in the Queue?

The item can be remembered into another variable if it helps.

Upvotes: 0

Views: 555

Answers (2)

Jan Turoň
Jan Turoň

Reputation: 32912

I finally found it! I hope it helps someone else, too.

The better collection for this task is LinkedList

bool findNotLast<T>(T item, LinkedList<T> list) {
    return list.Count>1 && list.Find(item) != list.Last;
}

Upvotes: 0

BrokenGlass
BrokenGlass

Reputation: 160922

Just keep a HashSet<T> Dictionary<T,int> and keep count of your items this way - when you enqueue an item in the queue you increase the count for that item (or add it to the dictionary if not present yet) - you can just check using dictionary.ContainsKey() before adding the new item to see if the item was already added, or retrieve the count for the item (>=2 in this case after insertion) - this requires of course that the item have equality defined properly.

Likewise you would have to decrease the count of an item in the dictionary when you dequeue an item from the queue, and remove it once the count reaches zero.

This approach trades additional memory cost for O(1) lookup time.

Upvotes: 4

Related Questions