6

Stack has been implemented with a resizable array (Vector) in Java. However, to my understanding, although you have a choice, a Queue is usually instantiated with a LinkedList for common applications.

I know that theoretically they support all of their operations in O(1) worst-case or amortized. However, is there a specific reason that a resizable array is more suited for stacks while a linked list is more suitable for queue?

In other words, why don't they both use resizable arrays, or linked lists?

A. Mashreghi
  • 1,729
  • 2
  • 20
  • 33
  • Also see https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist. The common recommendation that I've seen is that there's almost never a reason to use a linked list, but there are some people arguing otherwise. (And of the people arguing otherwise, their reasons are unrelated to asymptotic analysis, and aren't specific to lists.) – Radiodef Aug 16 '18 at 21:19

2 Answers2

6

I know that theoretically they support all of their operations in O(1) worst-case or amortized.

You seem to be mistaken, as Stack#search is an O(n) operation.

... while a linked list is more suitable for queue?

A LinkedList is unlikely to be optimal when used as a Queue, as explained by the documentation of ArrayDeque:

[ArrayDeque] is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

In other words, why don't they both use resizable arrays, or linked lists?

Because Stack is an outdated class that should not be used, as specified by its documentation:

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

Jacob G.
  • 28,856
  • 5
  • 62
  • 116
3

Stacks are called such because they “stack.” One object over the other. Iteration over these stacked objects needs to be fat, stacks are usually meant to be built to be read and written quickly. ArrayLists (or resizable arrays) use a single dynamic array to store data. Adding new content to the array isn’t the fastest thing ever, but because it is a single array, read and write speeds are better.

Queues are simply strings of data queued one after the other. Regardless, queues are usually growing constantly. Think of a music queue, songs are being added on multiple times. The read of the music, however, is pretty basic, so read and write doesn’t need to take as much time. LinkedLists operate using a double linked list, which allows for faster add/remove times, but slower read write times.

Hope this answers your question. Cheers!

Jacob B.
  • 423
  • 3
  • 12
  • 1
    "Iteration over these stacked objects is faster when they are stored together in memory, which is why using a resizable array is good for that." - Java's heap memory has no obligation to be contiguous. – Jacob G. Aug 16 '18 at 21:08
  • 1
    @JacobG. Thanks for that pointer, my mind started running in C for a second. My bad – Jacob B. Aug 16 '18 at 21:15