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

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) —
推荐阅读:网站的优化技巧,掌握这些对网站排名更好 商城系统常见开发语言及特点分享 吐槽一下一些“正在吐槽百度的人 滴滴的内部赛马:网约车与出租车各自进化,一亿补贴投向快的新出租 如何写好SEO软文? SEOer众生相 2020年该如何做好网站外链建设? 摩围山作文 生活因诚信而精彩作文750字 蔷薇别墅的老鼠读后感
- 评论列表
-
- 添加评论