Performance difference between arrays, stacks and queues
Arrays (and array based collections, for example ArrayList
) are bad for search performance because in the worst case, you are comparing each element ( O(n)
). But if you don't mind changing the order of your elements, you can sort the array ( Arrays.sort(yourArray)
) and then use Arrays.binarySearch(yourArray, element)
on it that provides a performance profile O(log n)
(much better than O(n)
).
The stacks are in O(n)
, so no.
Queues are not even meant to be iterated over, so looking for an object here means consuming the entire queue, which is not efficient ( O(n)
) and 2. This is probably not what you want.
So, among the data structures you suggest, I would choose a sorted array.
Now, if you don't mind other data structures, you should really take a look at those using hash functions ( HashSet
, HashMap
...). Hash functions are really good at finding items, with a performance profile in O(1)
(with a good hashcode()
method in your objects).
source to share
I will try to answer in a very simple way.
Stacks and queues are for temporary storage of data, so you can process content one at a time. Just like a queue for movie tickets or a stack of pancakes, you process one item at a time.
Arrays are for storing data and also for accessing elements from the beginning, end, or between them. It would be better to use arrays for searching.
Can you search for items within stacks and queues? Maybe. But that's not what they are used for.
source to share
In Java, you have ArrayList
(built on array), Stack
(built on array) and ArrayQueue
and ArrayDeque (which is also built on array). Since they all use the same underlying data structure, their access speeds are mostly the same.
For brute force searches, the time to scan or iterate over them (they all support iteration) is O (n) Btw, even HashMap uses an array to store records, so iterating over its elements to find the value, for example containsValue
also O (n).
While you can have a sorted array that will sit more naturally in the ArrayList, you can also argue that the PriorityQueue will find and remove the next element most efficiently. Stack is perfect for finding the last added item.
To answer a question, you must determine what assumption the person asking the question is making. Without this assumption, you would have to say that they can all be used. In this case, I would use ArrayList as it is the easiest to understand IMHO.
source to share