利用栈c++假设火车调度n节硬席或软席,输出调度操作序列,使所有软席在硬席之前
时间: 2024-05-03 08:21:34 浏览: 11
算法思路:
1. 从输入中读取火车调度序列;
2. 创建一个空栈,用于暂存调度序列;
3. 遍历调度序列,对于每一节车厢,进行以下操作:
- 如果该车厢是软席,则将其入栈;
- 如果该车厢是硬席,则先将栈中所有软席出栈,再将该硬席入栈;
4. 最后,将栈中剩余的软席依次出栈,输出调度序列即可。
C++代码实现:
```c++
#include <iostream>
#include <stack>
using namespace std;
int main() {
int n;
cin >> n;
stack<int> s;
int x;
for (int i = 0; i < n; i++) {
cin >> x;
if (x == 0) { // 软席
s.push(x);
} else { // 硬席
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << x << " ";
}
}
while (!s.empty()) { // 输出栈中剩余的软席
cout << s.top() << " ";
s.pop();
}
return 0;
}
```
示例输入:
```
8
0 0 1 0 1 1 0 1
```
示例输出:
```
0 0 0 1 0 1 1 1
```
时间复杂度:$O(n)$,其中 $n$ 为车厢数量。