上体育课的时候,老师已经把班级同学排成了两个队列,而且每个队列都是按照从底到高排好队,现在需要把两个队列合并,合并后需要保证还是从低到高排列。合并队列,用C++编程实现
时间: 2024-02-29 07:51:42 浏览: 20
当然可以,我可以用归并排序的思路来合并两个已经有序的队列,具体步骤如下:
1. 定义两个指针分别指向两个队列的队首,比较两个指针所指向的元素的大小,将小的元素插入到新的队列中,并将指向该元素的指针往后移动一位。
2. 重复上述操作直到一个队列的元素全部插入到新队列中,然后将另一个队列中剩余的元素依次插入到新队列中。
下面是具体的代码实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
vector<int> merge_queue(vector<int>& queue1, vector<int>& queue2) {
vector<int> queue;
int i = 0, j = 0;
while (i < queue1.size() && j < queue2.size()) {
if (queue1[i] <= queue2[j]) {
queue.push_back(queue1[i]);
i++;
} else {
queue.push_back(queue2[j]);
j++;
}
}
while (i < queue1.size()) {
queue.push_back(queue1[i]);
i++;
}
while (j < queue2.size()) {
queue.push_back(queue2[j]);
j++;
}
return queue;
}
int main() {
vector<int> queue1 = {1, 3, 5, 7, 9};
vector<int> queue2 = {2, 4, 6, 8, 10};
vector<int> merged_queue = merge_queue(queue1, queue2);
for (int i = 0; i < merged_queue.size(); i++) {
cout << merged_queue[i] << " ";
}
cout << endl;
return 0;
}
```
在这个代码中,我们定义了一个新的向量 `queue`,然后遍历两个有序队列 `queue1` 和 `queue2`,比较队首元素的大小,将小的元素插入到新队列中,并将指向该元素的指针向后移动一位。最后,将剩余的元素依次插入到新队列中即可。
输出结果为:
```
1 2 3 4 5 6 7 8 9 10
```
可以看到,合并后的队列仍然是有序的。