挑战数据结构和算法——栈的push、pop序列

题目来源“数据结构与算法面试题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);
}

$(".MathJax").remove();

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序生活

Python json 模块dumps、dump、loads、load的使用

本文主要讲下json.dumps和json.dump、json.loads和json.load的区别,因为经常需要加载json文件,读取数据,傻傻分不清...

9210
来自专栏决胜机器学习

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一)——图的连通性问题与最小生成树算法(2) (原创内容,转载请注明来源,谢谢) 再次遇到微信公众号限制字数3000字的问题。因此将...

458100
来自专栏向治洪

高级聚类

FuzzyKmeans 在对数据进行聚类时,最常用的方法应该是kmeans,但是kmean只能保证每一条待聚类的数据划分到一个类别,针对一条数据可以被划分到多个...

20980
来自专栏数据结构与算法

2806 红与黑 个人博客:doubleq.win

个人博客:doubleq.win 2806 红与黑  时间限制: 1 s  空间限制: 64000 KB  题目等级 : 白银 Silver 题解  查看运行结...

29740
来自专栏GIS讲堂

Geohash之范围搜索

很多时候,我们都会遇到这样的需求:查找某个点周边多少距离的点。从本质来说,是一个缓冲区分析+空间查找,本文结合Geohash来实现类似的功能。

27340
来自专栏kevin-blog

acm C语言求两个数最大值

67510
来自专栏数据结构与算法

洛谷P3807 【模板】卢卡斯定理exgcd

题目背景 这是一道模板题。 题目描述 给定n 求  保证P为prime C表示组合数。 一个测试点内包含多组数据。 输入输出格式 输入格式: 第一行...

40760
来自专栏机器学习算法与Python学习

Numpy

Numpy Numpy是Python中用于科学计算的核心库。它提供了高性能的多维数组对象,以及相关工具。(本文文末的原文链接为numpy的官方文档) NumPy...

35470
来自专栏机器学习入门

POJ 刷题系列:2965. The Pilots Brothers' refrigerator

POJ 刷题系列:2965. The Pilots Brothers’ refrigerator 传送门:POJ 2965. The Pilots Brothe...

20760
来自专栏landv

c语言_头文件

22930

扫码关注云+社区

领取腾讯云代金券