CODEWITHSUNDEEP
javadata-structuresstackqueuetime-complexity
Zoomba
Zoomba

Reputation: 1806

The reason for different implementation of Stack and Queue in Java?

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?

Upvotes: 6

Views: 1560

Answers (2)

Jacob G.
Jacob G.

Reputation: 29680

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.

Upvotes: 6

Jacob B.
Jacob B.

Reputation: 433

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!

Upvotes: 3

Related Questions