Stack Data Structure

Question: What is stack ?

Ans: Stack is a Linear data structure , Operations in Stack is performed in LIFO order

 Stack: Stack is a Last in first out data structure [LIFO MODEL]

Stack is Linear data structure in which insertion and deletions are allowed only at the end,called the top of the stack.

As a stack is a Linear data structure , we can implement it using Array and LinkedList . bcse we know that Array and linkedlist is a linear data structure so can implement stack on Array and Linkedlist

Operations In Stacks: 

1) Push elements onto the stack or push Operation: Kisi cheej ko push karke stack ke sabse upar dal dena Push keh lata hai , Iski time complexity O(1) hoti hai.

2) Pop elements from the stack or pop Operations: To remove and return the top element from the stack, Stack ke top se element ko nikal lena Pop kehlata hai. Time Complexity O(1).

pop will remove last inserted elements from stack

Kisi bhi element ko stack se delete krne ko ham PoP bolte hai

3) Top/Peek at the top element or Peek Operations: To retrieve the top element without removing it, Stack ke sabse top ki, upr ki value ko nikalna use Peek kehte hai .Time Complexity O(1)

Top me kon si element rakhi hai ye wo batayega

4) is Empty() : It will help me to know stack is empty or not.

5) Size(): size of stacks

Question: Applications of stack ?

Ans: 1) Used in Function call

        2) Infix to postfix conversion

        3) Parenthesis matching and many more.

        4) Stack recursion me bhi use hota hai.

Problem statement

Given an empty Stack and we perform following functions on the stack:

1. push(5)
2. push(3)
3. push(4)
4. pop()
5 push(2)

What is the size of stack now?

Ans: 3;

Problem statement

What would be the sum of elements of Stack after performing following functions:

1. push(5)
2. push(3)
3. push(4)
4. pop()
5. push(2)

Ans: 10; because 4 will popped out, pop will remove top element then will add 5+3+2 = 10;

Problem statement
What should be the return type of size function in stack?
Ans: Int.

Time Complexity of Stack function's
Operations  
Complexity
push() 
O(1)
pop()   
O(1)
isEmpty() 
O(1)
size()
O(1)

Types of Stacks:

• Fixed Size Stack: As the name suggests, a fixed size stack has a fixed size and cannot grow or shrink dynamically. If the stack is full and an attempt is made to add an element to it, an overflow error occurs. If the stack is empty and an attempt is made to remove an element from it, an underflow error occurs.
• Dynamic Size Stack: A dynamic size stack can grow or shrink dynamically. When the stack is full, it automatically increases its size to accommodate the new element, and when the stack is empty, it decreases its size. This type of stack is implemented using a linked list, as it allows for easy resizing of the stack.

Implementation of Stacks

\

This is class for stack where will create Stack data

import javax.xml.transform.stream.StreamSource;
import java.sql.SQLOutput;
import java.util.LinkedList; // Corrected import statement with full package path


public class stackUsingArray {




    private int data[];  /// this is array type data
    private int top; //this is topmost element of Stack

    public stackUsingArray (){
        data = new int[10]; // this is 10 size array, by default will create 10 size array
        //if there is no any capacity or size given by user for array then
        //this constructor will help to create maximum 10 sizes array
        top = -1; // if there is no data in Array then top will be -1


    }

    public stackUsingArray(int capacity){  // if u want that, user should provide size of array
        //then on that condition it will help users to give size of array

        data = new int[capacity];
        top = -1;
    }

    public boolean isEmpty(){  // this is function
        if(top == -1){
            return true;
        }
        else {
            return false;
        }
    }

    public void push(int elem){
        top++;
        data[top] = elem;
    }



    // Getter method for top
    public int GetTop() {
        return data[top];
    }

}

>>> here I'm creating a another class where will use stack 

public class StackUseArray{




    public static void main(String[] args) {





    stackUsingArray stack = new stackUsingArray();  //this is object

        stack.push(18);   // this is element pushing code
        
//        stack is object and push ki method to push element 
        stack.push(34);
        System.out.print(stack.GetTop());   // for print stack will stack.GetTop 
        //top is  method to print stack , object name and getter function call



}
}

Note:

>>> top -1 isliye rkhte hai kyu ki initially element empty hota hai saath hi isEmpty -1 hoga to true return karega.

Question: Design a stack using Array In java and explain.

Ans:

First of all let me help u to know in stack using array we have around 5 different functions, that can help u to create a stack using Array..

1) isEmpty

2) size()

3)push

4)top

5)pop

>> as we know in stack using array we need 2 properties or member variable first is int data[] which is array type bcse we are creating a stack using array. if i talk about second instanse or member varible we need a top property.

public class stackUsingArray {

    private int data[];

    private int top;

}

>> here u can se I've created data[] array type and second is top but this is private so that no one can access these data member apart from this class   

Second:

//default constructor 
public stackUsingArray(){
    data = new int[10]; // this is 10 size array;
    top = -1;
    
}

>>here u can see I've created a constructor bcse if user not provide any capacity or size for the array then it will automatically allot size to array that is 10/it will automatically create 10 size array.

Third:

  //if user want to give specific size of array then this constructor will help to create

    stackUsingArray(int capacity){
        data = new int[capacity]; // capacity is for size of array
        top = -1; // top initially -1
        
    }
}

>> why top is -1 bcse initially in array there are no any stack available so top is basically index of array 

is -1 means nothing , there are no any data in stack array.

>> capacity is int type variable it will help users to provide size of array

forth:

Now I'm going to create isEmpty function --

isEmpty function will return true and false therefore return type of this function is boolean

boolean isEmpty(){
    if(top == -1){
        return true;
    }
    else {
        return false;
    }

}

in this function if top is -1 then it will return true means stack isEmpty

other wise return false;

as u can see here top is initially -1 means there is nothing , so it means isEmpty is true 

if top == -1 then it'll return true otherwise false .

Now I'm going to create a another functin name size()

>>so size means if top is in -1 then we need to return 0 size of stack/array , means if top is -1 then i want to return top+1 bcse after -1 > 0 so top -1+1 is size of stack in array

>>bcse it will return size thats why in this function return type will be int 

int size(){
        return top+1;

} 

Now I'm going to create push function

>>push function will return nothing so return type of this function is void 

>>before push anything we need to increment top position because top is initially in -1 position so before push anything will do top++ means top +1 then data ke [top] me element ko store kr denge . jaha data mera array ka name hai.

void push(int element) throws StackFullException{
    if(size() == data.length){
        StackFullException e = new StackFullException();
        throw e;

    }
        top++;
        data[top] = element;

}

>> yaha hamne if size == data.length then ek StackFullExecption ka class bnake use extends kiya hai execption ke class se jo ki java ki inbuilt class hoti uske kuch function ko use karke message de rhe agar size hamari data ke length ke barabar ho jayegi to message throw kar denge jisse exception aa jayega aur run time error nhi aayega , jisme StackFullException ka ek object bana rhe ham yaha stackUsingArray me banaye jiske function me throw karke StackFullException ko throws ke saath throw karenge aur if(size == data.length) throw e kar denge, otherwise top++ karke data[top] me element ko dal denge.

Now I'm going to create top function --

int top() throws StackEmptyException{
    if(size() == 0){
    StackEmptyException em = new StackEmptyException();
    throw em;
    }
    return data[top];
}

Now I'm going to use this stack class 

public class StackUse {
    public static void main(String[] args) {
        stackUsingArray stack = new stackUsingArray(8);

        for (int i = 0; i <= 10; i++) {
            try {
                stack.push(i);
            } catch (StackFullException e) {
                System.out.println("Stack is full. Cannot push element: " + i);
            }
        }

        try {
            System.out.println(stack.top());
        } catch (StackEmptyException e) {
            System.out.println("Stack is empty. Cannot get top element.");
        }
    }
}

try catch ek block hai jisme try me ham operation likhte hai jo krna hai aur catch hamara exception ko catch karega