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

example 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

Sample Questions: