Data Structures
Overview
Number
String
Array
Stack
Hash
Tree
Trie
Probabilistic Data Structures
Big O

# Stack

Updated: 2021-12-15

## Basic Stack

class Stack<T> {
class Node {
T data;
Node next;
}

protected int size;
protected Node top;

public boolean isEmpty() {
}

public int size() {
return size;
}

public T peek() {
if (isEmpty()) {
return null;
}
}

public T pop() {
if (isEmpty()) {
throw new RuntimeException("Stack is Empty.");
}

T data = top.data;
top = top.next;
size--;
return data;
}

public void push(T data) {
Node tmp = top;
top = new Node();
top.data = data;
top.next = tmp;
size++;
}
}

## Stack with O(1) Min Operation

Store a min value in each node. Could be redundant.

class StackWithMin extends Stack<Integer> {

class NodeWithMin extends Stack<Integer>.Node {
int min;
}

public void push(int data) {
int m = Math.min(data, min());
NodeWithMin tmp = ((NodeWithMin) top);
top = new NodeWithMin();
top.data = data;
((NodeWithMin) top).min = m;
top.next = tmp;
size++;
}

public int min() {
if (isEmpty()) {
return Integer.MAX_VALUE;
}
return ((NodeWithMin) top).min;
}
}

Use another stack to store min values.

class StackWithMin extends Stack<Integer> {
private Stack<Integer> minStack;

public StackWithMin() {
minStack = new Stack<Integer>();
}

public Integer pop() {
int data = super.pop();
if (data == min()) {
minStack.pop();
}
return data;
}

public void push(int data) {
if (data < min()) {
minStack.push(data);
}
super.push(data);
}

public Integer min() {
if (isEmpty()) {
return Integer.MAX_VALUE;
} else {
return minStack.peek();
}
}
}