# Stacks and Queues

Last Updated: 2024-01-17

## 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();
}
}
}
``````

## By Language

### Java

``````import java.util.Stack;

Stack<Integer> stack = new Stack<>();

stack.push(i);
stack.pop();

stack.isEmpty();
``````

### Python

List can be used as a stack:

``````stack = []
stack.append(1)
stack.pop()

# Check empty
not stack
``````

Use `collections.deque` for quicker `append()` and `pop()`:

``````from collections import deque

stack = deque()

stack.append(1)
stack.pop()
``````