数据结构教学课件3p幻灯片.pptVIP

第三章 栈和队列 3．1 栈 3．2 队列 3．3 栈与队列的比较 第三章 栈和队列 3．1 栈 栈的定义及运算 栈（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成为新的栈顶元素。 （4）出栈pop（s）：删除栈s的栈顶元素。 （5）读栈顶元素top（s）：栈顶元素作为结果返回， 不改变栈的状态。 顺序栈及运算的实现 采用顺序方式存储的栈称为顺序栈（Sequential Stack）。 顺序栈用C语言描述如下： #define MAXSIZE 1024 /*栈可能达到的最大容量*/ typedef int DataType; typedef struct { DataType data[MAXSIZE]; int top; }SeqStack ; SeqStack *s; /*定义s是一个指向顺序栈的指针*/ 栈的操作及栈顶指针变化情况 在顺序栈上实现五种基本运算的C函数 （1）初始化栈 首先建立栈空间，然后初始化栈顶指针。 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(overflow); return 0; } s-top++; s-data[s-top]=x; return 1; } 在顺序栈上实现五种基本运算的C函数 （4）出栈 void pop (SeqStack *s) /*设栈不空*/ { s-top--; } （5）读栈顶元素 DataType top (SeqStack *s) /*设栈不空*/ { return (s-data[s-top] ); } 链栈及运算的实现 采用链接方式存储的栈称为链栈（Linked Stack） 链栈用C语言描述如下： typedef struct Node { DataType data; struct Node *next; } LinkStack; LinkStack *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）当表达式全部扫描完毕，若栈为空，说明括号匹配，否则表明“左括弧”有多余的。 栈与递归 栈的一个重要应用是在程序设计语言中实现递归 递归：函数、过程或数据结构等对象在其定义的内部直接或间接出现