顺序优先队列的两种策略与编程实现及完整代码
时间: 2024-04-30 18:23:32 浏览: 22
顺序优先队列是一种数据结构,可以实现在队列中按优先级排序。在顺序优先队列中,元素按照其优先级排序,优先级最高的元素排在队列的前面,而优先级最低的元素排在队列的后面。顺序优先队列的实现方式有两种策略:升序和降序。
1. 升序策略
升序策略是指在队列中,优先级最低的元素在队列的前面,而优先级最高的元素在队列的后面。在升序策略中,元素是按照其优先级从小到大排序的。
在编程实现中,我们可以使用一个数组来存储队列中的元素,每次插入新元素时,将其插入到数组的合适位置,以保证队列中的元素是有序的。具体实现如下:
```python
class PriorityQueue:
def __init__(self):
self.queue = []
def enqueue(self, element):
index = len(self.queue)
for i in range(len(self.queue)):
if element < self.queue[i]:
index = i
break
self.queue.insert(index, element)
def dequeue(self):
if self.is_empty():
return None
return self.queue.pop()
def is_empty(self):
return len(self.queue) == 0
```
2. 降序策略
降序策略是指在队列中,优先级最高的元素在队列的前面,而优先级最低的元素在队列的后面。在降序策略中,元素是按照其优先级从大到小排序的。
在编程实现中,我们可以使用一个数组来存储队列中的元素,每次插入新元素时,将其插入到数组的合适位置,以保证队列中的元素是有序的。具体实现如下:
```python
class PriorityQueue:
def __init__(self):
self.queue = []
def enqueue(self, element):
index = len(self.queue)
for i in range(len(self.queue)):
if element > self.queue[i]:
index = i
break
self.queue.insert(index, element)
def dequeue(self):
if self.is_empty():
return None
return self.queue.pop()
def is_empty(self):
return len(self.queue) == 0
```
完整代码如下:
```python
class PriorityQueue:
def __init__(self, reverse=False):
self.queue = []
self.reverse = reverse
def enqueue(self, element):
index = len(self.queue)
for i in range(len(self.queue)):
if self.reverse:
if element > self.queue[i]:
index = i
break
else:
if element < self.queue[i]:
index = i
break
self.queue.insert(index, element)
def dequeue(self):
if self.is_empty():
return None
return self.queue.pop()
def is_empty(self):
return len(self.queue) == 0
```
使用示例:
```python
q = PriorityQueue()
q.enqueue(3)
q.enqueue(1)
q.enqueue(5)
q.enqueue(2)
q.enqueue(4)
while not q.is_empty():
print(q.dequeue())
# Output: 1 2 3 4 5
q = PriorityQueue(reverse=True)
q.enqueue(3)
q.enqueue(1)
q.enqueue(5)
q.enqueue(2)
q.enqueue(4)
while not q.is_empty():
print(q.dequeue())
# Output: 5 4 3 2 1
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)