当前位置: 代码迷 >> 编程 >> 栈的压进压出(判断栈的压出顺序是否合法)
  详细解决方案

栈的压进压出(判断栈的压出顺序是否合法)

热度:3492   发布时间:2013-02-26 00:00:00.0
栈的压入压出(判断栈的压出顺序是否合法)

(1)问题描述

题目描述:

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

输入:

每个测试案例包括3行:

第一行为1个整数n(1<=n<=100000),表示序列的长度。

第二行包含n个整数,表示栈的压入顺序。

第三行包含n个整数,表示栈的弹出顺序。

输出:

对应每个测试案例,如果第二个序列是第一个序列的弹出序列输出Yes,否则输出No


(2)程序实现

      栈的特点是后进先出,假设入栈的顺序是  1 2 3  4 5,出栈的顺序是:4 5 3 2 1,这样操作的顺序是:push 1, push 2,push 3,push 4,pop 4, push 5 , pop 5,pop 3, pop 2, pop 1。假设出栈的顺序是4 5  3  1 2,这种顺序是错误的,因为1比2先压入栈,所以2的出栈顺序应该是1之前,显然出栈顺序是错误的。

       判断思路:遍历出栈顺序中的元素,有两种情况  A:如果元素是栈顶的元素,则pop出来;B:如果不是栈顶元素,则根据入栈顺序将没入栈的元素push进栈,直到将该元素push栈中,然后将该元素pop出来,如果push完所有元素都没有找到该元素,那么这个出栈顺序是错误的。


#include <iostream>#include <stack> using namespace std; int main(){    int n;    while(cin>>n)    {        stack<int> s;        int* stack_in = new int[n];        int* stack_out = new int[n];        for(int i=0; i<n; ++i)            cin>>stack_in[i];        for(int i=0; i<n; ++i)            cin>>stack_out[i];        int i = 0;        bool isValid = false;//判断标志        for(int j=0; j<n; ++j)        {            //判断栈顶是否是该元素            if(s.size() != 0 && s.top() == stack_out[j])                s.pop();            else            {                bool find = false;                for(; i<n;++i)                {                    s.push(stack_in[i]);                    if(stack_in[i] == stack_out[j])                    {                        ++i;                        find = true;                        break;                    }                }                if(!find)                {                    isValid = true;                    break;                }                else                    s.pop();            }        }        if(isValid)            cout<<"No"<<endl;        else            cout<<"Yes"<<endl;        delete[] stack_in;        delete[] stack_out;    } }


  相关解决方案