c语言队列实现火车车厢重排

火车车厢重排问题是一个经典的队列应用问题，可以用队列来实现。

具体实现步骤如下：

1. 定义一个队列，用来存储火车车厢的编号。

2. 输入火车车厢的编号，将其依次加入队列中。

3. 定义一个栈，用来存储中转站的编号。

4. 从队列中取出一个车厢，如果它的编号等于当前期望的编号，则直接放入出站序列中，否则将其放入栈中。

5. 重复步骤4，直到队列为空。

6. 如果栈不为空，则从栈中取出一个车厢，判断它的编号是否等于当前期望的编号，如果是则放入出站序列中，否则继续将其放回栈中。

7. 重复步骤6，直到栈为空。

最后得到的出站序列就是火车车厢的重排结果。

下面是一个简单的 C 语言队列实现火车车厢重排的示例代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// 定义队列结构体
typedef struct Queue {
    int data[MAX_SIZE];
    int front;  // 队首指针
    int rear;   // 队尾指针
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = q->rear = 0;
}

// 判断队列是否为空
int isEmpty(Queue *q) {
    return q->front == q->rear;
}

// 判断队列是否已满
int isFull(Queue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

// 入队
int enqueue(Queue *q, int x) {
    if (isFull(q)) {
        return 0;  // 队列已满，无法入队
    }
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return 1;
}

// 出队
int dequeue(Queue *q, int *x) {
    if (isEmpty(q)) {
        return 0;  // 队列为空，无法出队
    }
    *x = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return 1;
}

// 定义栈结构体
typedef struct Stack {
    int data[MAX_SIZE];
    int top;  // 栈顶指针
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
int isStackEmpty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
int isStackFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈
int push(Stack *s, int x) {
    if (isStackFull(s)) {
        return 0;  // 栈已满，无法入栈
    }
    s->data[++s->top] = x;
    return 1;
}

// 出栈
int pop(Stack *s, int *x) {
    if (isStackEmpty(s)) {
        return 0;  // 栈为空，无法出栈
    }
    *x = s->data[s->top--];
    return 1;
}

int main() {
    int n, i, x, expected = 1;
    Queue q;     // 定义队列
    Stack s;     // 定义栈
    initQueue(&q);  // 初始化队列
    initStack(&s);  // 初始化栈

    printf("请输入火车车厢的数量：");
    scanf("%d", &n);

    printf("请输入%d个火车车厢的编号：\n", n);
    for (i = 0; i < n; i++) {
        scanf("%d", &x);
        enqueue(&q, x);  // 将车厢编号入队
    }

    while (!isEmpty(&q)) {
        dequeue(&q, &x);  // 从队列中取出一个车厢
        if (x == expected) {
            printf("车厢%d直接出站\n", x);
            expected++;  // 更新期望编号
        } else {
            while (!isStackEmpty(&s) && s.data[s.top] == expected) {
                pop(&s, &x);  // 从栈中取出一个车厢
                printf("车厢%d从中转站出站\n", x);
                expected++;  // 更新期望编号
            }
            push(&s, x);  // 将车厢放入中转站
        }
    }

    while (!isStackEmpty(&s)) {
        pop(&s, &x);  // 从栈中取出一个车厢
        if (x != expected) {
            printf("无法重排\n");
            return 0;
        }
        printf("车厢%d从中转站出站\n", x);
        expected++;  // 更新期望编号
    }

    printf("重排成功\n");
    return 0;
}