Skip to content

Instantly share code, notes, and snippets.

@iwilbert
Created July 4, 2014 21:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save iwilbert/5c62763ac77541d24e28 to your computer and use it in GitHub Desktop.
Save iwilbert/5c62763ac77541d24e28 to your computer and use it in GitHub Desktop.
public class StackMin{
private int[] Stk;
private int top_s;
private int[] Min;
private int top_m;
public StackMin() {
this.Stk = new int[1];
this.Min = new int[1];
this.top_s = -1;
this.top_m = -1;
}
public void push(int val) {
resize_if_full();
Stk[++top_s] = val;
if(top_m == -1 || val < Min[top_m])
Min[++top_m] = val;
}
private void resize_if_full() {
if(top_s == Stk.length-1) {
int size = Stk.length;
int[] temp = new int[size * 2];
for(int i = 0; i < size; i++)
temp[i] = Stk[i];
Stk = temp;
}
if(top_m == Min.length-1) {
int size = Min.length;
int[] temp = new int[size * 2];
for(int i = 0; i < size; i++)
temp[i] = Min[i];
Min = temp;
}
}
public int pop() {
if(isEmpty())
throw new NoSuchElementException("stack underflow!");
int val = Stk[top_s--];
if(Min[top_m] == val && Stk[top_s] != val)
top_m--;
return val;
}
private boolean isEmpty() {
return top_s == -1;
}
public int min() {
if(isEmpty())
throw new NoSuchElementException("stack underflow!");
return Min[top_m];
}
}
@jason51122
Copy link

  1. You can use Stack class from Java instead of creating 2 new arrays.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment