Stack
overflow
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() );
}
}Last updated