数据结构栈和队列.ppt
《数据结构栈和队列.ppt》由会员分享,可在线阅读,更多相关《数据结构栈和队列.ppt(24页珍藏版)》请在三一文库上搜索。
1、第三章 栈和队列,31 栈 32 队列 33 栈与队列的比较,第三章 栈和队列,31 栈 栈的定义及运算 栈(Stack)是运算受限的线性表,限制它的插入和删除操作仅在表的一端进行。 栈顶(Top),栈顶元素,栈底(Bottom),空栈,进栈或入栈,出栈或退栈。 后进先出的线性表(Last In First Out),简称 LIFO表,栈的基本运算有五种: (1)初始化栈 initStack(s):构造了一个空栈s。 (2)判栈空empty(s):若栈s为空栈,返回值为“真” (1),否则返回值为“假”(0)。 (3)入栈push(s,x):在栈s的顶部插入一个新元素x , x成为新的栈顶元素
2、。 (4)出栈pop(s):删除栈s的栈顶元素。 (5)读栈顶元素top(s):栈顶元素作为结果返回, 不改变栈的状态。,顺序栈及运算的实现 采用顺序方式存储的栈称为顺序栈(Sequential Stack)。 顺序栈用C语言描述如下: #define MAXSIZE 1024 /*栈可能达到的最大容量*/ typedef int DataType; typedef struct DataType dataMAXSIZE; int top; SeqStack ; SeqStack *s; /*定义s是一个指向顺序栈的指针*/,栈的操作及栈顶指针变化情况,在顺序栈上实现五种基本运算的C函数 (1
3、)初始化栈 首先建立栈空间,然后初始化栈顶指针。 SeqStack *initSeqStack() SeqStack *s; s=(SeqStack*)malloc(sizeof(SeqStack); s-top= -1; return s; (2)判栈空 int empty (SeqStack *s) if (s-top= -1) return 1; else return 0; ,在顺序栈上实现五种基本运算的C函数 (3)入栈 int push (SeqStack *s, DataType x) if (s-top=MAXSIZE-1) /*栈满不能入栈*/ printf(“overflo
4、w“); return 0; s-top+; s-datas-top=x; return 1; ,在顺序栈上实现五种基本运算的C函数 (4)出栈 void pop (SeqStack *s) /*设栈不空*/ s-top-; (5)读栈顶元素 DataType top (SeqStack *s) /*设栈不空*/ return (s-datas-top ); ,链栈及运算的实现 采用链接方式存储的栈称为链栈(Linked Stack) 链栈用C语言描述如下: typedef struct Node DataType data; struct Node *next; LinkStack; Lin
5、kStack *top ; /*说明top为栈顶指针*/,栈的应用 例3.1 将一个十进制正整数N转换成r进制的数 N N / 8 (整除) N % 8(求余) 1835 229 3 低 229 28 5 28 3 4 3 0 3 高,例3.2 算术表达式中括号匹配的检查 用栈来实现括号匹配检查的原则是,对表达式从左到右扫描。 (1)当遇到左括号时,左括号入栈; (2)当遇到右括号时,首先检查栈是否空,若栈空,则表明该“右括弧”多余;否则比较栈顶左括号是否与当前右括号匹配,若匹配,将栈顶左括号出栈,继续操作;否则,表明不匹配,停止操作。 (3)当表达式全部扫描完毕,若栈为空,说明括号匹配,否则
6、表明“左括弧”有多余的。,栈与递归 栈的一个重要应用是在程序设计语言中实现递归 递归:函数、过程或数据结构等对象在其定义的内部直接或间接出现了对自身的引用是一种递归。 递归函数:一个函数在其定义的内部直接调用自身,这个函数就叫做直接递归函数。 long fact (int n) long f; if (n=0) f=1 ; else f=n* fact (n-1) ; return f; ,fact(3) 的执行过程,递归调用过程中栈及栈中数据的变化状况,递归函数转换为非递归函数 递归函数的完成需要借助于一个系统栈来保存中间结果。实际上,用户也可以在算法中设置栈来模拟系统栈的作用,从而将递归函
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 队列
链接地址:https://www.31doc.com/p-3185671.html