Implementing Monotonic Stack in Python

A monotonic stack is an extension of the Stack data structure in which the elements of the stack are in either increasing or decreasing order. The stack in which the items are in increasing order is called the monotonically increasing stack, the top element of such a stack will be the largest of all the elements below. On the other hand, if the items are arranged in a decreasing order then the stack is called a monotonically decreasing stack, on which the top element will be the smallest of all the elements below. Monotonic stacks are very popular in competitive programming.

Disclaimer: All code presented in this article has been run with Python 3.12 version, the same may not run expected on a different version of Python. Please modify the code accordingly based on the Python version(s).

The core of a monotonic stack is the LIFO stack, except for the fact that during every push() operation, the elements are popped from the stack till the desired ordering is achieved. A stack data structure is initially added as a Class with the following methods defined,
push - insert an element at the top of the stack
pop - remove the element at the top of the stack
is_empty - check whether a given stack has no entries
peek - return the element at the top of the stack without removing it

Apart from the core methods, there are two more methods that were added for debugging purposes,
__str__ - overloading the string format method to return the list of elements in stack
verify - a unit testing method to verify the stack elements at any given point of time

The Stack is coded as follows,

class Stack:
    def __init__(self):
        self.stack = []
        self.top = -1

    def peek(self):
        if not self.is_empty():
            return self.stack[self.top]
        return None

    def is_empty(self):
        return self.top == -1

    def push(self, num):
        self.stack.append(num)
        self.top += 1

    def pop(self):
        if not self.is_empty():
            self.top -= 1
            return self.stack.pop()
        return None

    def __str__(self):
        return "Stack: " + " -> ".join(str(i) for i in self.stack)

    def verify(self, expected):
        if self.stack != expected:
            raise Exception(f"Expected {expected}, got {self.stack}")

For push and pop methods, Python's existing list modification methods append and pop are used respectively. The top variable of the object keeps track of the index where the top of the stack is located. The is_empty method uses the top of the stack index to determine whether the stack is empty.

With the basic stack implementation, a monotonic stack can be implemented just by overriding the push method. There are two more classes added, one for the increasing and other for decreasing order. For an increasing stack, the top element is the highest, so if the current top is higher than the element that is being pushed, then a pop is invoked and the new top is compared and so on. The process repeats as long as the top element is less than the element being pushed or the stack becomes empty. For a decreasing stack, the reverse happens, the top element is smaller compared to the current element being pushed, then a series of pop operation happens, till all the elements in the stack are larger than the current element. These classes only implement the push method, but extends the base Stack class. These classes are coded as follows,

class IncreasingStack(Stack):
    def push(self, num):
        while not self.is_empty() and self.peek() >= num:
            self.pop()
        super().push(num)


class DecreasingStack(Stack):
    def push(self, num):
        while not self.is_empty() and self.peek() <= num:
            self.pop()
        super().push(num)

There are a set of tests written to validate the behavior of the newly implemented stacks. Each test pushes one element to a given stack and verifies the order of the stack to ensure the logic works fine. The test code is as follows, no output is shown but the assert trips in case of any failure.

def run_one_test(s, n, expected):
    s.push(n)
    s.verify(expected)


def run_tests(s, tests):
    for test in tests:
        run_one_test(s, test[0], test[1])


def run_dec_tests():
    dec_tests = [
        (1, [1]),
        (2, [2]),
        (4, [4]),
        (3, [4, 3]),
        (6, [6]),
        (5, [6, 5]),
    ]
    s = DecreasingStack()
    run_tests(s, dec_tests)


def run_inc_tests():
    inc_tests = [
        (1, [1]),
        (2, [1, 2]),
        (4, [1, 2, 4]),
        (3, [1, 2, 3]),
        (6, [1, 2, 3, 6]),
        (5, [1, 2, 3, 5]),
    ]
    s = IncreasingStack()
    run_tests(s, inc_tests)


run_inc_tests()
run_dec_tests()

Thank you for reading the article, please leave your suggestions or comments if any.