The stack data structure is a data structure which follows LIFO(Last in First out). A real-life example is the pile of books which are placed on top of one another, where the book on the top is the last placed and it would be the first one we can pick from the top.
In java we have the Stack class in util package and the following code can be used to understand its working. Some of the methods it provides are add, peek, push etc.
import java.util.Stack;
public class StackDemo {
public static void main(String[] args) {
Stack<Integer> stk = new Stack<>();
stk.add(5); // insert
stk.add(6);
stk.add(7);
stk.add(8);
while(!stk.isEmpty()){
System.out.println(stk.peek()); //access
stk.pop();// delete
}
}
}
output
8
7
6
5
Time complexity
Insert - O(n), Delete - O(n) Access - O(1)*,* Search - O(n)
DS => Data Structure
As we can see that this type of DS is useful when we want to access the data in constant time
let's see how can we implement this from scratch in java.
Before we start coding, let us look into the functionality we require, we require 4 functions we can name them however we want, but the most important thing to decide is which DS we need to store the values. we can use arrays, ArrayList, and LinkedList but as ArrayList is a dynamic array we can make use of its methods easily which are already implemented.
add() - Should add the value to an existing list
pop() - Should remove the last inserted value
peek() - Should give the last inserted value
isEmpty() - should give us the boolean value representing if the DS is empty or not
We would make use of generics of java so that the class can work on any type(Integer, String etc..)
Code
import java.util.ArrayList;
import java.util.List;
public class Stack<T> {
private List<T> list = new ArrayList<>();
public void add(T value){
list.add(value);
}
public void pop(){
list.remove(list.size() -1); //remove last inserted
}
public T peek(){
return list.get(list.size() -1); //get the last inserted
}
public boolean isEmpty(){
return list.size() -1 < 0;
}
public static void main(String[] args) {
Stack<Integer> stk = new Stack<>();
stk.add(5);
stk.add(6);
stk.add(7);
stk.add(8);
while(!stk.isEmpty()){
System.out.println(stk.peek());
stk.pop();
}
}
}
Follow me for more such articles
#RealEngineering #java #datastructures