How to implement a Stack in Java using Arrays and Linked-List

Posted on Updated on

Stack is a fundamental data structure which is extensively used in algorithm design. A Stack can be simply defined as Last In First Out (LIFO) data structure, i.e. the last element added at the top of the stack should be the first element to be removed from the stack. The push method inserts element at the top of the stack while pop method removes top element. In practice we don’t need to implement Stack as it is already available with JDK which is explained here. But, it is always better to have understanding of internal details and implementation of Stack.

There are two popular ways to implement Stack.

  1. Array Based Implementation.
  2. Linked List Implementation.

As per programming best practices we should always use Interface. So, created one interface stack that each of above implementation must implement and fulfil the contractual agreement.

Array Based Implementation

In array based implementation, elements are stored in array and variable top holds the index of top element. The initial size of array is 1. Whenever index of top reaches the maximum capacity of array, size of array will be doubled. In case of popping element from stack if index of top is less than half of the array size, capacity of array will be decremented to half of the current capacity.

Run the program

Output

Linked List Implementation

Now a days, much more complex algorithms are implemented using Stack and performance is always a big concern while implementing any algorithm and writing any program. The performance of array based implementation of Stack is not up to the mark as resizing the capacity of array at run time is extensive and time consuming task. To overcome this problem it is recommended to use Linked List for Stack implementation. This implementation creates a new node instance per addition, each storing supplied value and reference to following node. This links allow us to keep the stack intact and eventually traverse the entire collection. No additional memory requires as we creates a new node each time thus consume the space required per node.

Run the program

Output

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.