1. 列车厢调动

1.1 实验内容

有三条平行的列车轨道（1、2、3）以及 1-3 和 2-3 两段连接轨道。现有一列车厢停在1号轨道上，请利用两条连接轨道以及3号轨道，将车厢按照要求的顺序转移到2号轨道。

1.2 实验目的

掌握栈的基本操作，入栈和出栈，能够应用栈来解决问题。

1.3 程序清单

▶

Code

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

#define MAX_CARS 100

/* 栈的定义 */
typedef struct stack_s {
    char data[MAX_CARS];
    int             top;
} stack_t;

/**
 * @brief 初始化栈
 * 
 * @param s 栈指针
 */
void init_stack(stack_t *s)
{
    s->top = -1;
}

/**
 * @brief 判断栈是否为空
 * 
 * @param s 栈指针
 * @return true  空栈
 * @return false 非空栈
 */
bool is_empty(stack_t *s)
{
    return s->top == -1;
}

/**
 * @brief 判断栈是否已满
 * 
 * @param s 栈指针
 * @return true  满栈
 * @return false 非满栈
 */
bool is_full(stack_t *s)
{
    return s->top == MAX_CARS - 1;
}

/**
 * @brief 入栈操作
 * 
 * @param s      栈指针
 * @param data   数据
 * @return true  成功
 * @return false 失败
 */
bool push(stack_t *s, int data)
{
    if (is_full(s)) {
        return false;
    }

    s->data[++(s->top)] = data;
    return true;
}

/**
 * @brief 出栈操作
 * 
 * @param s      栈指针
 * @param data   数据
 * @return true  成功
 * @return false 失败
 */
bool pop(stack_t *s, int *data)
{
    if (is_empty(s)) {
        return false;
    }

    *data = s->data[(s->top)--];
    return true;
}

/**
 * @brief 获取栈顶元素
 * 
 * @param s      栈指针
 * @param data   数据
 * @return true  成功
 * @return false 失败
 */
bool peek(stack_t *s, int *data)
{
    if (is_empty(s)) {
        return false;
    }

    *data = s->data[s->top];
    return true;
}

/**
 * @brief 模拟列车车厢重排
 * 
 * @param n 车厢总数
 * @param source 1 号轨道的初始顺序
 * @param target 2 号轨道的目标顺序
 */
void train_shunting(int n, char source[], char target[])
{
    stack_t track;  // 3 号轨道
    init_stack(&track);

    int source_idx = 0;  // 1 号轨道当前序列的索引
    int target_idx = 0;  // 2 号轨道目标序列的索引

    // 遍历目标序列中的每一节车厢
    for (target_idx = 0; target_idx < n; target_idx++) {
        int expected_car = target[target_idx];
        int top_car;

        while (1) {
            // 1. 栈顶就是期望车厢 -> 从 3 号移到 2 号
            if (!is_empty(&track) && peek(&track, &top_car) && top_car == expected_car) {
                pop(&track, &top_car);
                printf("3->2\n");
                break;
            }
            // 2. 1 号轨道当前车厢正好是期望车厢 -> 直接移到 2 号
            else if (source_idx < n && source[source_idx] == expected_car) {
                printf("1->2\n");
                source_idx++;
                break;
            }
            // 3. 当前车厢不是期望的，暂存到 3 号轨道
            else if (source_idx < n) {
                push(&track, source[source_idx]);
                printf("1->3\n");
                source_idx++;
            }
            // 4. 1 号轨道已空且栈顶仍不匹配 -> 无法完成调度
            else {
                printf("ERROR!\r\n");
                return;
            }
        }
    }
}

int main()
{
    // +1 用于 '\0'
    char source[MAX_CARS + 1];
    char target[MAX_CARS + 1];

    if (scanf("%s", &source) != 1 || scanf("%s", target) != 1) {
        printf("Invalid input!\r\n");
        return -1;
    }

    int n = strlen(source);
    if (n == 0 || n > MAX_CARS) {
        return -1;
    }

    train_shunting(n, source, target);
    return 0;
}

1.4 调试步骤

1. 输入测试数据

ABC
CBA

2. 程序输出

1->3
1->3
1->2
3->2
3->2

1.5 分析与思考

• 空间复杂度：$O(n)$

• 时间复杂度：$O(n)$

2. 银行业务队列简单模拟

2.1 实验内容

设某银行有 A、B 两个业务窗口，且处理业务的速度不一样，其中 A 窗口处理速度是 B 窗口的2倍，即当 A 窗口每处理完2个顾客时，B 窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A 窗口顾客优先输出。

输入给出顾客总数和每个顾客的编号。按照编号奇偶分别进入 A 窗口和 B 窗口排队。

2.2 实验目的

掌握队列的基本操作，入队和出队，能够应用队列来解决问题。

2.3 程序清单

▶

Code

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

#define MAX 1005

/* 队列结构 */
typedef struct queue_s {
    int data[MAX];
    int     front;
    int      rear;
} queue_t;

/**
 * @brief 初始化队列
 * 
 * @param q 
 */
void init(queue_t *q)
{
    q->front = q->rear = 0;
}

/**
 * @brief 判断队列是否为空
 * 
 * @param q 队列指针
 * @return true  空队列
 * @return false 非空队列
 */
bool is_empty(queue_t *q)
{
    return q->front == q->rear;
}

/**
 * @brief 入队
 * 
 * @param q 队列指针
 * @param x 值
 */
void enqueue(queue_t *q, int x)
{
    q->data[q->rear++] = x;
}

/**
 * @brief 出队
 * 
 * @param q 队列指针
 * @return int 返回值
 */
int dequeue(queue_t *q)
{
    return q->data[q->front++];
}

int main()
{
    int   n;
    int num;

    queue_t qA;
    queue_t qB;
    init(&qA);
    init(&qB);

    // 输入顾客总数及编号
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);

        if (num % 2) {
            enqueue(&qA, num);  // 奇数去 A 窗口
        } else {
            enqueue(&qB, num);  // 偶数去 B 窗口
        }
    }

    int first = 1;  // 控制输出空格

    // 模拟银行处理业务
    while (!is_empty(&qA) || !is_empty(&qB)) {
        // A窗口优先，每次最多处理2人
        if (!is_empty(&qA)) {
            if (!first) {
                printf(" ");
            }

            printf("%d", dequeue(&qA));
            first = 0;

            if (!is_empty(&qA)) {
                printf(" %d", dequeue(&qA));
            }
        }

        // B窗口每次处理1人
        if (!is_empty(&qB)) {
            if (!first) {
                printf(" ");
            }

            printf("%d", dequeue(&qB));
            first = 0;
        }
    }

    printf("\r\n");
    return 0;
}

2.4 调试步骤

1. 输入测试数据

8 2 1 3 9 4 11 13 15

2. 程序输出

1 3 2 9 11 4 13 15

2.5 分析与思考

• 空间复杂度：$O(n)$

• 时间复杂度：$O(n)$