2023考研408数据结构备考知识点:栈(上)

今天小编为大家整理了2023考研408数据结构知识点之栈的相关介绍,从栈的定义、栈的核心问题、对顶栈等方面为大家做详细的介绍,助力大家更好地备考,提高备考效率,顺利进入理想院校。

1:栈的定义

栈:只允许存表的一端(栈项)进行插入或删除的线性表。栈的操作特性为后进先出(LIFO),故又称后进先出的线性表

2:栈的出栈情形计算

给定n个元素依次进栈,虽然进栈顺序是一定的,但是出栈顺序不确定,因为在进栈后,可以随时做出栈操作,出栈的顺序一共有多少种呢?对应的公式, 给定n个元素,出栈的顺序的情形满足卡特兰数,计算公式是:
考研备考知识点

3:顺序栈的进栈和出栈的表达式

一般我们讨论是,都是用A[0,…,n-1]的数组进行存储,且初始时top = bottom = 0;

进栈:考研备考知识点

出栈:考研备考知识点

4:栈的核心问题

一般我们讨论是,都是用A[0,…,n-1]的数组进行存储,且初始时top = bottom = 0;

(1)什么时候栈空? top = bottom;

(2)如何进栈?考研备考知识点

(3)如何出栈?考研备考知识点

(4)栈底指针指向哪里?bottom始终指向0的位置;

(5)栈顶指针指向哪里?top始终指向栈顶元素的下一个空位置;

(6)什么时候栈满? top-bottom >= n;

(7)栈中元素有几个? top个;

5:对顶栈

假如有两个顺序栈,我们可以让两个栈共享同一片存储空间,将两个栈的栈底在这片存储空间的两端,当元素入栈时,两个栈的栈顶指针相向而行,这样的栈叫做对顶栈。

当|t1-t2| == 1时,表示共享栈满,其中t1和t2表示两个栈的栈顶。

6:链栈的插入和删除

大家只需要理解并掌握一点,链栈是头出头插的单链表。具体实现上有两种情况:

(1)带头结点的单链表方式:假设头指针为top;工作指针是p

入栈:p-> next = top-> next ; top->next = p;

出栈:p = top-> next ; top->next = p ->next; return p;

(2)不带头结点的单链表方式: 假设头指针为top;工作指针是p

入栈:p - >next = top ; top = p;

出栈:p = top; top = top ->next; return p;

【23考研黄金期辅导课程推荐】23暑期集训营线上+线下VIP领学计划龙腾一对一专属VIP公共课+专业课全科辅导,这些课程中都会配有内部讲义以及辅导书和资料,同时会有教研教辅双师模式对大家进行教学以及督学,并配有24小时答疑和模拟测试等,具体详情可直接咨询在线客服老师。


免责声明:本平台部分帖子来源于网络整理,不对事件的真实性负责,具体考研相关内容请以各院校的官网通知为准。 如果本站文章侵犯到您的权利,请联系我们(400-108-7500)进行删帖处理。

启航教育热门私房课

MORE
  • 2023考研VIP领学计划

    时间:随报随学
    形式:网课+面授
     

    查看详情

    在线咨询

  • 2023考研全年集训营

    时间:3.1-12.16
    形式:面授
     

    查看详情

    在线咨询

  • 2023考研二战集训营

    3.1-12.16
    形式:面授
     

    查看详情

    在线咨询

姓名

手机号

报考专业

请选择  
  • 计算机
  • 经济学
  • 金融硕士
  • 法律硕士
  • 应用统计
  • 机械工程
  • 管理学
  • 通信工程
  • 教育学
  • 心理学
  • 国际商务
  • 土木工程
  • 其他专业
一键申请
扫描上方二维码免费领取学习资料