c#如何实现栈的压入、弹出序列
导读:本文共1584.5字符,通常情况下阅读需要5分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1、2、3、4、5是某栈的压栈顺序,序列4、5、3、2、1是该压栈序列对应的一个弹出序列,但4、3、5、1、2就不可能是该压栈序列的弹出序列。 首先,可以在第一个序列也就是压栈顺序中找第二个序列中第一个元素,是4,因为第二个序列中第一个... ...
目录
(为您整理了一些要点),点击可以直达。输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1、2、3、4、5是某栈的压栈顺序,序列4、5、3、2、1是该压栈序列对应的一个弹出序列,但4、3、5、1、2就不可能是该压栈序列的弹出序列。
首先,可以在第一个序列也就是压栈顺序中找第二个序列中第一个元素,是4,因为第二个序列中第一个元素是第一个被弹出的,那么在压入顺序中,被弹出数据之前的所有数据都被压入了栈中且还没有被弹出,也就是连续压进去了1、2、3、4,然后弹出第一个数据4;之后在第二个序列中往后的元素,是5,如果不是栈顶元素就在第一个序列中从4开始往后找继续压入再弹出,再次往后取第二个序列中的元素,如果是栈顶元素就弹出,直到栈空且两个序列都遍历一遍为止,否则,如果栈不为空且两个序列都遍历过了,则说明第二个序列不是压栈序列的弹出序列。
程序设计如下:
#include<iostream>#include<stack>#include<assert.h>usingnamespacestd;boolIsPopSeq(int*push_arr,int*pop_arr,size_tsize){assert(push_arr&&pop_arr&&size);//判断参数的有效性stack<int>s;size_tpush_index=0;size_tpop_index=0;while(pop_index<size){//将输入队列中处于输出队列第一个元素之前的所有元素都压入栈内while(push_index<size){s.push(push_arr[push_index]);++push_index;if(s.top()==pop_arr[pop_index])break;}//判断,如果输入队列全部压完了但仍然没有找到输出队列的的第一个元素,就返回falseif((!s.empty())&&(s.top()!=pop_arr[pop_index]))returnfalse;//当栈中的元素恰好就是输出队列的弹出顺序时就不断的弹出while((!s.empty())&&(pop_arr[pop_index]==s.top())){s.pop();++pop_index;}}//正确返回的条件就是当输入队列和输出队列都遍历完毕且栈为空时判断完成if((push_index==size)&&(pop_index==size)&&s.empty())returntrue;elsereturnfalse;}intmain(){intpush_arr[]={1,2,3,4,5};intpop_arr1[]={4,5,3,2,1};intpop_arr2[]={4,3,5,1,2};intpop_arr3[]={2,5,3,4,1};size_tsize=sizeof(push_arr)/sizeof(push_arr[0]);boolret=IsPopSeq(push_arr,pop_arr1,size);cout<<ret<<endl;ret=IsPopSeq(push_arr,pop_arr2,size);cout<<ret<<endl;ret=IsPopSeq(push_arr,pop_arr3,size);cout<<ret<<endl;return0;}
运行程序:
从上面的数组可以判断结果分别为true,false,false。
《完》
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">
c#如何实现栈的压入、弹出序列的详细内容,希望对您有所帮助,信息来源于网络。