Stack Basics

Stack data structure holds elements in LIFO (Last in, First out) order. This means elements are removed from a queue in the reverse order of the order in which they are added to the stack. In example below, integers 1,5,2,4 are added to the stack and them two integers are removed from stack:

•	Add 1, Stack contents:  1
•	Add 5, Stack contents: 5 <- 1
•	Add 2, Stack contents: 2 <- 5 <- 1
•	Add 4, Stack contents: 4 <- 2 <- 5 <- 1
•	Remove an integer, Stack contents:  2 <- 5 <- 1
•	Remove an integer, Stack contents: 5 <- 1

Use cases for Stacks

Algorithms requiring reversal of order.

Algorithms requiring backtracking.

History tracking.

Undo mechanisms, reverting to previous states.

In compilers to evaluate certain expressions, eg. Postfix, Prefix.

Time Complexity of Java Stack operations

Following table shows time complexity metrics for Stack operations:

Operation	Complexity
Add operation.	O(1)
Remove/Delete operation.	O(1)
Peek operation.	O(1)
Get size of Stack.	O(1)

Stack in Java JDK API.

Java provides Stack class, which provides the required stack behaviour.

Example code for instantiating Stack:

Stack stack=new Stack();

Now, we can use methods like push(), pop(), peek() on stack instance.

However, Java also recommends to use the Deque interface implementation as a Stack using addFirst()/ offerFirst(), removeFirst()/pollFirst() and peekFirst()/getFirst() methods

Example code for instantiating using Deque interface (LinkedList implementation) to be used as Stack:

Deque<Integer> stack=new LinkedList<Integer>();

Now we can perform operations like addFirst(), removeFirst(), getFirst() on stack instance.