description	overflow

Stack

Implement Queue using Stack

class MyQueue {
	Stack stack;
	int top;

	public MyQueue() {
		stack = new Stack();
	}

	public void push(int x) {
		Stack temp = new Stack();
		if (stack.isEmpty()) {
			stack.push(x);
		} else {
			while (!stack.isEmpty()) {
				temp.push(stack.pop());
			}
			stack.push(x);
			while (!temp.isEmpty()) {
				stack.push(temp.pop());
			}
		}
	}

	public int pop() {
		return (int) stack.pop();
	}

	public int peek() {
		return (int) stack.peek();
	}

	public boolean empty() {
		return stack.isEmpty();
	}
}

Balanced Parenthesis

import java.util.Stack;

class Solution {

	static public boolean isValid(String s) {
		Stack<Character> stck = new Stack<>();

		for (char bracket : s.toCharArray()) {
			if (bracket == '(' || bracket == '[' || bracket == '{') {
				stck.push(bracket);
			} else {
				try {
					char lstBracker = stck.peek();
					if (lstBracker == '(' && bracket == ')') {
						stck.pop();
					} else if (lstBracker == '[' && bracket == ']') {
						stck.pop();
					} else if (lstBracker == '{' && bracket == '}') {
						stck.pop();
					} else {
						return false;
					}
				} catch (Exception e) {
					return false;
				}
			}
		}

		return stck.size() == 0 ? true : false;

	}

	public static void main(String[] args) {
		System.out.println(isValid("{()}[]"));
	}
}

Two stacks in an array(Useless Question)

        import java.io.*;
        import java.util.*;

class TwoStacks {
    int cap;
    int top1, top2;
    int arr[];

    TwoStacks(int n) {
        arr = new int[n];
        cap = n;
        top1 = -1;
        top2 = cap;
    }

    void push1(int x) {
        if (top1 < top2 - 1) {
            top1++;
            arr[top1] = x;
        } else {
            System.out.println("Stack Overflow");
            System.exit(1);
        }
    }

    void push2(int x) {
        if (top1 < top2 - 1) {
            top2--;
            arr[top2] = x;
        } else {
            System.out.println("Stack Overflow");
            System.exit(1);
        }
    }

    int pop1() {
        if (top1 >= 0) {
            int x = arr[top1];
            top1--;
            return x;
        } else {
            System.out.println("Stack Underflow");
            System.exit(1);
        }
        return 0;
    }

    int pop2() {
        if (top2 < cap) {
            int x = arr[top2];
            top2++;
            return x;
        } else {
            System.out.println("Stack Underflow");
            System.exit(1);
        }
        return 0;
    }
}

class Main {

    public static void main(String[] args) {

        TwoStacks ts = new TwoStacks(5);
        ts.push1(5);
        ts.push2(10);
        ts.push2(15);
        ts.push1(11);
        ts.push2(7);
        System.out.println("Popped element from stack1 is: " + ts.pop1());
        ts.push2(40);
        System.out.println("Popped element from stack2 is: " + ts.pop2());

    }

}

K Stacks in an array(UseLess Question)

class kStacks {
    int arr[];
    int top[];
    int next[];
    int cap, k;
    int freeTop;

    kStacks(int k1, int n) {
        k = k1;
        cap = n;
        arr = new int[cap];
        top = new int[k];
        next = new int[cap];

        for (int i = 0; i < k; i++)
            top[i] = -1;

        freeTop = 0;
        for (int i = 0; i < cap - 1; i++)
            next[i] = i + 1;
        next[cap - 1] = -1;
    }

    boolean isFull() {
        return (freeTop == -1);
    }

    boolean isEmpty(int sn) {
        return (top[sn] == -1);
    }

    void push(int x, int sn) {
        if (isFull()) {
            System.out.print("\nStack Overflow\n");
            return;
        }

        int i = freeTop;
        freeTop = next[i];
        next[i] = top[sn];
        top[sn] = i;
        arr[i] = x;
    }

    int pop(int sn) {
        if (isEmpty(sn)) {
            System.out.print("\nStack Underflow\n");
            return Integer.MAX_VALUE;
        }

        int i = top[sn];
        top[sn] = next[i];
        next[i] = freeTop;
        freeTop = i;
        return arr[i];
    }

}

class Main {

    public static void main(String[] args) {

        int k = 3, n = 10;
        kStacks ks = new kStacks(k, n);

        ks.push(15, 2);
        ks.push(45, 2);

        ks.push(17, 1);
        ks.push(49, 1);
        ks.push(39, 1);

        ks.push(11, 0);
        ks.push(9, 0);
        ks.push(7, 0);

        System.out.println("Popped element from stack 2 is " + ks.pop(2));
        System.out.println("Popped element from stack 1 is " + ks.pop(1));
        System.out.println("Popped element from stack 0 is " + ks.pop(0));

    }

}

Stock Span Problem

        import java.io.*;
        import java.util.*;

class GFG {

    public static void printSpan(int arr[], int n) {
        Stack<Integer> s = new Stack<>();
        s.add(0);
        System.out.print(1 + " ");
        for (int i = 1; i < n; i++) {
            while (s.isEmpty() == false && arr[s.peek()] <= arr[i]) {
                s.pop();
            }
            int span = s.isEmpty() ? i + 1 : i - s.peek();
            System.out.print(span + " ");
            s.push(i);
        }
    }

    public static void main(String[] args) {

        int[] arr = new int[]{18, 12, 13, 14, 11, 16};

        printSpan(arr, arr.length);

    }

}

Previous Greater Element

        import java.io.*;
        import java.util.*;

class GFG {

    public static void printPrevGreater(int arr[], int n) {

        Stack<Integer> s = new Stack<>();
        s.add(arr[0]);
        for (int i = 0; i < n; i++) {
            while (s.isEmpty() == false && s.peek() <= arr[i])
                s.pop();
            int pg = s.isEmpty() ? -1 : s.peek();
            System.out.print(pg + " ");
            s.add(arr[i]);
        }
    }

    public static void main(String[] args) {

        int[] arr = new int[]{20, 30, 10, 5, 15};

        printPrevGreater(arr, arr.length);

    }

}

Next Greater Element

import java.io.*;
import java.util.*;

class GFG {

    public static ArrayList<Integer> nextGreater(int arr[],int n){
        ArrayList<Integer> v=new ArrayList<>();
        Stack <Integer> s=new Stack<>();
        s.add(arr[n-1]);v.add(-1);
        for(int i=n-2;i>=0;i--){
            while(s.isEmpty()==false && s.peek()<=arr[i])
                s.pop();
            int ng=s.isEmpty()?-1:s.peek();
            v.add(ng);
            s.add(arr[i]);
        }
        Collections.reverse(v);
        return v;
    }
    public static void main (String[] args) {

        int[] arr=new int[]{5,15,10,8,6,12,9,18};

        for(int x: nextGreater(arr,arr.length)){
            System.out.print(x + " ");   
        }  

    }

}

Largest Rectangular Area in a Histogram (Part 1)

import java.io.*;
import java.util.*;

class GFG {

    public static int getMaxArea(int arr[], int n) {
        int res = 0;
        int[] ps = new int[n];
        int[] ns = new int[n];

        Stack<Integer> s = new Stack<>();
        s.add(0);
        for (int i = 0; i < n; i++) {
            while (s.isEmpty() == false && arr[s.peek()] >= arr[i])
                s.pop();
            int pse = s.isEmpty() ? -1 : s.peek();
            ps[i] = pse;
            s.push(i);
        }

        while (s.isEmpty() == false) {
            s.pop();
        }

        s.push(n - 1);
        for (int i = n - 1; i > 0; i--) {
            while (s.isEmpty() == false && arr[s.peek()] >= arr[i])
                s.pop();
            int nse = s.isEmpty() ? n : s.peek();
            ns[i] = nse;
            s.add(i);
        }

        for (int i = 0; i < n; i++) {
            int curr = arr[i];
            curr += (i - ps[i] - 1) * arr[i];
            curr += (ns[i] - i - 1) * arr[i];
            res = Math.max(res, curr);
        }
        return res;

    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 2, 5, 4, 1, 5, 6};
        System.out.print("Maximum Area: " + getMaxArea(arr, arr.length));
    }
}

Largest Rectangular Area in a Histogram (Part 2)

import java.io.*;
import java.util.*;

class GFG {

    public static int getMaxArea(int arr[], int n) {
        Stack<Integer> s = new Stack<>();
        int res = 0;
        int tp;
        int curr;
        for (int i = 0; i < n; i++) {
            while (s.isEmpty() == false && arr[s.peek()] >= arr[i]) {
                tp = s.peek();
                s.pop();
                curr = arr[tp] * (s.isEmpty() ? i : i - s.peek() - 1);
                res = Math.max(res, curr);
            }
            s.add(i);
        }
        while (s.isEmpty() == false) {
            tp = s.peek();
            s.pop();
            curr = arr[tp] * (s.isEmpty() ? n : n - s.peek() - 1);
            res = Math.max(res, curr);
        }

        return res;

    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 2, 5, 4, 1, 5, 6};
        System.out.print("Maximum Area: " + getMaxArea(arr, arr.length));
    }
}

Largest Rectangle with all 1's (in a matrix)

import java.io.*;
import java.util.*;

class GFG {

    public static int largestHist(int R, int C, int arr[]) {
        Stack<Integer> result = new Stack<Integer>();

        int top_val;
        int max_area = 0;
        int area = 0;

        int i = 0;
        while (i < C) {
            if (result.empty() || arr[result.peek()] <= arr[i])
                result.push(i++);

            else {

                top_val = arr[result.peek()];
                result.pop();
                area = top_val * i;

                if (!result.empty())
                    area = top_val * (i - result.peek() - 1);
                max_area = Math.max(area, max_area);
            }
        }

        while (!result.empty()) {
            top_val = arr[result.peek()];
            result.pop();
            area = top_val * i;
            if (!result.empty())
                area = top_val * (i - result.peek() - 1);

            max_area = Math.max(area, max_area);
        }
        return max_area;
    }

    static int maxRectangle(int R, int C, int mat[][]) {
        int res = largestHist(R, C, mat[0]);

        for (int i = 1; i < R; i++) {

            for (int j = 0; j < C; j++)

                if (mat[i][j] == 1)
                    mat[i][j] += mat[i - 1][j];

            res = Math.max(res, largestHist(R, C, mat[i]));
        }

        return res;
    }

    public static void main(String[] args) {
        int R = 4;
        int C = 4;

        int A[][] = {
                {0, 1, 1, 0},
                {1, 1, 1, 1},
                {1, 1, 1, 1},
                {1, 1, 0, 0},
        };
        System.out.print("Area of maximum rectangle is " + maxRectangle(R, C, A));
    }
}

Stack with getMin() in O(1)

import java.io.*;
import java.util.*;

class MyStack {

    Stack<Integer> ms;
    Stack<Integer> as;

    MyStack(){
        ms=new Stack<>();
        as=new Stack<>();
    }

void push(int x) {

      if(ms.isEmpty() ) {
          ms.add(x);as.add(x);return;
      }

      ms.add(x);

      if(as.peek()>=ms.peek())
        as.add(x);
   }

void pop() {

    if(as.peek()==ms.peek())
        as.pop();
    ms.pop();

   }

int top() {
     return ms.peek();
   }

int getMin() {
      return as.peek();
   }
}

class GFG {

    public static void main(String[] args) 
    { 
        MyStack s=new MyStack();;
        s.push(4);
        s.push(5);
        s.push(8);
        s.push(1);
        s.pop();

        System.out.print(" Minimum Element from Stack: " + s.getMin() );

    } 
}

Design a Stack with getMin() in O(1) Space

Assuming all Elements Positive

import java.io.*;
import java.util.*;

class MyStack {

    Stack<Integer> s;
    int min;

    MyStack() {
        s = new Stack<>();
    }

    void push(int x) {

        if (s.isEmpty()) {
            min = x;
            s.add(x);
        } else if (x <= min) {
            s.add(x - min);
            min = x;
        } else {
            s.add(x);
        }
    }

    int pop() {

        int t = s.peek();
        s.pop();
        if (t <= 0) {
            int res = min;
            min = min - t;
            return res;
        } else {
            return t;
        }
    }

    int peek() {
        int t = s.peek();
        return ((t <= 0) ? min : t);
    }

    int getMin() {
        return min;
    }
}

class GFG {

    public static void main(String[] args) {
        MyStack s = new MyStack();
        ;
        s.push(4);
        s.push(5);
        s.push(8);
        s.push(1);
        s.pop();

        System.out.print(" Minimum Element from Stack: " + s.getMin());
    }
}

Handles Negatives

import java.io.*;
import java.util.*;

class MyStack {

    Stack<Integer> s;
    int min;

    MyStack(){
        s=new Stack<>();
    }

    void push(int x) {

        if(s.isEmpty() ) {
            min=x;
            s.add(x);
        }
        else if(x<=min){
            s.add(2*x-min);
            min=x;
        }else{
            s.add(x);
        }
    }

    int pop() {

        int t=s.peek();s.pop();
        if(t<=min){
            int res=min;
            min=2*min-t;
            return res;
        }else{
            return t;
        }
    }

    int peek() {
        int t=s.peek();
        return ((t<=min)? min : t);
    }

    int getMin() {
        return min;
    }
}

class GFG {

    public static void main(String[] args)
    {
        MyStack s=new MyStack();;
        s.push(4);
        s.push(5);
        s.push(8);
        s.push(1);
        s.pop();

        System.out.print(" Minimum Element from Stack: " + s.getMin() );
    }
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Stack

Implement Queue using Stack

Balanced Parenthesis

Two stacks in an array(Useless Question)

K Stacks in an array(UseLess Question)

Stock Span Problem

Previous Greater Element

Next Greater Element

Largest Rectangular Area in a Histogram (Part 1)

Largest Rectangular Area in a Histogram (Part 2)

Largest Rectangle with all 1's (in a matrix)

Stack with getMin() in O(1)

Design a Stack with getMin() in O(1) Space

Assuming all Elements Positive

Handles Negatives

FilesExpand file tree

stack.md

Latest commit

History

stack.md

File metadata and controls

Stack

Implement Queue using Stack

Balanced Parenthesis

Two stacks in an array(Useless Question)

K Stacks in an array(UseLess Question)

Stock Span Problem

Previous Greater Element

Next Greater Element

Largest Rectangular Area in a Histogram (Part 1)

Largest Rectangular Area in a Histogram (Part 2)

Largest Rectangle with all 1's (in a matrix)

Stack with getMin() in O(1)

Design a Stack with getMin() in O(1) Space

Assuming all Elements Positive

Handles Negatives