The Monotone Stack Implementation in Python

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

推荐阅读:
春季饮食宜润肺,常吃炖梨既滋润又养人,口感甜香味道美  这道小学应用题比较难,解题关键是求相遇时间  豆腐搭配鸡蛋做出香酥可口的丸子,营养也很丰富  这道小学奥数题难倒多数学生,解题关键是比例  分享茄子的家常做法,吃起来不油腻,营养美味又下饭  中华人民共和国慈善法(主席令第四十三号)  中华人民共和国深海海底区域资源勘探开发法(主席令第四十二号)  全国人民代表大会常务委员会关于修改《中华人民共和国人口与计划生育法》的决定(主席令第四十一号)  全国人大常委会关于修改《中华人民共和国高等教育法》的决定(主席令第四十号)  中华人民共和国反家庭暴力法(主席令第三十七号) 
评论列表
添加评论