首页 > 代码库 > 数据结构-栈的压入、弹出序列

数据结构-栈的压入、弹出序列

2024-07-05 02:52:00   223人阅读

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个顺序是否是该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1，2，3，4，5是某栈的压栈序列，序列4，5，3，2，1是该压栈序列对应的一个弹出序列，但是4，3，5，1，2就不可能是。

分析：首先利用图像进行形象化的理解。可以发现其压入的顺序并不是所有的一次性压入。同时要考虑栈是否为空。以及其长度。这段代码写的很痛苦，继续训练。

/*
剑指offer面试题22
*/
#include <iostream>
#include <stack>

using namespace std;

bool IsPopOrder(stack<int> pushOrder,stack<int> popOrder,int length,int* p){
    bool Possible = false;

    int num = 0;
    pushOrder.push(p[num]);

    if(popOrder.empty() || length <= 0){
        return false;
    }

    while(!popOrder.empty()){
        while(popOrder.top() != pushOrder.top()){
            if(num >= length){
                break;
            }
            pushOrder.push(p[num++]);
        }

        if(popOrder.top() != pushOrder.top()){
            break;
        }

        popOrder.pop();
        pushOrder.pop();
    }

    if(popOrder.empty()){
        Possible = true;
    }

    return Possible;
}

int main()
{
    stack<int> pushOrder;
    int p[5],pu[5];
    stack<int> popOrder;

    int n;
    for(int i=0;i<5;i++){
        cin >> n;
        p[i] = n;
    }

    for(int i=4;i>=0;i--){
        cin >> n;
        pu[i] = n;
    }

    for(int i=0;i<5;i++){
        popOrder.push(pu[i]);
    }

    bool result = IsPopOrder(pushOrder,popOrder,popOrder.size(),p);

    cout << result << endl;

    return 0;
}

 


联系
我们