编程题 02-线性结构3 Reversing Linked List【PAT】

编程练习题目集目录

题目

  Given a stack which can keep $M$ numbers at most. Push $N$ numbers in the order of $1,2,3,...,N$ and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if $M$ is $5$ and $N$ is $7$, we can obtain $1,2,3,4,5,6,7$ from the stack, but not $3,2,1,7,5,6,4$.

输入格式

  Each input file contains one test case. For each case, the first line contains $3$ numbers (all no more than $1000$): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

输出格式

  For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

输入样例

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

输出样例

YES
NO
NO
YES
NO

题解

解题思路

  创建一个空栈，对于弹出序列中的每个元素，使用指针 $i$ 从头到尾遍历。在每次循环中，先尝试弹出栈顶元素，如果栈顶元素等于当前处理的弹出序列元素，则弹出栈顶元素，指针 $i$ 移动到下一个位置。如果栈顶元素不等于当前处理的元素，并且栈未满，且还有数字未压入，则压入下一个数字，并更新 $next\_num$。如果栈满且无法压入新的数字，或者所有数字已压入但栈顶元素仍不匹配当前处理的元素，则该序列无法生成。如果整个序列都处理完毕且没有出现无法生成的情况，则该序列合法。

完整代码

#include <iostream>
using namespace std;

// 定义栈节点结构体
struct StackNode {
    int value;                 // 节点存储的值
    StackNode* next;           // 指向下一个节点的指针
    StackNode(int val) : value(val), next(nullptr) {}  // 构造函数
};

// 定义链表栈类
class LinkedListStack {
public:
    // 构造函数，初始化栈顶指针为空
    LinkedListStack() : top(nullptr) {}

    // 析构函数，释放栈中所有节点的内存
    ~LinkedListStack() {
        while (!isEmpty()) {
            pop();
        }
    }

    // 压栈操作：将一个新值压入栈顶
    void push(int val) {
        StackNode* newNode = new StackNode(val);  // 创建新节点
        newNode->next = top;                     // 新节点的下一个节点为当前栈顶
        top = newNode;                           // 更新栈顶为新节点
    }

    // 出栈操作：移除栈顶元素
    void pop() {
        if (!isEmpty()) {                        // 如果栈不为空
            StackNode* temp = top;               // 保存当前栈顶节点
            top = top->next;                     // 更新栈顶为下一个节点
            delete temp;                         // 释放原栈顶节点内存
        }
    }

    // 获取栈顶元素的值
    int getTop() {
        if (!isEmpty()) {                        // 如果栈不为空
            return top->value;                   // 返回栈顶元素的值
        }
        return -1;                               // 栈为空时返回-1（或抛出异常）
    }

    // 判断栈是否为空
    bool isEmpty() {
        return top == nullptr;                   // 栈顶为空则栈为空
    }

    // 获取栈中元素的数量
    int size() {
        int count = 0;
        StackNode* current = top;                // 从栈顶开始遍历
        while (current != nullptr) {
            count++;                             // 计数器加1
            current = current->next;             // 移动到下一个节点
        }
        return count;                            // 返回计数器的值
    }

private:
    StackNode* top;                              // 栈顶指针
};

// 验证弹出序列是否合法的函数
bool isPopSequence(const int* seq, int M, int N) {
    LinkedListStack stack;                       // 创建链表栈对象
    int next_num = 1;                            // 下一个要压入栈的数字
    int i = 0;                                   // 当前处理的弹出序列位置

    while (i < N) {                              // 遍历整个序列
        // 尝试弹出所有可能匹配的元素
        while (!stack.isEmpty() && stack.getTop() == seq[i]) {
            stack.pop();                         // 弹出栈顶元素
            i++;                                 // 移动到序列的下一个位置
        }
        if (i >= N) break;                       // 如果序列处理完毕，退出循环

        // 如果无法压入更多元素，则序列不可能
        if (next_num > N) {
            return false;                        // 返回不合法
        }

        // 压入下一个元素
        if (stack.size() < M) {                  // 如果栈未满
            stack.push(next_num);                // 压入下一个数字
            next_num++;                          // 更新下一个要压入的数字
        } else {
            // 栈满且无法压入所需元素
            return false;                        // 返回不合法
        }
    }

    return true;                                 // 序列处理完毕且合法
}

int main(void) {
    int M, N, K;                                 // 栈容量、数字个数、序列个数
    cin >> M >> N >> K;                          // 读取输入

    for (int i = 0; i < K; ++i) {                // 对每个序列进行处理
        int* seq = new int[N];                   // 动态分配序列数组
        for (int j = 0; j < N; ++j) {
            cin >> seq[j];                       // 读取序列中的每个数字
        }
        if (isPopSequence(seq, M, N)) {          // 验证序列是否合法
            cout << "YES" << endl;               // 合法输出YES
        } else {
            cout << "NO" << endl;                // 不合法输出NO
        }
        delete[] seq;                            // 释放动态分配的内存
    }

    return 0;                                    // 程序结束
}