栈与进栈出栈
成都创新互联公司长期为近1000家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为单县企业提供专业的
网站设计、成都网站制作，
单县网站改版等技术服务。拥有10多年丰富建站经验和众多成功案例,为您定制开发。
栈：是限定在栈表尾进行插入或删除的线性表，又称为后进先出（LIFO）的线性表，这个特点可以形象的表示为……（铁路调度站）
只要保证每次在栈顶操作，同一进栈顺序可以有不同的出栈顺序，以下是部分出栈顺序
34521 25431 14532 32145 43215
那么究竟怎样验证一个出栈序列与一个入栈序列匹配？
思路：将进栈和出栈序列分别存在数组里，然后再创建一个辅助栈，把输入序列中的元素依次压入栈中，并按照出栈序列依次弹出。
将进栈和出栈序列存在两个数组里，然后再创建一个辅助栈，把输入序列中的元素依次压入栈中，并按照出栈序列依次弹出。
方法：以弹出序列4,5,3,2,1为例，第一个希望被弹出的数字是4，因此需要将4先压入栈中，而压入栈中的序列由进栈序列决定，也就是在4进栈之前保证1,2,3都在栈里面。这个时候栈中包含4个数字，分别是1,2,3,4，其中4位于栈顶，正好对应出栈数组的第一个，弹出栈顶元素4，接下来希望弹出的元素是5，而5不在栈中，因此需要将进栈序列4之后的元素压进去，这个时候5位于栈顶，就可以弹出来了，接下来希望被弹出的是3,2,1，在每次操作之前他们都位于栈顶，故直接弹出即可。
代码：
#include
#include
using namespace std;
bool Check_Push_Pop(int* pPush,int* pPop,int length)
{
if(length<=0 || pPush == NULL || pPop == NULL)
{
return false;
}
int in = 0;
int out = 0;
stack s;
//s.push(pPush[0]);
int index = 0; //压入元素的个数
for(out = 0;out < length; out++) //(1)for循环控制什么
{
for(in = index;in <=length; in++) //pPush[1,2,3,4,5] pPop[4,5,3,2,1]
{
if((s.empty())||s.top()!=pPop[out]) //(2)为什么要进行判空
{
if(in == length) //(3)if检测的是什么
{
return false;
}
s.push(pPush[in]);
++index;
}
else
{
s.pop();
break; //跳出这层for循环，使它遍历下一个出栈元素
}
}
}
if(s.empty() && in == length && out==length)
return true;
else
return false;
}
void Test1()
{
int Push[5] = {1,2,3,4,5};
int Pop[5] = {4,5,3,2,1};
if(Check_Push_Pop(Push,Pop,5))
{
cout<<"输入与输出匹配"<总结：
如果下一个弹出的数字刚好是栈顶数字，那么直接弹出。如果下一个弹出的数字不在栈顶，我们把进栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈为止。如果所有的数字都压入了栈仍找到下一个弹出的数字，那么该序列不可能是一个弹出的序列。
对于入栈序列:1 2…i…j…k…n，那么它的出栈序列中不能有k…j…i这样的序列子集。即如果入栈序列为ABC，则出栈序列不可以是CAB。
例题：
某个栈的入队序列为A,B,C,D,E，则可能的出栈序列为（）
A . ADBEC(DBC) B. EBCAD (EBC)
C. BCDEA D. EABCD（EAB）
用上述规律可以得出选C
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
网站名称：进栈出栈的合法性检查-创新互联
本文地址：http://kswjz.com/article/dcdjjd.html
