Skip to content

Instantly share code, notes, and snippets.

@berkayk
Created January 30, 2016 12:29
Show Gist options
  • Save berkayk/412d5050db7a18f73fa7 to your computer and use it in GitHub Desktop.
Save berkayk/412d5050db7a18f73fa7 to your computer and use it in GitHub Desktop.
public class Node {
public Node next;
public Node nextMinimum;
public int data;
public Node(int value) {
this.data = value;
}
}
class MinStack {
public Node top;
public Node minimum;
public int minValue;
public int pop() {
if (top == null) {
return null;
}
// popping minimum
if (top == minimum) {
minimum = top.nextMinimum;
if (minimum != null) {
minValue = minimum.data;
}
else {
minValue = Integer.MAX_VALUE;
}
}
int retValue = top.data;
top = top.next;
return retValue;
}
public void push(int value) {
Node node = new Node(value);
if (top == null) {
top = node;
minValue = top.data;
minimum = top;
}
else {
node.next = top;
top = node;
if (value < minValue) {
minValue = value;
// We have other minimum
if (minimum != null) {
node.nextMinimum = minimum;
}
minimum = node;
}
}
}
public int getMinValue() {
return minValue;
}
public Node getMinNode() {
return minimum;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment