The Monotone Stack Implementation in Python

Stack-Operation-in-C-Programming

A stack is a first-in-last-out (FILO) data structure.

We all know that the list/array in Python is very powerful, that it can be used as a stack itself. For example, to create a stack in Python, we do this:

1

st = []

st = []

Then, we can push an element to the stack using the list append() method.

1
2
3
4
5

st.append(1)
st.append(2)
st.append(3)
# now the stack has 3 elements
[1, 2, 3]

st.append(1)
st.append(2)
st.append(3)
# now the stack has 3 elements
[1, 2, 3]

We can check the length of the list in order to perform the stack.empty() test.

1
2

def isEmptyStack(st):
   return len(st) == 0

def isEmptyStack(st):
   return len(st) == 0

The last element in the list/array will be useful, such as peeking the top of the stack:

1
2

def peekStack(st):
   return st[-1]

def peekStack(st):
   return st[-1]

Popping an element is even simpler with the array.pop() method – which removes the last element from the list/array and return it.. For example:

1
2

def popStack(st):
   return st.pop()

def popStack(st):
   return st.pop()

The Monotone Stack in Python

A Monotone stack is a stack, however, it preserves the orders of the elements in the stack from left to the right. For example, the Monotone decreasing stack looks like:

1

st = [5, 4, 3, 2, 1]

st = [5, 4, 3, 2, 1]

Now, if we now push another element, e.g. 3, to the stack. It will pop out elements that are smaller than 3 before 3 is pushed to the stack.

1

st = [5, 4, 3, 3] # 2 and 1 will be removed

st = [5, 4, 3, 3] # 2 and 1 will be removed

At anytime, the monotone stack will keep the elements in the stack in either increasing or decreasing order (monotone sequence). The Monotone stack is handy as it tells us the next larger-or-equal element. For example, in the above case, we know the next larger-or-equal number is 3.

1
2
3
4

def pushMontoStack(st, ele):
   while len(st) > 0 and st[-1] < ele:
       st.pop()
   st.push(ele)

def pushMontoStack(st, ele):
   while len(st) > 0 and st[-1] < ele:
       st.pop()
   st.push(ele)

Similarly, we can use the same data-structure i.e. array/list in Python to implement a montotone Queue.

–EOF (The Ultimate Computing & Technology Blog) —