c语言课件︰栈及队列.ppt

栈和队列 栈 抽象数据类型栈的定义 栈的表示和实现 栈的应用举例 数制转换 表达式求解 队列 栈(Stack) 栈的基本概念 栈:又称为后进先出的线性表（LIFO表，Last In First Out）一叠书或一叠盘子。 栈与子程序调用 调用子程序时，计算机将子程序要用到的参数及返回地址等信息存放在栈里 子程序返回时，从栈顶取回返回地址，转回主调程序继续运行。 处理递归调用 顺序栈 用数组定义（类似于顺序表），将栈底位置设置在向量两端的任意一个端点；用top（整型量，栈顶指针）来指示栈当前栈顶位置。 定义： typedef (type) Element;/*栈元素的数据类型*/ #define maxsize 100 /*栈初始的容量*/ typedef struct stack {Element data[maxsize]; int top; }Stack; /*顺序栈类型定义*/ Stack *s; /*s是顺序栈类型指针*/ 顺序栈：栈顶指针与栈中元素间的关系 顺序栈 栈底位置固定在数组的低端，即： S-data[0]----表示栈底元素； 进栈：S-TOP加1（正向增长）。 退栈：S-TOP减1。 空栈： S-TOP 0 栈满：S-TOP=maxsize-1 上溢：栈满时再做进栈运算（一种出错状态，应设法避免）。 顺序栈的几种基本运算 置空栈 判栈空 进栈 退栈 取栈顶元素 顺序栈的几种基本运算 置空栈：Create(Stack S) 顺序栈的几种基本运算 判栈空： 顺序栈的几种基本运算 进栈： 顺序栈的几种基本运算 顺序栈的几种基本运算 链栈进栈运算 栈小结 顺序栈有发生上溢 的可能，而链栈通常不会发生栈满（除非整个空间均被占满） 只要满足LIFO原则，均可采用栈结构。 栈的应用实例：递归调用。 栈的应用举例一数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d + (n mod d) 队列的基本概念 队头（head):允许删除（出队）的一端 队尾（tail):允许插入的一端 空队列：队列中没有元素 进队：队的插入运算，即插入新的队尾元素 出队：队的删除运算，删除队首元素 队列的基本运算 入队 出队 取队头元素 置空队列 判队列是否为空 顺序队列 队列的顺序存储结构，用一组连续的存储单元依次存放队列中的元素 顺序队列的类型说明： typedef struct { datatype data[m]; int head, tail; /*队首、队尾*/ } queue; queue *sq; 顺序队列运算时的头、尾指针变化 顺序队列的约定和主要运算 队头指针:head总是指向当前队头元素 队尾指针:tail指向当前队尾元素的下一个位置。 初始状态：head=tail=0 入队运算：sq-tail++; /*尾指针加1 */ sq-data[sq-tail]=x; /* x入队 */ 出队运算：sq-head++; /* 头指针加1 */ 顺序队列的约定和主要运算 队列长度：(sq-tail)-(sq-head) 队空： (sq-tail)=(sq-head) 下溢： 队空时再作出队操作。 队满： (sq-tail)-(sq-head)=m 上溢： 队满时再作入队操作。 顺序队列的上溢 队上溢： 真上溢（r-f=m)：队列真正满时再入队。 假上溢：r已指向数组尾端，但队列前端仍有空位置。 解决假上溢的方法： 方法一：每次删除队头一个元素后，把整个队列往前移一个位置（造成时间浪费）。 方法二：循环队列 顺序队列置队空 顺序队列判队空 顺序队列取队头元素 顺序队列入队 顺序队列出队 循环队列 (Circular Queue) 当队尾指针tail等于MaxSize时，无论有否空间，都无法再将数据存于队列中 将所用的数组sq-data[m]设想为首尾相接的循环数组（即：data[0]连在data[m-1]之后)。 循环队列的进队和出队 循环队列 (Circular Queue) 队列入队： 若尾指针 r 等于向量的上界，再入队，令尾指针等于向量的下界，即：在循环意义下的尾指针的加1操作可描述为： if(sq-tail+1=m) sq-tail=0; else sq-tail++; 循环队列 (Circular Queue) 存储队列的数组被当作首尾相接的表处理。 队头、队尾指针加1时从maxSize -1直接进到0，可用语言的取模(余数)运算实现。 队