c++队列实现火车车厢重排
时间: 2024-04-15 11:22:48 浏览: 63
C++中可以使用队列来实现火车车厢的重排。队列是一种先进先出(FIFO)的数据结构,可以用来模拟车厢的进出顺序。
具体实现步骤如下:
1. 首先,定义一个队列来存储火车车厢的编号。
2. 将火车车厢的编号按照需要的顺序依次入队。
3. 从队列中依次出队,将出队的车厢编号按照出队顺序输出,即为重排后的结果。
下面是一个示例代码:
```cpp
#include <iostream>
#include <queue>
using namespace std;
void rearrangeTrain(vector<int>& train) {
queue<int> q;
int n = train.size();
// 将火车车厢编号依次入队
for (int i = 0; i < n; i++) {
q.push(train[i]);
}
// 按照出队顺序输出车厢编号
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
}
int main() {
vector<int> train = {3, 1, 2};
rearrangeTrain(train);
return 0;
}
```
运行以上代码,输出结果为:3 1 2,表示重排后的火车车厢顺序为3、1、2。
相关问题
火车车厢重排队列c++
火车车厢重排队列问题可以使用栈来解决。具体步骤如下:
1. 读入原始车厢序列,保存在一个数组中。
2. 定义一个栈,用于辅助重排车厢。
3. 从左到右依次遍历原始车厢序列,对于每一个车厢,执行以下操作:
a. 若当前车厢是目标车厢序列中下一个要进站的车厢,则直接将其进站。
b. 若当前车厢不是目标车厢序列中下一个要进站的车厢,则将其压入栈中。
4. 当遍历完整个原始车厢序列后,如果栈不为空,则依次将栈中的车厢出栈并进站,直到栈为空。
5. 如果栈已经为空且进站序列中的车厢数量等于原始车厢序列中的车厢数量,则说明重排成功,返回true;否则返回false。
以下是C++代码实现:
```c++
#include <iostream>
#include <stack>
using namespace std;
bool checkOrder(int n, int ori[], int tar[]) {
stack<int> s;
int i = 0, j = 0; // i指向原始车厢序列,j指向目标车厢序列
while (i < n) {
if (ori[i] == tar[j]) { // 当前车厢是目标车厢序列中下一个要进站的车厢
i++;
j++;
} else if (!s.empty() && s.top() == tar[j]) { // 栈顶车厢是目标车厢序列中下一个要进站的车厢
s.pop();
j++;
} else { // 将当前车厢压入栈中
s.push(ori[i]);
i++;
}
}
while (!s.empty() && s.top() == tar[j]) { // 栈中剩余车厢出栈并进站
s.pop();
j++;
}
return j == n; // 进站序列中的车厢数量等于原始车厢序列中的车厢数量,则重排成功
}
int main() {
int n;
cin >> n;
int ori[n], tar[n];
for (int i = 0; i < n; i++) {
cin >> ori[i];
}
for (int i = 0; i < n; i++) {
cin >> tar[i];
}
if (checkOrder(n, ori, tar)) {
cout << "Possible" << endl;
} else {
cout << "Impossible" << endl;
}
return 0;
}
```
c++ 优先队列实现代码
C++中的优先队列是一种特殊的队列,它的元素按照一定的优先级进行排序。在C++中,可以使用STL库中的priority_queue来实现优先队列。
下面是一个简单的C++代码示例,演示了如何使用优先队列实现一个最大堆:
```cpp
#include <iostream>
#include <queue>
int main() {
// 创建一个优先队列,默认为最大堆
std::priority_queue<int> pq;
// 向优先队列中插入元素
pq.push(10);
pq.push(30);
pq.push(20);
// 访问队列中的最大元素
std::cout << "队列中的最大元素为:" << pq.top() << std::endl;
// 弹出队列中的最大元素
pq.pop();
// 再次访问队列中的最大元素
std::cout << "弹出一个元素后,队列中的最大元素为:" << pq.top() << std::endl;
return 0;
}
```
在上面的代码中,我们首先包含了`<iostream>`和`<queue>`头文件,分别用于输入输出和使用优先队列。然后,我们创建了一个`std::priority_queue<int>`对象`pq`,默认为最大堆。
接下来,我们使用`push()`函数向优先队列中插入元素。然后,使用`top()`函数访问队列中的最大元素,并使用`pop()`函数弹出队列中的最大元素。
注意,优先队列默认是按照元素的大小进行排序的,对于基本数据类型,按照从大到小的顺序排列。如果要实现最小堆,可以使用`std::greater`作为第二个模板参数,例如`std::priority_queue<int, std::vector<int>, std::greater<int>>`。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)