## 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:
1. The current visiting value is guaranteed to be more optimal than all larger values visted so far.
2. 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:
1. The current visiting value is guaranteed to be more optimal than all smaller values visted so far.
2. 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