Menu
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?
520
asked Aug 16 '18 20:08
The primary difference between Stack and Queue Data Structures is that Stack follows LIFO while Queue follows FIFO data structure type. LIFO refers to Last In First Out. It means that when we put data in a Stack, it processes the last entry first. Conversely, FIFO refers to First In First Out.
A stack is a linear data structure that follows the LIFO principle, which means that the element inserted first will be removed last. On the other hand, Queue is a linear data structure that follows the FIFO principle, which means that the added element will be removed first.
You can use an Array or a Linked List as the Storage structure to implement the Stack or the Queue pattern.
Stacks can be used to implement recursive solutions iteratively. Queues are useful when the ordering of the data matters as it preserves that ordering. For example, they're used for caching.
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.
120
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!
23
answered Oct 01 '22 03:10
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
