The Monotone Stack Implementation in Python

  • 时间:2020-09-18 17:01:02
  • 分类:网络文摘
  • 阅读:108 次
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) —

推荐阅读:
HPZ800 Server Does Not Support Hard Drives Larger Than 2TB  Fresno Blogger Changing The Vegan Blogging Scene  Russian ‘Pokemon Go’ Blogger Goes On Trial  Starting a Blog? 5 Topics People Care About in 2017  6 Strategies To Grow Your Facebook Page  5 Sure Shot Content Marketing Trends to Follow  7 Ways for Your Underdog Blog to Beat the Competition  Darkstore Aims to be Less Invasive Alternative to Tech Giants ac  5 Free Blogging Apps You Need On Your IPhone Right Now  The Exact Amount that You Must Spend on a Great Blog Is… 
评论列表
添加评论