上体育课的时候,老师已经把班级同学排成了两个队列,而且每个队列都是按照从底到高排好队,现在需要把两个队列合并,合并后需要保证还是从低到高排列。合并队列,你能编程实现吗?
时间: 2024-02-29 08:51:41 浏览: 198
当然可以,我可以用归并排序的思路来合并两个已经有序的队列,具体步骤如下:
1. 定义两个指针分别指向两个队列的队首,比较两个指针所指向的元素的大小,将小的元素插入到新的队列中,并将指向该元素的指针往后移动一位。
2. 重复上述操作直到一个队列的元素全部插入到新队列中,然后将另一个队列中剩余的元素依次插入到新队列中。
下面是具体的代码实现(假设队列中的元素为整数):
```python
def merge_queue(queue1, queue2):
queue = []
i, j = 0, 0
while i < len(queue1) and j < len(queue2):
if queue1[i] <= queue2[j]:
queue.append(queue1[i])
i += 1
else:
queue.append(queue2[j])
j += 1
queue += queue1[i:]
queue += queue2[j:]
return queue
```
在这个函数中,我们定义了一个新的队列 `queue`,然后遍历两个有序队列 `queue1` 和 `queue2`,比较队首元素的大小,将小的元素插入到新队列中,并将指向该元素的指针向后移动一位。最后,将剩余的元素依次插入到新队列中即可。
使用该函数合并两个队列的方法如下:
```python
queue1 = [1, 3, 5, 7, 9]
queue2 = [2, 4, 6, 8, 10]
merged_queue = merge_queue(queue1, queue2)
print(merged_queue)
```
输出结果为:
```
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
```
可以看到,合并后的队列仍然是有序的。