DSA Day 53/100

Topic: Stack

Questions Successfully Completed: 3

1) Implement Stack using Linked List	Easy
2) Parenthesis Checker with Stack Implementation	Easy
3) Parenthesis Checker Optimized without Stack Implementation	Easy

Implement Stack using Linked List

package stack;
/* OPERATIONS

 * push
 * pop
 * peek

 * */

class StackLLNode{
    int data;
    StackLLNode next;

    StackLLNode(int data){
        this.data = data;
        this.next = null;
    }
}

public class implementStackusingLinkedList {

    // create stack class object to access its members
    static StackLLNode top = null;
    static int count = 0;

    static void push(int x){
        // if stack full then dont push
        StackLLNode newNode = new StackLLNode(x);
        if(newNode==null){
            System.out.println("Stack is full");
        }
        else{
            newNode.next = top;
            top = newNode;
        }
    }

    static int pop(){
        // if stack is empty dont pop element
        int result =-1;
        if(top==null){
            System.out.println("Stack is empty");
        }
        else{
            StackLLNode temp = top;
            result = temp.data;
            top = top.next;
        }
        count--;
        return result;
    }

    static int peek(int position){
        int reCount = count;
        StackLLNode ref = top;
        while(reCount-1>0){
            reCount--;
            ref=ref.next;
        }
        return ref.data;
    }


    static void display(StackLLNode head){
        while(head!=null){
            System.out.println(head.data + " | ");
            head=head.next;
            count++;
        }
    }

    public static void main(String[] args) {
            push(40);
            push(50);
            push(60);
            push(70);
            System.out.println("**** This is original Stack ****");
            display(top);
            System.out.println("**** poped up element is **** \n" + pop());
            System.out.println("**** Element at first position is ****\n" + peek(1));
    }
}

/*OUTPUT

**** This is original Stack ****
70 |
60 |
50 |
40 |
**** poped up element is ****
70
**** Element at first position is ****
40

*/

Parenthesis Checker with Stack Implementation

// Implemented Stack using array
package stack;
class PStack{
    int size;
    int top;
    char[] a;
}
public class parenthesisChecker {
    static PStack stack = new PStack();
    static int newCount = 0;

    static void createStack(String x){
        stack.size = x.length();
        stack.top = -1;
        stack.a = new char[stack.size];
    }

    static void push(char data){
        if(stack.top!=stack.size-1){
            stack.top++;
            stack.a[stack.top] = data;
            newCount++;
        }
        // if stack is full
        else{
            System.out.println("StackOverflow");
        }
    }
    static char pop(){
        char poped = ' ';
        // if stack empty
        if(stack.top==-1){
            System.out.println("Stack Underflow");
        }
        else{
            poped = stack.a[stack.top];
            stack.top--;
        }
        return poped;
    }

    static boolean ispar(String x)
    {
        char[] arr= x.toCharArray();
        for(int i=0;i<arr.length;i++){
            // push open bracket
                if(arr[i]=='('||arr[i]=='['||arr[i]=='{'){
                    push(arr[i]);
                    System.out.println("Pushed element is " + arr[i]);
                }
                else if(arr[i]==')'|| arr[i]==']'||arr[i]=='}'){
                    System.out.println("Poped element is " + pop());
                }
           }
        stack.size = newCount;

        // display stack
        if(stack.top==-1){
            System.out.println("Stack is empty");
            System.out.println("Pair of brackets present");
            return true;
        }
        else{
            System.out.println("Value present at stack top is " + stack.top);
            return false;
        }

    }

    public static void main(String[] args) {
        String str1 = "{([])}"; // true
        createStack(str1);
        System.out.println(ispar(str1));

        System.out.println("*************");
        String str2 = "()"; // true
        System.out.println(ispar(str2));

        System.out.println("*************");
        String str3 = "([]"; // false
        System.out.println(ispar(str3));

    }
}

/*OUTPUT
Pushed element is {
Pushed element is (
Pushed element is [
Poped element is [
Poped element is (
Poped element is {
Stack is empty
Pair of brackets present
true
*************
Pushed element is (
Poped element is (
Stack is empty
Pair of brackets present
true
*************
Pushed element is (
Pushed element is [
Poped element is [
Value present at stack top is 0
false
* */

Parenthesis Checker Optimized without Stack Implementation

Time Complexity : O(|x|)

Space Complexity : O(|x|)

 static boolean ispar(String x)
    {
        Stack<Character> stack = new Stack<>();

        char[] arr= x.toCharArray();
        if(arr.length==1){return false;}
        for(int i=0;i<arr.length;i++){
            if(arr[i]=='('||arr[i]=='['||arr[i]=='{'){
                stack.push(arr[i]);
            }
            else if(stack.empty()==false){
                char val = stack.peek();
                if((arr[i]==')' && val == '(') || (arr[i]==']' && val == '[') || (arr[i]=='}' && val == '{')){
                    stack.pop();}
                else{
                    return false;
                }
            }
            else{return false;}// if stack empty
        }

        if(stack.empty()==true){
            return true;
        }
        else{
            return false;
        }
    }

Thank you for reading :)