首页 > 编程语言 >挑战数据结构和算法——栈的push、pop序列

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

时间:2023-06-14 20:38:01浏览次数:60  
标签:index int len ++ pop push 数据结构 op


题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。

挑战数据结构和算法——栈的push、pop序列_基本操作

问题分析:本题考查栈的基本操作,栈是一种“先进后出”的数据结构。判断一个序列是否是栈的pop序列是一种常见的问题,可以通过模拟push和pop的过程,push和pop总是成对出现的,如:

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

方法:

#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);
}


标签:index,int,len,++,pop,push,数据结构,op
From: https://blog.51cto.com/u_16161414/6480393

相关文章

  • 【数据结构和算法面试题】跳台阶问题
    题目来源“数据结构与算法面试题80道”。问题分析:假设为跳台阶的总跳法,当时,;当时,;当时,如果先跳1级台阶,有种方法,如果先跳2级台阶,有种方法,依次类推,可以得到下面的递推公式:方法:intget_kind(intn){ if(n<=0)return0; intresult; int*cal=(int*)malloc(sizeof(int)*n);......
  • 挑战数据结构和算法——整数的二进制表示中1的个数
    题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。问题分析:本题涉及到二进制的处理,在本题使用到&操作和>>操作。方法:intget_num(intn){intnum=0;if(n<0){num+=1;n=n*(-1);}while(n!=0){......
  • 【数据结构与算法面试题】二叉树节点的最大距离
    题目来源“数据结构与算法面试题80道”。问题分析:涉及的知识点是二叉树的遍历,遍历的方法主要有:先序遍历中序遍历后序遍历层次遍历在本题中,使用先序遍历的方法。方法:voidm_length(BSTreeNode*root,int*length,int*max_length){if(NULL==root||(NULL==root......
  • 数据结构和算法——旋转打印链表
    1、问题描述输入参数nn为正整数,如输入n=5n=5,则按行打印如下的数字:2、问题的理解这个问题是将数字1…n21…n2按照一圈一圈的方式......
  • python基础知识——内置数据结构(字典)
      字典是有“键-值”对组成的集合,字典中的“值”通过“键”来引用。“键-值”对之间用逗号隔开,并且被包含在一对花括号中。1、字典的创建格式dictionary_name={key1:value1,key2:value2,...}创建空的字典dictionary_name={}例如dict={'b':'beijing','s':......
  • 挑战数据结构和算法面试题——二叉搜索树的后序遍历
    分析:根据二叉查找树的定义,二叉查找树或者是一棵空二叉树,或者是具有一下特性的二叉树:若它的左子树不为空,则左子树上的所有结点的值均小于根节点的值;若它的右子树不为空,则右子树上的所有结点的值均小于根节点的值;它的左右子树又分别是二叉查找树。结合二叉树的后序遍历,则初始序列的最......
  • 【数据结构和算法面试题】左旋转字符串
    问题分析:本题是常见的旋转字符串的问题,解决的方法是两步旋转的方法:方法:voiddo_reverse(char*p_start,char*p_end){ if(NULL==p_start||NULL==p_end||p_start>p_end)return; chartmp; while(p_start<p_end){ tmp=*p_start; *p_start=*p_end; *p_end......
  • 【数据结构与算法面试题】子数组的最大和
    题目来源“数据结构与算法面试题80道”。问题分析:在数组的每一个位置处保存当前的最大值,当前的最大值组成为:解决方案:intget_max_subarray(int*a,intlength,bool&is_array_ok){ if(NULL==a||length<=0){ is_array_ok=false; return0; } int*p_h_a=(int*......
  • 数据结构和算法——二叉排序树
    一、二叉排序树对于无序的序列“62,58,88,47,73,99,35,51,93,29,37,49,56,36,48,50”,是否存在一种高效的查找方案,使得能够快速判断在序列中是否存在指定的数值?二叉排序树是一种简单,高效的数据结构。二叉排序树,又称为二叉查找树。二叉排序树或者是一棵空树,或者是具有以下性质的二叉树:若其左子树不为......
  • 挑战数据结构和算法面试题——最大差值
    题目来自伯乐在线,欢迎有不同答案的同学来一起讨论。分析:基本方法是遍历数组,找到当前值前面所有数组元素的最小值。方法:intget_max_distance(int*a,constintn){intmax_distance=0;//纪录最大距离if(n==0)returnmax_distance;intmin=a[0];//纪录最小的......