What is the difference between Array Stack , Linked Stack , and Stack

Question

Recently im studying Stack, Bag, and Queue. A question came out of my mind while im reading note from class.

what is the difference between Array and Linked? Why we can't just use Stack?

Stack<String> stack = new Stack<String>()
Stack<String> stack = new ArrayStack<String>()

These two i think they do the same thing, they can peek , pop , and remove

I don't get it that why we need to implement array or linked

Answer 1

Basically, it's to do with performance. A 'stack' is just an interface - it's a way of getting at the data for viewing and modification through some set of commands. However, this tells is nothing about how that data is stored in the structure - that's where stuff like ArrayStack and LinkedStack become important.

Essentially, each of these stacks is 'backed' by some more primitive structure - this is the bit behind the scenes that actually stores the data that we put in it. In the case of the ArrayStack, this is an array - in the case of the LinkedStack, this is a linked list.

So what's the difference? Well, consider the array. Arrays must use contiguous memory - namely, the whole array has to be given a block in memory which is one long uninterrupted chunk. On the other hand, a linked list consists of individual nodes linked by pointers - there is no requirement that it be contiguous at all. This makes resizing arrays problematic - essentially, we have to make a new array, and copy everything into it to resize it. This can be a problem with stacks, as we often have no idea precisely how large the stack will get. Linked lists don't have this problem - we just create a new node and link it to the list as it was before.

Thus, overall, the difference is memory use and performance - try implementing both and timing how they work with big data to see the difference.

Answer 2

Any of the data structures is used depending on what you you want to do. Each of the different data structures has different performances for different scenarios. For more information, read more about them on Wikipedia

Answer 3

The operations and functionality is the same no matter the implementation. You choose to use the array or the linked type for performance improvements.

Performance details are answered here in much more detail: Array-Based vs List-Based Stacks and Queues

Answer 4

LinkedStack is stored in linked nodes.It represents a last-in-first-out (LIFO).It supports the usual push and pop operations, along with methods for peeking at the top item, testing if the stack is empty, and iterating through the items in LIFO order.

ArrayStack represents an array implementation of a stack.It is an array implementation base of iStack. Its growth factor is 2 and starting size of 150.

Stack It extends class Vector with five operations that allow a vector to be treated as a stack.The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.

For more details visit Array-Based vs List-Based Stacks and Queues

Answer 5

Stack is part of the Java JDK (see JavaDoc). ArrayStack and LinkedStack aren't part of the standard JDK. Just relying on the names, they will be backed by an Array or an linked list instead of being based on Vector.