# Stack

## Remarks

- A stack is a collection that is Last-In-First-Out(LIFO).

## Implementation

An implementation of Stack using linked list.

```
class Node:
def __init__(self, item=None):
self.item = item
self.next = None
class Stack:
def __init__(self):
self.node = None
self._n = 0
@property
def is_empty(self):
return not self.node
def __len__(self):
return self.n
def push(self, item):
prev = self.node
self.node = self.Node(item)
self.node.next = prev
self._n += 1
def pop(self):
assert not self.is_empty, "Stack is empty"
item = self.node.item
self.node = self.node.next
self._n -= 1
return item
def peek(self):
return self.node.item
```

## Monotonic Stack

```
arr = [1, 5, 2, 4, 6, 3, -1]
```

### Monotonic Increasing Stack

- Sweep through an array of values and use stack to keep track of elements visited so far in a increasing order.
- Applicable when:
- The current visiting value is guaranteed to be more optimal than all larger values visted so far.
- But can not rule out the possibility that the smaller visited values can be better.

- Mental graph - you are tracking the flattest uphill path from the lowest starting point.

with the example array `arr`

show above:

iteration | stack | element values | remark |
---|---|---|---|

0 | [0] | [1] | stack is empty |

1 | [0, 1] | [1, 5] | start to walk uphill |

2 | [0, 2] | [1, 2] | found a flatter uphill path |

3 | [0, 2, 3] | [1, 2, 4] | continue walk uphill |

4 | [0, 2, 3, 4] | [1, 2, 4, 6] | continue walk uphill |

5 | [0, 2, 5] | [1, 2, 3] | found a flatter uphill path |

6 | [6] | [-1] | found a new lowest point |

### Monotonic Decreasing Stack

- Similar to monotonic increasing stack, just the reverse in condition.
- Sweep through an array of values and use stack to keep track of elements visited so far in a decreasing order.
- Applicable when:
- The current visiting value is guaranteed to be more optimal than all smaller values visted so far.
- But can not rule out the possibility that the larger visited values can be better.

- Mental graph - you are tracking the flattest downhill path from the highest starting point.

with the example array `arr`

show above:

iteration | stack | element values | remark |
---|---|---|---|

0 | [0] | [1] | stack is empty |

1 | [1] | [5] | found a new highest point |

2 | [1, 2] | [5, 2] | continue walk downhill |

3 | [1, 3] | [5, 4] | found a flatter downhill path |

4 | [4] | [6] | found a new lowest point |

5 | [4, 5] | [6, 3] | continue walk downhill |

6 | [4, 5, 6] | [6, 3, -1] | continue walk downhill |