数据结构复习要点第三章栈和队列
编辑整理:东莞自考网 发表时间:2018-05-23 12:26:53 【大 中 小】 [添加招生老师微信]
立即购买
《自考视频课程》名师讲解,轻松易懂,助您轻松上岸!低至199元/科!
栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表,称插入、删除这一端为栈顶,另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的,我们又称栈为LIFO表(Last In First Out)。通常栈有顺序栈和链栈两种存储结构。
栈的基本运算有六种: ·构造空栈:InitStack(S)
·判栈空: StackEmpty(S)
·判栈满: StackFull(S)
·进栈: Push(S,x)
·退栈: Pop(S)
·取栈顶元素:StackTop(S)
在顺序栈中有"上溢"和"下溢"的现象。 ·"上溢"是栈顶指针指出栈的外面是出错状态。
·"下溢"可以表示栈为空栈,因此用来作为控制转移的条件。顺序栈中的基本操作有六种:·构造空栈·判栈空·判栈满·进栈·退栈·取栈顶元素链栈则没有上溢的限制,因此进栈不要判栈满。链栈不需要在头部附加头结点,只要有链表的头指针就可以了。
链栈中的基本操作有五种:·构造空栈·判栈空·进栈·退栈·取栈顶元素队列(Queue)是一种运算受限的线性表,插入在表的一端进行,而删除在表的另一端进行,允许删除的一端称为队头(front),允许插入的一端称为队尾(rear) ,队列的操作原则是先进先出的,又称作FIFO表(First In First Out) 。队列也有顺序存储和链式存储两种存储构。
队列的基本运算有六种: ·置空队:InitQueue(Q)
·判队空:QueueEmpty(Q)
·判队满:QueueFull(Q)
·入队:EnQueue(Q,x)
·出队:DeQueue(Q)
·取队头元素:QueueFront(Q)
顺序队列的"假上溢"现象:由于头尾指针不断前移,超出向量空间。这时整个向量空间及队列是空的却产生了"上溢"现象。
为了克服"假上溢"现象引入循环向量的概念,是把向量空间形成一个头尾相接的环形,这时队列称循环队列。
判定循环队列是空还是满,方法有三种: ·一种是另设一个布尔变量来判断;
·第二种是少用一个元素空间,入队时先测试((rear+1)%m = front)? 满:空;
·第三种就是用一个计数器记录队列中的元素的总数。
队列的链式存储结构称为链队列,一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作,在表尾增加一个尾指针,一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中,要注意当原队中只有一个结点时,出队后要同进修改头尾指针并使队列变空。
栈的基本运算有六种: ·构造空栈:InitStack(S)
·判栈空: StackEmpty(S)
·判栈满: StackFull(S)
·进栈: Push(S,x)
·退栈: Pop(S)
·取栈顶元素:StackTop(S)
在顺序栈中有"上溢"和"下溢"的现象。 ·"上溢"是栈顶指针指出栈的外面是出错状态。
·"下溢"可以表示栈为空栈,因此用来作为控制转移的条件。顺序栈中的基本操作有六种:·构造空栈·判栈空·判栈满·进栈·退栈·取栈顶元素链栈则没有上溢的限制,因此进栈不要判栈满。链栈不需要在头部附加头结点,只要有链表的头指针就可以了。
链栈中的基本操作有五种:·构造空栈·判栈空·进栈·退栈·取栈顶元素队列(Queue)是一种运算受限的线性表,插入在表的一端进行,而删除在表的另一端进行,允许删除的一端称为队头(front),允许插入的一端称为队尾(rear) ,队列的操作原则是先进先出的,又称作FIFO表(First In First Out) 。队列也有顺序存储和链式存储两种存储构。
队列的基本运算有六种: ·置空队:InitQueue(Q)
·判队空:QueueEmpty(Q)
·判队满:QueueFull(Q)
·入队:EnQueue(Q,x)
·出队:DeQueue(Q)
·取队头元素:QueueFront(Q)
顺序队列的"假上溢"现象:由于头尾指针不断前移,超出向量空间。这时整个向量空间及队列是空的却产生了"上溢"现象。
为了克服"假上溢"现象引入循环向量的概念,是把向量空间形成一个头尾相接的环形,这时队列称循环队列。
判定循环队列是空还是满,方法有三种: ·一种是另设一个布尔变量来判断;
·第二种是少用一个元素空间,入队时先测试((rear+1)%m = front)? 满:空;
·第三种就是用一个计数器记录队列中的元素的总数。
队列的链式存储结构称为链队列,一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作,在表尾增加一个尾指针,一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中,要注意当原队中只有一个结点时,出队后要同进修改头尾指针并使队列变空。
本文标签:东莞自考 串讲笔记 数据结构复习要点第三章栈和队列
转载请注明:文章转载自(http://www.dongguanzikao.com)
《东莞自考网》免责声明:
1、由于考试政策等各方面情况的调整与变化,本网提供的考试信息仅供参考,最终考试信息请以省考试院及院校官方发布的信息为准。
2、本站内容部分信息均来源网络收集整理或来源出处标注为其它媒体的稿件转载,免费转载出于非商业性学习目的,版权归原作者所有,如有内容与版权问题等请与本站联系。联系邮箱:812379481@qq.com