Performance difference between arrays, stacks and queues

Question

What is the search performance of arrays, stacks and queues?

I think that arrays are the quickest and most straightforward, because I can access any element immediately by calling it using its index. Is this correct? What about the performance of stacks and queues? How do they compare?

Answer 1

Arrays (and collections based on arrays, eg. ArrayList) are bad for search performance because in the worst case you end up comparing every item (O(n)). But if you don't mind modifying the order of your elements, you could sort the array (Arrays.sort(yourArray)) then use Arrays.binarySearch(yourArray, element) on it, which provides a O(log n) performance profile (much better that O(n)).

Stacks are in O(n), so nope.

Queues are not even meant to be iterated on, so looking for an object in here would mean consuming the whole queue, which is 1. not performant (O(n)) and 2. probably not what you want.

So among the datastructures you suggested, I would go for a sorted array.

Now, if you don't mind considering other datastructures, you really should take a look at those who use hash functions (HashSet, HashMap...). Hash functions are really good at searching for elements, with a performance profile in O(1) (with a good hashcode() method in your objects).

Answer 2

I'll try to answer in a very simple way.

Stacks and queues are for storing data temporarily so that you can process the contents one by one. Just like a queue for buying movie tickets, or a stack of pancakes, you process one element at a time.

Arrays are for storing data as well as for accessing elements from the beginning, the end or in between. For searching, arrays would be a better choice.

Can you search elements inside stacks and queues? Possibly. But that's not what they are used for.