Skip to content

Instantly share code, notes, and snippets.

@fatihsokmen
Last active August 29, 2015 14:15
Show Gist options
  • Save fatihsokmen/c3d9af384fe81ffa0529 to your computer and use it in GitHub Desktop.
Save fatihsokmen/c3d9af384fe81ffa0529 to your computer and use it in GitHub Desktop.
Stack implementation + getting minimum with O(1)
public class Stack {
private int[] data;
private int size = 0;
private int cursor = -1;
private int min = 0;
private final static float LOAD_FACTOR = 1.4f;
public Stack() {
data = new int[10];
}
public void push(int x) {
adjustIfNeeded();
if (size == 0 || x < min) {
data[++cursor] = min;
data[++cursor] = x;
min = x;
} else {
data[++cursor] = x;
}
size++;
}
public int pop() {
if (size > 0) {
int x = data[cursor--];
if (x == min && cursor >= 0) {
min = data[cursor--]; // move left
}
size--;
return x;
}
return -1;
}
public int getMin() {
return min;
}
public int size() {
return size;
}
private void adjustIfNeeded() {
int l = data.length;
if ((cursor == l - 1) || (cursor == l - 2)) {
int[] buffer = new int[(int) (data.length * LOAD_FACTOR)];
System.arraycopy(data, 0, buffer, 0, data.length);
data = buffer;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment