Performance difference between arrays, stacks and queues

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

I think arrays are the fastest and simplest because I can access any element at once by calling it using my index. It's right? How about the performance of stacks and queues? How do they compare?


source to share

4 answers

It depends on how the search is done (or the search algorithm). Stack

or Queue

may also be useful for some applications of search, such as - BFS


. But in the usual case when you are using linear search, you might consider an array or ArrayList




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).



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.



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.



All Articles