首页  

数据结构第三章栈和队列     所属分类 DS 浏览量 119
栈(Stack)
只允许在一端进行插入或删除操作的线性表

栈顶(Top)允许进行插入和删除的那一端
栈底(Bottom)不允许进行插入和删除的另一端
LIFO(Last In First Out)

顺序栈
顺序存储 
顺序栈的操作
判空 进栈 出栈 读取栈顶元素

共享栈
顺序栈的存储空间大小需要事先开辟好,
每个栈各自单独开辟存储空间的利用率不高

各个栈的存储空间共享


链式栈
1.链栈一般不存在栈满的情况
2.空栈的判定条件通常定为top==NULL

队列
只允许在一端进行插入,而在另一端进行删除的线性表
队头(Front):允许删除的一端,又称为队首
队尾(Rear): 允许插入的一端。
先进先出 First In First Out FIFO

顺序队列
用数组来实现  队首放在数组下标为0的位置

循环队列
把数组“掰弯”,形成一个环  首尾相连的顺序存储的队列 
入队  rear=(rear+1)%MaxSize
出队  front=(front+1)%MaxSize
 
入队  出队
如何判断队列是空还是满 
方法一
设置标志位flag,当flag=0且rear等于front时为队列空,当flag=1且rear等于front时为队列满

方法二
把front=rear 作为队空的判定条件
队列满时,数组中仍然保留一个空余单元 

链式队列
线性表的单链表,增加限制,只能表尾插入元素,表头删除元素
分别设置队头指针和队尾指针,队头指针指向头结点,队尾指针指向尾结点
链式队列的操作
1.入队
只能从队尾插入元素,队头删除元素
于是入队就是在队尾指针进行插入结点操作
链队的插入操作和单链表的插入操作是一致的

2.出队
出队就是头结点的后继结点出队,然后将头结点的后继改为它后面的结点

双端队列
允许两端都可以进行入队和出队操作的队列


栈的应用 括号匹配 表达式求值 递归 递归最重要的是递归式和递归边界 1.阶乘 时间复杂度:O(NlogN) 2.斐波那契数列 时间复杂度 O(2^n) 中缀表达式转换成后缀表达式 1.按运算符优先级对所有运算符和它的运算数加括号 2.把运算符移到对应的括号后 3.去掉括号

上一篇     下一篇
增广贤文全文及解释

数据结构第一章绪论

数据结构第二章线性表

程序员排行榜

数据结构之树

算法导论第二版中文目录