The Monotone Stack Implementation in Python

  • 时间:2020-09-18 17:01:02
  • 分类:网络文摘
  • 阅读:94 次
Stack-Operation-in-C-Programming The Monotone Stack Implementation in Python data structure 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) —

推荐阅读:
Javascript Coding Exercise: The QuickSort Implementation in Java  In-place Run-Length String Compressions using C++  Algorithms to Compute the Factor Combinations for An Integer usi  How and Why You Should Use Infographics On Your Blog  How to Make Your “Contact Us” Page Kick Ass  The A to Z of Content Marketing: Habits Every Content Marketer S  Keeping the Flame Going: How to Rock a Steady Job and Still Have  How to Use Social Media and User-Generated Content to Boost Traf  7 Types of Blog Posts and When to Use Them  How to Maximize Profit From Your Blog Visitors 
评论列表
添加评论