【卡码网C++基础课 19.洗盘子】

题目描述与分析

题目描述：
在餐厅里，洗盘子的工作需要使用到栈这种数据结构。
假设你手里有一个盘子堆放区。现在需要模拟洗盘子的过程，每个盘子都有一个编号。
盘子堆放区操作说明：
1.当操作为 1 时，表示从盘子堆放区拿走顶部的盘子清洗。
2.当操作为 2 时，表示有未洗的盘子放入盘子堆放区。
在一系列操作之后，你需要回答：下一个清洗的盘子编号？

输入描述：
第一行有一个整数 n，代表初始盘子堆放区中盘子的数量为 n。
第二行有 n 个整数，代表了盘子的编号，同时整数之间的顺序也代表了未洗盘子加入盘子堆放区的顺序。
第三行为一个整数 m，代表接下来将会有 m 次操作。
接下来一共有 m 行，代表共有 m 次操作。
如果是操作 1，那么该行只会有一个数字 1，代表有一个盘子被拿走清洗。
如果是操作 2，那么该行有两个数字，第一个数字 2 表示有未洗的盘子加入，第二个数字代表未洗的盘子编号。

输出描述：
输出共一行，为下一个该清洗的盘子编号。 如果没有下一个该清洗的盘子，那么请输出 “All the dishes have been washed.”

输入示例：

5
1001 1002 1003 1004 1005
3
1
1
2 1006

输出示例：

1006

一、栈

栈的操作实际上和洗盘子的过程是类似的，洗盘子的过程中，会拿出待清洗那一摞盘子的最顶端的那个盘子，清洗之后将其放在已清洗区域，这对于待清洗盘子来说是出栈，对于已清洗区域来说，是入栈（进栈），具体的过程可以看下面的图示：

栈这种结构只能在一侧（栈顶那一侧）进行插入和删除操作，而且是后进先出LIFO(后进入栈的元素离栈顶比较近，先出来)，允许进行插入和删除的那一端是栈顶，与之对应的另一端是栈底, 如果一个栈不包含任何元素，这个栈被称为空栈。

在计算机领域，栈的应用也十分广泛，比如浏览器的历史回退和编写文档时的“撤销”操作。

二、栈的操作

C++标准模板库（STL）提供了stack容器来实现栈的操作。想要使用它，只需要引入<stack>头文件即可。

#include <stack> // 引入stack头文件

然后就可以通过stack数据类型 栈名称这样的形式来创建一个栈并进行操作了

 stack<int> st; // 创建一个int类型的栈

主要操作有以下几种：
1.压入元素 (push)：
使用 s.push(value) 方法将元素压入栈顶，stack 会根据栈的后进先出的原则，最后压入的元素最先被弹出。

2.弹出元素 (pop)：
使用 s.pop() 移除栈顶的元素，但注意 pop 只是移除栈顶元素，并不会返回它。要访问栈顶元素，需要先使用 top。

3.获取栈顶元素 (top)：
s.top() 返回当前栈顶元素的引用，允许你查看或修改栈顶元素，但不会移除它。

4.判断栈是否为空 (empty)：
使用 s.empty() 来判断栈是否为空，返回值为布尔类型。

5.获取栈的大小 (size)：
s.size() 返回栈中元素的数量。

#include <iostream>
#include <stack>
using namespace std;

int main() {
    // 创建一个int类型的栈
    stack<int> s;

    // 压入元素
    s.push(10);
    s.push(20);
    s.push(30);

    // 获取栈顶元素
    cout << "Stack top: " << s.top() << endl;  // 输出 30

    // 弹出栈顶元素
    s.pop();

    // 再次获取栈顶元素
    cout << "Stack top after pop: " << s.top() << endl;  // 输出 20

    // 获取栈的大小
    cout << "Stack size: " << s.size() << endl;  // 输出 2

    // 判断栈是否为空
    if (s.empty()) {
        cout << "Stack is empty" << endl;
    } else {
        cout << "Stack is not empty" << endl;
    }

    return 0;
}

三、代码编写

我们先把代码的基础结构写出来，使用栈的时候需要引入头文件

#include <iostream>
#include <stack> // 引入stack头文件
using namespace std;
int main() {
  int n, val;
  cin >> n; // 输入盘子的数量
}

然后我们需要定义一个栈，将输入的n个整数push到栈中，这代表着未洗盘子加入盘子堆放区的顺序。

stack<int> st; // 初始化一个栈结构
while (n--) { 
    cin >> val; // 输入盘子的编号
    st.push(val); // 将输入的n个盘子的编号push到栈中
}

接下来接收m和m个整数的输入，表示对盘子的操作，如果数字为1，表示盘子被拿去清洗，即出栈操作，如果数字为2，表示有新的盘子加入到待清洗区域中，即入栈操作。

cin >> m; // 接收m，表示m次操作
while(m--) {
  cin >> opt; // 接收操作的指令，1表示出栈，2表示入栈
  if (opt == 1) { // 如果指令为1， 将栈顶元素出栈
    st.pop();
  } else if(opt == 2) { // 如果指令为2，将输入的数字入栈
    cin >> num;
    st.push(num);
  }
}

但是在这里需要注意的一点是，如果栈已经成为空栈，再输入1，也无法弹出栈顶元素，所以需要判断栈是否为空。

// 如果指令为1，并且栈不为空的话，才弹出栈顶元素。
if (opt == 1 && !st.empty()) st.pop();

当执行完所有操作后，如果没有下一个该清洗的盘子，输出 “All the dishes have been washed.”， 如果有，则输出下一个待清洗的盘子编号。

// 如果已经为空栈
if (st.empty()) {
  cout << "All the dishes have been washed." << endl;
} else {// 否则，输出下一个待清洗的盘子编号，即栈顶元素的值
  cout << st.top() << endl;
}

完整代码如下：

#include <iostream>
#include <stack>
using namespace std;
int main() {
    int n, m, opt, val, num;
    cin >> n;
    stack<int> st; // 新构建一个栈结构
    while (n--) {
        cin >> val;
        st.push(val); // 将输入的盘子编号使用push操作推到栈中
    }
    cin >> m;
    while (m--) {
        cin >> opt;
        // 注意这里如果栈已经为空就不能再弹出了，所以要判断是否为空
        if (opt == 1 && !st.empty()) st.pop(); // 使用pop操作将栈顶元素推出
        else {
            cin >> num;
            st.push(num);
        }
    }
  // 使用empty()操作判断是否为空栈
    if (st.empty()) cout << "All the dishes have been washed." << endl;
    else cout << st.top() << endl; // 使用top()获取栈顶元素
}