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) —
推荐阅读:口腔食疗:牙龈“去火”的常见食物 贝因美营养米粉被指违规添加猪肝粉 作坊“老字号”竟用工业盐腌制烤鸭 网传男人应远离的八大败“性”食物 导致食物致癌多是人为因素造成 颜色鲜亮的枸杞可能导致肝肾损伤 不是所有食物都适合用保鲜膜“保鲜” 新鲜水果的最佳食用时间是何时? 食用水果时应该注意的一些问题 男人不能常喝豆浆的传言荒谬至极
- 评论列表
-
- 添加评论