Stack implementation and all operations on stack using Array

 Click Me
Example of stack implementation - back button of the browser
_____________________________________
public class Main {
    // The Array used to implement stack
    int[] arr;
    // topOfStack is used to maintain the index of the topmost element present in stack. If not present then it will store -1
    int topOfStack;
 
    // constructor
    Main(int size){
        this.arr = new int[size];
        this.topOfStack=-1;
    }
 
    // used to initialize the array for stack
    // Time Complexity - O(n), Space Complexity - O(n)
    public void initializeArray(){
        if(topOfStack==-1){
            for(int i=0;i<this.arr.length;i++){
                this.arr[i]=Integer.MIN_VALUE;
            }
        }
    }
 
    // function to push element to top of stack
    // Time Complexity - O(1), Space Complexity - O(1)
    public void push(int value){
        // check if there is stack present or not
        if(this.arr==null){
            System.out.println("No stack present, first create a stack");
            return;
        }
        // check if stack is full or not
        if(this.topOfStack==(this.arr.length-1)){
            System.out.println("Stack is full, Can't push into stack");
            return;
        }
        // if stack is empty
        this.topOfStack++;
        this.arr[this.topOfStack]=value;
    }
 
    // function to pop an element from the top of stack
    // Time Complexity - O(1), Space Complexity - O(1)
    public void pop(){
        // check if there is any stack present or not
        if(this.arr==null){
            System.out.println("No stack present, first create a stack");
            return;
        }
        // check if stack is empty
        if(this.topOfStack==-1){
            System.out.println("Stack is empty, can't pop from stack");
            return;
        }
        // if stack is not empty
        this.arr[this.topOfStack]=Integer.MIN_VALUE;
        this.topOfStack--;
    }
 
    // function to see the topmost element of stack
    // Time Complexity - O(1), Space Complexity - O(1)
    public void peek(){
        // check if there is any stack present or not
        if(this.arr==null){
            System.out.println("No stack present, first create a stack");
            return;
        }
        // check if stack is empty
        if(topOfStack==-1){
            System.out.println("Stack is empty, can't peek");
            return;
        }
        // if stack is not empty
        System.out.println("Top of the stack: "+this.arr[this.topOfStack]);
    }
 
    // function to traverse the stack array
    // Time Complexity - O(n), Space Complexity - O(1)
    public void traverseStack(){
        // check if there is any stack present or not
        if(this.arr==null){
            System.out.println("No stack present, first create a stack");
            return;
        }
        // check if stack is empty
        if(this.topOfStack==-1){
            System.out.println("Stack is empty, can't traverse");
            return;
        }
        // if stack is not empty
        System.out.println("Printing stack...");
        for(int i=0;i<=this.topOfStack;i++){
            System.out.print(this.arr[i]+" ");
        }
        System.out.println();
    }
 
    // function to delete whole stack
    // Time Complexity - O(1), Space Complexity - O(1)
    public void deleteStack(){
        // check if there is any stack present or not
        if(this.arr==null){
            System.out.println("No stack present, first create a stack");
            return;
        }
        // if stack is present
        topOfStack=-1;
        arr=null;
        System.out.println("Stack deleted successfully");
    }
 
    public static void main(String[] args) throws Exception {
        Main stack = new Main(5);
        stack.initializeArray();
        stack.peek();
        stack.pop();
        stack.traverseStack();
        stack.push(1);
        stack.traverseStack();
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(2);
        stack.push(6);
        stack.traverseStack();
        stack.pop();
        stack.traverseStack();
        stack.peek();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.traverseStack();
        stack.deleteStack();
        stack.push(1);
        stack.traverseStack();
    }

}

Output:

Stack is empty, can't peek
Stack is empty, can't pop from stack
Stack is empty, can't traverse
Printing stack...
1 
Stack is full, Can't push into stack
Printing stack...
1 2 3 4 2 
Printing stack...
1 2 3 4 
Top of the stack: 4
Stack is empty, can't pop from stack
Stack is empty, can't traverse
Stack deleted successfully
No stack present, first create a stack
No stack present, first create a stack

Comments

Post a Comment

Popular posts from this blog

Binary Heap - Introduction

Image
#Image Credit - GeeksForGeeks Types of heap: Min Heap - every node is less than or equal to  its children(s) Max Heap - every node is more than or equal to its children(s) Operations on any heap : create insert extract/delete - we can extract/delete only the top node in any heap traverse delete entire heap get size of heap peek top of heap We should prefer implementing binary heap using arrays and not linked list, as during bottom to top heapify, in reaching the bottom rightmost node we take only 0(1) time in case of array but we take 0(n) time in case of linked list because first, we need to level order traverse the binary heap tree to get bottom-most rightmost element.  Heaps are used to efficiently implement:  Prim's Algorithm Heapsort Priority queue
Read more

Divide and Conquer - Introduction

Image
What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can br...
Read more

Bubble Sort

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array     ...
Read more