Stack is one of the basic data structure which Implements ordering principle LIFO or last-in first-out. In real life we can meet this principle in magazines:

Shooting begins with the bullet that was loaded last. Or if you don’t like guns here is another good example of LIFO:

On the example above, if you want to reach the green ring you need to get the red ring first and then get yellow ring. The most obvious example of the stack in java is stack of method calls. In which, the last executed method will be on the top of the stack.

Operations with stack

To manage the stack there are two basic operations:

1. Push – adds new element to the top of the stack.
2. Pop – removes top element of the stack and previous element becomes top.

Furthermore, there are such operations as “peek” which returns top element but not removes it or “is empty” which checks whether the stack is empty.

Implementation

Stack can be implemented using either Array or linked list. The most easiest implementation of the stack uses linked list:

https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/ds/impl/LinkedListStack.java

Another approach uses Array to implement stack:

https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/ds/impl/ArrayStack.java

Both approaches have its own advantages and disadvantages. For instance, for array based stack you don’t need to create additional class to hold linked list structure. For linked list based stack you don’t have to set capacity of the stack.

Complexity

All operations with stack take linear time.