c语言队列实现火车车厢重排
时间: 2023-09-04 11:11:11 浏览: 94
火车车厢重排问题是一个经典的算法问题,可以使用队列来实现。具体实现步骤如下:
1. 定义一个队列结构体,包含一个数组和队首、队尾指针;
2. 将原始车厢序列入队(将数组元素依次入队);
3. 定义一个辅助栈,用于存储待排序车厢;
4. 从队列中取出一个车厢,如果该车厢的编号等于当前待排序的车厢编号,则将其输出,否则将其压入辅助栈;
5. 重复第4步,直到队列为空;
6. 将辅助栈中的车厢依次出栈,如果其编号等于当前待排序车厢编号,则将其输出;
7. 重复第6步,直到辅助栈为空。
以下是 C 语言队列实现火车车厢重排的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct queue {
int data[MAX_SIZE];
int front; // 队首指针
int rear; // 队尾指针
} Queue;
int main() {
Queue q;
int n, i, j, k;
int train[MAX_SIZE], tmp[MAX_SIZE];
// 初始化队列
q.front = q.rear = -1;
// 输入车厢数量
printf("请输入车厢数量:");
scanf("%d", &n);
// 输入车厢编号
printf("请输入车厢编号:");
for (i = 0; i < n; i++) {
scanf("%d", &train[i]);
q.data[++q.rear] = train[i];
}
// 初始化辅助栈
int top = -1;
// 依次取出队列中的车厢
for (i = 0; i < n; i++) {
k = q.data[q.front + 1];
// 如果当前车厢编号与待排序车厢编号相同,则输出
if (k == train[i]) {
printf("%d ", k);
q.front++; // 出队
} else {
// 否则将当前车厢压入辅助栈
tmp[++top] = k;
q.front++; // 出队
i--; // 重新检查当前车厢
}
}
// 依次取出辅助栈中的车厢
while (top >= 0) {
k = tmp[top--];
// 如果当前车厢编号与待排序车厢编号相同,则输出
if (k == train[i]) {
printf("%d ", k);
i++; // 检查下一个车厢
} else {
// 否则将当前车厢压入辅助栈
tmp[++top] = k;
}
}
return 0;
}
```
相关推荐
![](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)