剑指offer_chap4_22_栈的压入、弹出序列

《剑指 offer》第 4 章第 22 道面试题

问题描述

输入两个整数序列，第一个序列表示栈的压入顺序，判断第二个序列是否为该栈的弹出顺序，假设没有重复的数字

样例

[1, 2, 3, 4, 5]， [4, 5, 3, 2, 1] 返回 true
[1, 2, 3, 4, 5]， [4, 5, 3, 1, 2] 返回 false

解题思路

上面的例子中，4 先被弹出栈，说明 1、2、3 已经在栈中，输出顺序必然是 3、2、1，所以第一个为 true，第二个为 false。编写算法时，可以根据这个思路模拟栈的压入弹出操作。

代码

Java

这份代码是根据上面的思路写的，但因为 LintCode、LeetCode 都没有这道题，因此无法保证完全正确，看个思路就好。

public class Solution {

    public boolean isStackSequence(int[] input, int[] output) {
        if (input == null || output == null || input.length != output.length)
            return false;
        if (input.length == 0)
            return true;

        Stack stack = new Stack<>();

        int i, index = 0;
        for (int num : output) {
            if (!stack.isEmpty() && stack.peek() == num) {
                stack.pop();
                continue;
            }
            // 把 num 前面的数字压入栈
            for (i = index; i                 if (input[i] == num) {
                    index = i + 1;
                    break;
                } else 
                    stack.push(input[i]);
            }
            // 如果 input 里找不到 num，返回 false
            if (i == input.length)
                return false;
        }

        return true;
    }
}

C++

这份是作者本人的代码

class Solution {
public:
    bool IsPopOrder(const int* pPush, const int* pPop, int nLength)
    {
        bool bPossible = false;

        if(pPush != nullptr && pPop != nullptr && nLength > 0)
        {
            const int* pNextPush = pPush;
            const int* pNextPop = pPop;

            std::stack<int> stackData;

            while(pNextPop - pPop             {
                // 当辅助栈的栈顶元素不是要弹出的元素
                // 先压入一些数字入栈
                while(stackData.empty() || stackData.top() != *pNextPop)
                {
                    // 如果所有数字都压入辅助栈了，退出循环
                    if(pNextPush - pPush == nLength)
                        break;

                    stackData.push(*pNextPush);

                    pNextPush ++;
                }

                if(stackData.top() != *pNextPop)
                    break;

                stackData.pop();
                pNextPop ++;
            }

            if(stackData.empty() && pNextPop - pPop == nLength)
                bPossible = true;
        }

        return bPossible;
    }
};