2020考研计算机《数据结构(C语言版)》复习笔记(3)
2019.05.23 12:18

  2020年计算机考研复习已经开始,新东方在线在此整理了2020考研计算机《数据结构(C语言版)》复习笔记(3),希望能帮助大家!

  第三章 栈和队列知识点整理

  栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表,称插入、删除这一端为栈顶,另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的,我们又称栈为LIFO表(Last In First Out)。通常栈有顺序栈和链栈两种存储结构。

  栈的基本运算有六种: ·

  构造空栈:InitStack(S)

  ·判栈空: StackEmpty(S)

  ·判栈满: StackFull(S)

  ·进栈: Push(S,x)

  ·退栈: Pop(S)

  ·取栈顶元素:StackTop(S)

  在顺序栈中有“上溢”和“下溢”的现象。 ·“上溢”是栈顶指针指出栈的外面是出错状态。·“下溢”可以表示栈为空栈,因此用来作为控制转移的条件。

  顺序栈中的基本操作有六种:·构造空栈 ·判栈空 ·判栈满 ·进栈 ·退栈 ·取栈顶元素

  链栈则没有上溢的限制,因此进栈不要判栈满。链栈不需要在头部附加头结点,只要有链表的头指针就可以了。

  链栈中的基本操作有五种:·构造空栈 ·判栈空 ·进栈 ·退栈 ·取栈顶元素

  队列(Queue)是一种运算受限的线性表,插入在表的一端进行,而删除在表的另一端进行,允许删除的一端称为队头(front),允许插入的一端称为队尾(rear) ,队列的操作原则是先进先出的,又称作FIFO表(First InFirst Out) .队列也有顺序存储和链式存储两种存储结构。

  队列的基本运算有六种:

  ·置空队:InitQueue(Q)

  ·判队空:QueueEmpty(Q)

  ·判队满:QueueFull(Q)

  ·入队:EnQueue(Q,x)

  ·出队:DeQueue(Q)

  ·取队头元素:QueueFront(Q)

  顺序队列的“假上溢”现象:由于头尾指针不断前移,超出向量空间。这时整个向量空间及队列是空的却产生了“上溢”现象。为了克服“假上溢”现象引入循环向量的概念,是把向量空间形成一个头尾相接的环形,这时队列称循环队列。

  判定循环队列是空还是满,方法有三种:

  ·一种是另设一个布尔变量来判断;

  ·第二种是少用一个元素空间,入队时先测试((rear+1)%m = front)? 满:空;

  ·第三种就是用一个计数器记录队列中的元素的总数。

  队列的链式存储结构称为链队列,一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作,在表尾增加一个尾指针,一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中,要注意当原队中只有一个结点时,出队后要同进修改头尾指针并使队列变空。


MORE+

    相关阅读 MORE+

    版权及免责声明
    1.凡本网注明"稿件来源:新东方在线"的所有文字、图片和音视频稿件,版权均属北京新东方迅程网络科技有限公司所有,任何媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他方式复制发表。已经本网协议授权的媒体、网站,在下载使用时必须注明"稿件来源:新东方在线",违者本网将依法追究责任。
    2.本网末注明"稿件来源:新东方在线"的文/图等稿件均为转载稿,本网转载出于传递更多信息之目的,并不意味着赞同其观点或证实其内容的真实性。如其他媒体、网站或个人从本网下载使用,必须保留本网注明的"稿件来源",并自负版权等法律责任。如擅自篡改为"稿件来源:新东方在线”,本网将依法追究责任。
    3.如本网转载稿涉及版权等问题,请作者致信weisen@xdfzx.com,我们将及时外理

    Copyright © 2011-202

    All Rights Reserved