题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。
问题分析:本题考查栈的基本操作,栈是一种“先进后出”的数据结构。判断一个序列是否是栈的pop序列是一种常见的问题,可以通过模拟push和pop的过程,push和pop总是成对出现的,如:
方法:
#define push 1
#define pop -1
bool judge_push_pop(int *a, int *b, int len_a, int len_b){
if (NULL == a || NULL == b || len_a != len_b) return false;
int *p_a = a;
int *p_b = b;
int *op = (int *)malloc(sizeof(int) * len_a * 2);
int index = 0;
int i = 0;
while(i < len_a){
op[index] = push;
index ++;
if (*p_a == *p_b){
p_b ++;
op[index] = pop;
index ++;
}
p_a ++;
i ++;
}
while(index < len_a * 2){
op[index++] = pop;
}
// judge
int start = 0;
int end = len_a * 2 - 1;
while(start < end){
if (op[start] + op[end] == 0){
start ++;
end --;
}else return false;
}
return true;
free(op);
}