【PTA数据结构 | C语言版】用两个栈实现队列

本专栏持续输出数据结构题目集，欢迎订阅。

题目

一个队列（先进先出结构）可以用两个堆栈（后进先出结构）来实现，方法如下：

1.从两个空堆栈 s1 和 s2 开始。
2.当元素 e 入队时，它实际上是被推入到 s1。
3.当我们需要出队时，首先检查 s2。如果 s2 是空的，则把 s1 中的元素全部导入 s2，即将每个元素从 s1​ 弹出后马上推入 s2​。然后从 s2​ 中弹出元素 —— s2 顶端元素一定是第一个进入 s1 的，所以是应该出列的第一个元素。

假设每个堆栈的推入和弹出操作都用 1 个单位时间，请你给出每个出队操作所花的时间。

输入格式：
输入首先在一行中给出一个正整数 N（≤10^3 ），是操作数量。随后 N 行，每行按以下格式给出一个操作：

操作 元素

其中 操作 或者是 I 表示入队，或者是 O 表示出队。每个 I 后面跟的 元素 是一个不超过 10^6 的正整数。O 操作后面不跟任何元素。

题目保证至少有一个 O 操作。

输出格式：
对每个出队操作，在一行中输出出队的那个元素和这出队操作所花费的单位时间数量，其间以 1 个空格分隔，行首尾不得有多余空格。
若出队操作被调用时队列是空的，则在对应行中输出 ERROR。

输入样例：
10
I 20
I 32
O
I 11
O
O
O
I 100
I 66
O

输出样例：
20 5
32 1
11 3
ERROR
100 5

题目引用自攀拓考试真题（2023年夏季）。

代码

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

#define MAX_STACK_SIZE 1000

// 堆栈结构体定义
typedef struct {
    int data[MAX_STACK_SIZE];
    int top;
} Stack;

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

// 入栈操作
void push(Stack *s, int elem) {
    s->data[++(s->top)] = elem;
}

// 出栈操作，返回栈顶元素
int pop(Stack *s) {
    return s->data[(s->top)--];
}

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

int main() {
    int N;
    scanf("%d", &N);
    
    Stack s1, s2;
    initStack(&s1);
    initStack(&s2);
    
    for (int i = 0; i < N; i++) {
        char op[2];
        scanf("%s", op);
        
        if (op[0] == 'I') {
            int elem;
            scanf("%d", &elem);
            push(&s1, elem);
        } else if (op[0] == 'O') {
            // 处理出队操作
            if (isEmpty(&s1) && isEmpty(&s2)) {
                printf("ERROR\n");
            } else {
                int time = 0;
                // 若s2为空，将s1所有元素导入s2
                if (isEmpty(&s2)) {
                    while (!isEmpty(&s1)) {
                        int elem = pop(&s1);
                        push(&s2, elem);
                        time += 2;  // 弹出s1和压入s2各1单位时间
                    }
                }
                // 从s2弹出元素，耗时1单位
                int outElem = pop(&s2);
                time += 1;
                printf("%d %d\n", outElem, time);
            }
        }
    }
    
    return 0;
}