0%

栈的应用——判断pop序列是否合理

栈有着广泛的应用,比如逆波兰表达式,表达式求值,迷宫问题求解,程序调用等,不过这些问题今天都不涉及哈哈哈哈。关于程序执行期间,各个函数的相互调用使用的调用栈,可以参考这里

也许在上数据结构这门课的时候,经常遇到一个问题,一个栈压入一个序列,随缘pop,判断哪个是合理的pop,哪个是不合理的pop,之前都是脑内演算。很巧的今天我在刷题期间也遇到了,记录一下如何用代码判断pop序列是否合理。

题目

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.

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

众所周知,栈是先进先出的一种数据结构,进栈为push,出栈为pop。题目的大概意思就是给定栈的最大空间,压入的序列和待检查的pop序列,因为栈是随缘pop的,判断哪个pop序列是正确的,哪个pop序列是错误的。

分析

脑内演算

  • 对于序列 1, 2, 3, 4, 5, 6, 7, 很容易得到栈是如何工作的,即压入一个元素立刻弹出即可。push 1,pop 1,push 2,pop 2,一直到push 7,pop 7。
  • 对于序列 5, 6, 4, 3, 7, 2, 1,也可以得到栈的工作顺序为:push 1, 2, 3, 4, 5,而后pop 5,而后push 6 pop 6,pop 4,pop 3,push 7 pop 7,pop 2,pop 1。
  • 对于序列 3, 2, 1, 7, 5, 6, 4,如果pop 7后,后面的顺序必然是 6,5,4而不可能是5,6,4。因此这个序列是错误的。
  • 对于序列 7, 6, 5, 4, 3, 2, 1,在栈空间为5的情况下,不可能第一次就pop 7,因此这个序列是错误的。

一般化

在脑内演算后,也很容易发现题的难点在于不确定性的pop,可能在第一次pop,也可能在第三次pop,且每次pop几个元素也是不确定的。

我们实现知道了元素的进栈顺序,是1,2,3,4,…,$N$这样的顺序序列,所以,如果想办法按着它给出的序列模拟压栈和弹栈,如果能模拟出来,说明序列正确,模拟不出来说明序列错误。

  • 第一步,创建一个序列,读取题目示例输入的序列:

    for (int i = 1; i <= n; i++)
    scanf("%d", &arr[i]);
  • 第二步,创建一个栈,并按元素的输入顺序组织元素进栈,开始按读取序列元素的顺序进行压栈和弹栈。

  • 对输入序列设立标志位,并初始化标志位为1。当刚进栈的元素和输入序列标志位的元素相等时,说明此时元素要弹栈,则执行弹栈操作,且标志位自增向后移动;若不相等,则继续组织进栈,直到进栈元素和输入序列中标志位的元素相等。若一直不相等,则表明此序列错误。因此核心算法程序如下:

    // 设立标志位
    int pos = 1;
    for(int j = 1; j <= n; j++) {
    // 按元素顺序组织进栈
    s.push(j);
    // 超过栈允许的最大空间
    if(s.size() > m) break;
    // 按序列元素的弹栈顺序开始模拟
    // 栈非空且栈顶元素和当前标志位的元素相等
    while(!s.empty() && s.top() == arr[pos]) {
    // 弹栈
    s.pop();
    // 标志位自增
    pos++;
    }
    }

程序

得到最终的程序如下:

#include <iostream>
#include <stack>

using namespace std;

int arr[1002];

int main(int argc, char const *argv[])
{
int m, n, k;
cin >> m >> n >> k;
for (int j = 0; j < k; j++)
{
for (int i = 1; i <= n; i++)
scanf("%d", &arr[i]);
int flag = 0, pos = 1;
stack <int> s;
for (int i = 1; i <= n; i++)
{
s.push(i);
if (s.size() > m) break;
while (!s.empty() && s.top() == arr[pos])
{
s.pop();
pos += 1;
}
}
if (pos == n + 1) flag = 1;
if (flag == 1) printf("YES\n");
else printf("NO\n");
}
return 0;
}

明人不说暗话,如果你感觉我写的还可以对你有帮助的话,Could you buy me a yogurt? ,文末也可评分。如果这样不行的话,我,秦始皇,打钱。

欢迎订阅我的文章