The Monotone Queue Implementation in Python
- 时间:2020-09-18 17:01:02
- 分类:网络文摘
- 阅读:98 次

queue-data-structure
A queue is a first-in-first-out (FIFO) data structure.
We all know that the list/array in Python is very powerful, that it can be used as a queue itself. For example, to create a queue in Python, we do this:
1 | q = [] |
q = []
Then, we can push an element to the queue using the list append() method.
1 2 3 4 5 | q.append(1) q.append(2) q.append(3) # now the queue has 3 elements [1, 2, 3] |
q.append(1) q.append(2) q.append(3) # now the queue has 3 elements [1, 2, 3]
We can check the length of the list in order to perform the queue.empty() test.
1 2 | def isEmptyQueue(queue): return len(queue) == 0 |
def isEmptyQueue(queue): return len(queue) == 0
The last element in the list/array will be useful, such as peeking the top of the queue:
1 2 | def peekQueue(queue): return queue[-1] |
def peekQueue(queue): return queue[-1]
Popping an element i.e. deQueue() is even simpler with the array.pop(0) method – which removes the first element (index zero) from the list/array and return it. For example:
1 2 | def deQueue(queue): return queue.pop(0) |
def deQueue(queue): return queue.pop(0)
The Monotone Queue in Python
A Monotone queue is a queue, however, it preserves the orders of the elements in the queue from left to the right. For example, the Monotone decreasing queue looks like:
1 | q = [5, 4, 3, 2, 1] |
q = [5, 4, 3, 2, 1]
Now, if we now push another element, e.g. 3, to the queue. It will dequeue the elements that are larger than 3 before 3 is pushed to the queue.
1 | q = [3, 3, 2, 1] # 5 and 4 will be dequeued and removed. |
q = [3, 3, 2, 1] # 5 and 4 will be dequeued and removed.
At anytime, the monotone queue will keep the elements in the queue in either increasing or decreasing order (monotone sequence). The Monotone queue is handy as it tells us the next smaller-or-equal element. For example, in the above case, we know the next smaller-or-equal number is 3.
1 2 3 4 | def pushMontoQueue(queue, ele): while len(queue) > 0 and queue[0] > ele: queue.pop(0) # deQueue queue.push(ele) |
def pushMontoQueue(queue, ele): while len(queue) > 0 and queue[0] > ele: queue.pop(0) # deQueue queue.push(ele)
Similar, the array/list can be used to implement a monotone stack.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:如何分析优化竞价推广效果 竞价推广效果差怎么办?从这8个维度分析着手优化 小说网站建站赚钱怎么操作? 做什么网站赚钱?试试小说网站吧 百度冰桶算法说明,如何避免冰桶算法呢? 百度飓风算法版本类型说明,如何破解飓风算法呢 最少要付多少元的租金 此时水的高度是多少 将原有水果卖出40%后 求这五个整数的平均数
- 评论列表
-
- 添加评论