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) —

推荐阅读:
How to Improve Your Blog’s Bounce Rate (and Why You Should)  Does Your SME Have A Disaster Recovery Plan?  7 Best SEO Trends Gaining Popularity In 2019  How To Choose The Best Hosting Service For A WordPress Website  An Idiot’s Guide to Email Automation for Bloggers  Checklist for Choosing a Perfect WordPress Blog Theme  15 Mindset Hacks to Avoid Blogging Failure  Can Retailers Refuse Refunds Using POS Software?  How to Create Sponsorship Proposals For Your Blog  7 Top Investment Blogs For Newbie And Veteran Investors 
评论列表
添加评论