判断一个序列是否为栈的出栈序列
判断一个序列是否为栈的出栈序列
判断一个序列是否为栈的出栈序列
判断一个序列是否为栈的出栈序列
例,入栈顺序为6 5 4 3 2 1 ,输入一个序列,判断是否为出栈序列
#include<iostream
#include<malloc.h
#define ArSize 10
#define STACK_INCREMENT 20
using namespace std;
struct _Stack//栈{int *top;int *base;int stacksize;};void InitStack(_Stack &stack){
stack.base=(int *)malloc(STACK_INCREMENT*sizeof(int));//初始化栈顶和栈底
stack.top=stack.base;
stack.stacksize=ArSize;}void Push(_Stack &stack,int data){if(stack.top-stack.base==stack.stacksize)//当栈满里,增加分配空间{stack.base=(int*)realloc(stack.base,(stack.stacksize+STACK_INCREMENT)*sizeof(int));
stack.top=stack.base+stack.stacksize;
stack.stacksize+=STACK_INCREMENT;}*(stack.top)=data;//元素入栈
stack.top++;}void Pop(_Stack &stack)//出栈{int data;if(stack.top==stack.base)
cout<<"栈为空";else{stack.top--;
data=*stack.top;}}void Show(_Stack stack)//显示栈中的元素{stack.top--;
while(stack.top=stack.base){cout<<" "<<*stack.top;
stack.top--;}}int GetTop(_Stack &stack)//返回栈顶元素{return *(stack.top-1);}int main(){_Stack stack;int temp;int srcData[10]={6,5,4,3,2,1};//原始序列
int destData[10];
InitStack(stack);//初始化栈
for(int k=0;k<6;k++)//输入判断序列
cindestData[k];
int i=0,j=0;
while(stack.top=stack.base)//当栈不为空时{temp=GetTop(stack);//获取栈顶元素
if(destData[j]!=temp
)//当判断序列中的元素与栈顶元素不相等时,原始序列元素按顺序入栈{Push(stack,srcData[i]);i++;if(i6)break
;//当判断序列不是出栈顺序时,总会在某个元素时出现该元素与栈顶元素始终不相等
//此时,原始序列元素不断放栈,当大于序列长度时,判断结果;