第4章栈和队列 栈 栈的应用 队列 队列的应用
第4章 栈和队列 栈 栈的应用 队列 队列的应用
栈的定义 ◆栈:限定仅在表尾进行插入和删除的线性表,又称后进 先出( Last in First0ut或筒称LFO)的线性表。 ◆栈顶:允许进行插入和删除的一端。 ◆栈底:不允许插入和删除的另一端 ◆实例: 出栊 栈顶top 底 bottom 图4-1栈的示意图
栈的定义 栈：限定仅在表尾进行插入和删除的线性表 ，又称后进 先出（Last In First 0ut或简称LIFO）的线性表。 栈顶：允许进行插入和删除的一端。 栈底：不允许插入和删除的另一端 。 实例：
栈的运算 初始化:建立一个空栈。 入栈:在栈中加入一个新元素 出栈:删除栈中的栈顶元素。 取栈顶:读栈中的栈顶元素。 判空:测试栈是否为空
栈的运算 初始化：建立一个空栈。 入栈 ：在栈中加入一个新元素。 出栈： 删除栈中的栈顶元素。 取栈顶：读栈中的栈顶元素。 判空：测试栈是否为空
栈的表示方式 静态的数组表示:栈的顺序存储结构,常常 以一个固定大小的数组来表示栈。 动态的链表表示:用链表的结构来表示栈
栈的表示方式 静态的数组表示：栈的顺序存储结构，常常 以一个固定大小的数组来表示栈。 动态的链表表示：用链表的结构来表示栈
栈的顺序存储结构 顺序栈:用一组地址连续的存储单元依次存放自栈底 到栈顶的数据元素,设指针top指示栈顶元素在顺序栈 中的位置。 顺序栈数据结构可表示为: Typedef struct int stacksize elemtype *bottom; elemType *top; } SqlStack;/顺序栈类型定义* Sqlstack*s;/*S是顺序栈类型指针*/
栈的顺序存储结构 顺序栈：用一组地址连续的存储单元依次存放自栈底 到栈顶的数据元素，设指针top指示栈顶元素在顺序栈 中的位置。 顺序栈数据结构可表示为： Typedef struct { int stacksize； elemtype *bottom； elemType *top； ｝SqlStack; /*顺序栈类型定义*/ Sqlstack *S; /*S是顺序栈类型指针*/
顺序栈中数据元素和栈顶指针之间的对应 关条 op top DCBA B top A A 〔a)空栊 〔b〕插入A 〔c)插入B,C,D〔d)册除D,C 图4-2栈顶指针和栈中元索之间的关系
顺序栈中数据元素和栈顶指针之间的对应 关系
静态教组实现栈结构 # define maxsize64/*栈的最大容量*/ typedef datatype int;/*栈元素的数据类型* typedef struct datatype data[maxsizel int top; int base, shestack;/顺序栈定义*/ shestack*s;/*顺序栈的实现*/ Stackdata[o 数组 Stackdata maxsize] 栈顶指针,用整数 栈底 表示为数组下标 图4-3栈的数組表示
静态数组实现栈结构 #define maxsize 64 /* 栈的最大容量*/ typedef datatype int; /*栈元素的数据类型*/ typedef struct { datatype data[maxsize]; int top; int base; } seqstack; /*顺序栈定义*/ seqstack *s; /*顺序栈的实现 */
顺序栈的模块说明 置空栈(栈的初始化)操作: initstack(seqstack*s) datatype data[] S->top=0 S->base=0;
顺序栈的模块说明 置空栈（栈的初始化）操作： initstack(seqstack *s ) { datatype data[maxsize]; s->top=0; s->base=0; }
◆判栈空操作: int empty(seqstack*s if(s->top==s->base return true. else return false
判栈空操作： int empty(seqstack *s;) { if(s->top==s->base) return true; else return false; }
◆进栈操作: seqstack *Push(seqstack*s, datatype x) /*将元素x插入顺序栈s的顶部* k if(s->top==maxsize t printf("overflow") return NULL, se s->datals->top =x, S->top++,) return s
进栈操作： seqstack *Push(seqstack *s,datatype x) /* 将元素x插入顺序栈s的顶部*/ { if (s->top==maxsize) { printf("overflow"); return NULL; } else { s->data[s->top]=x; s->top++; } return s; }