Java栈序列匹配问题：判断数字序列是否存在于栈正/逆序中

给定一个数字栈和一个整数，需编写Java方法判断该整数的所有数字是否作为连续序列出现在栈中（可从栈顶到栈底或栈底到栈顶查看）。现有代码返回结果部分错误：例如栈[1,2,3]（3为栈顶），判断数字12时返回错误结果；但栈[3,2,1]（1为栈顶）时结果正确。问题出在栈的逆序处理部分，逻辑或运算未生效，请问遗漏了什么？
注：StackX为自定义栈类，包含push、pop、peek、isEmpty、isFull、getSize等通用操作。

原代码 #

// return a string with the stack values
public static String StackValues(StackX S)
{
    String seq = "";
    while (!S.isEmpty())
    {
        long l = S.pop();
        seq += Long.toString(l);
    }
    return seq;
}

// checks if a string contains a substring
public static boolean sub(String string, String substring)
{
    int index = string.indexOf(substring);
    if (index==-1)
        return false;
    else
        return true;
}

// returns a reverse of the string
public static StackX StackReverse(StackX S)
{
    StackX newStack = new StackX(S.getStackMaxSize());
    while (!S.isEmpty())
    {
        newStack.push(S.pop());
    }
    return newStack;
}

public static boolean isSeq(StackX S, int num)
{
    String theNum = Integer.toString(num);
    String theStack = StackValues(S);
    StackX temp = new StackX(S.getStackMaxSize());
    temp = StackReverse(S);
    String theStackReversed = StackValues(temp);

    if (sub(theStack, theNum)==true || sub(theStackReversed, theNum)==true)
        return true;
    else
        return false;
}

错误原因 #

你的代码核心问题是操作栈时会直接清空原栈，导致后续操作失效：

1. 调用StackValues(S)时，通过pop()把栈S的元素全部弹出，此时S已经是空栈。
2. 之后调用StackReverse(S)时，S为空，返回的temp自然也是空栈，theStackReversed为空字符串，逻辑或的后半部分永远为false。
3. 另外，StackValues方法破坏了原栈的结构，判断操作不应该修改原栈内容。

修正方案 #

解决思路是遍历栈时保留原栈结构，以下是两种可行的修正方式：

方式一：遍历后还原原栈结构 #

修改StackValues和StackReverse方法，遍历栈后将元素放回原栈，避免破坏原结构：

public static String StackValues(StackX S)
{
    String seq = "";
    StackX temp = new StackX(S.getStackMaxSize());
    // 弹出元素生成字符串，同时存入临时栈
    while (!S.isEmpty())
    {
        long l = S.pop();
        seq += Long.toString(l);
        temp.push(l);
    }
    // 把临时栈元素放回原栈，恢复结构
    while (!temp.isEmpty())
    {
        S.push(temp.pop());
    }
    return seq;
}

public static StackX StackReverse(StackX S)
{
    StackX newStack = new StackX(S.getStackMaxSize());
    StackX temp = new StackX(S.getStackMaxSize());
    // 先把原栈元素移到临时栈，保留原栈结构
    while (!S.isEmpty())
    {
        long l = S.pop();
        temp.push(l);
        newStack.push(l);
    }
    // 恢复原栈
    while (!temp.isEmpty())
    {
        S.push(temp.pop());
    }
    return newStack;
}

public static boolean isSeq(StackX S, int num)
{
    String theNum = Integer.toString(num);
    String theStack = StackValues(S);
    String theStackReversed = StackValues(StackReverse(S));

    return sub(theStack, theNum) || sub(theStackReversed, theNum);
}

// 简化sub方法
public static boolean sub(String string, String substring)
{
    return string.indexOf(substring) != -1;
}

方式二：直接反转字符串（更高效） #

不需要单独反转栈，生成原栈字符串后直接反转字符串即可：

public static String StackValues(StackX S)
{
    String seq = "";
    StackX temp = new StackX(S.getStackMaxSize());
    while (!S.isEmpty())
    {
        long l = S.pop();
        seq += Long.toString(l);
        temp.push(l);
    }
    // 恢复原栈
    while (!temp.isEmpty())
    {
        S.push(temp.pop());
    }
    return seq;
}

public static boolean isSeq(StackX S, int num)
{
    String theNum = Integer.toString(num);
    String stackStr = StackValues(S);
    // 直接反转字符串得到栈底到栈顶的序列
    String reversedStackStr = new StringBuilder(stackStr).reverse().toString();
    
    return stackStr.contains(theNum) || reversedStackStr.contains(theNum);
}

内容的提问来源于stack exchange，提问作者user2899944