《栈和队列PPT课件.ppt》由会员分享，可在线阅读，更多相关《栈和队列PPT课件.ppt（23页珍藏版）》请在三一办公上搜索。
1、第三章 栈和队列,栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS3.1 栈（stack）栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）,栈的存储结构栈顺序存储表示：#define STACK_INIT_SIZE 100/存储空间初始分配量#define STACKINCREMENT 10/存储空间分配增量typedef struct Selemtype*base;/在栈构造之前和销毁之后，base的值为NULL Selemtype*top;/栈顶指针 int stacksize;
2、/当前已分配的存储空间，以元素为单位 sqstack;栈的基本操作：P46,栈顶指针top,指向实际栈顶后的空位置，初值为0,进栈,A,出栈,栈满,B,C,D,E,F,top=0,栈空，此时出栈，则下溢top=stacksize,栈满，此时入栈，则上溢,栈的操作演示：,构造一个空栈,status initstack(sqstack,销毁栈,status destorystack(sqstack,置栈为空栈,status clearstack(sqstack,判空,int stackempty(sqstack s)return s.base=s.top;,在一个程序中同时使用两个栈,链栈,入栈,
3、出栈,栈的应用数值转换,回文游戏：顺读与逆读字符串一样（不含空格）,1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文,括号匹配的检验：行编辑程序迷宫求解,字符串：“madam im adam”,表达式求值,中缀表达式 后缀表达式（RPN)a*b+c ab*c+a+b*c abc*+a+(b*c+d)/e abc*d+e/+,中缀表达式：操作数栈和运算符栈,(1)对每种运算符赋予一个优先数(2)可以使用两个工作栈：数栈(NS)；运算符栈(OS)。(3)编译程序自左向右扫描至语句结束符，处理的原则是：凡遇到操作数，一律进数栈；当遇到
4、运算符时，则将该运算符的优先数与运算符栈中的栈顶元素的优先数相比较。若该运算符的优先数大，则进栈；反之，则取出栈顶的运算符，并在数栈中连续取出两个栈顶元素作为运算对象进行运算，并将运算结果存入数栈，然后继续比较该运算符与栈顶元素的优先数。,例 计算 2+4-3*6,后缀表达式求值步骤：1、读入表达式一个字符2、若是操作数，压入栈，转43、若是运算符，从栈中弹出2个数，将运算结果再压入栈4、若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转1,例 计算 4+3*5,后缀表达式：435*+,3.2 队列队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(r
5、ear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO),双端队列,链队列结点定义,typedef struct QNode Qelemtype data;struct QNode*next;Qnode,*QueuePtr;,设队首、队尾指针front和rear,front指向头结点，rear指向队尾,typedef struct QueuePtr front;QueeuPtr rear;LinkQueue;,构造空队列,销毁队列Q,status InitQueue(LinkQueue,status DestoryQueue(LinkQueue,入队算法,出队算法,
6、status EnQueue(LinkQueue,status DeQueue(LinkQueue,队列的顺序存储结构,J1,J2,J3,设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1,空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;,存在问题设顺序空间为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出真溢出当front-1,rear=M-1时，再有元素入队发生溢出假溢出解决方案队首固定，每次出队剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让s
7、q0接在sqM-1之后，若rear+1=M,则令rear=0;,实现：利用“模”运算入队：rear=(rear+1)%M;sqrear=x;出队：front=(front+1)%M;x=sqfront;队满、队空判定条件,队空：front=rear队满：front=rear,解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front=rear 队满：(rear+1)%M=front,构造空队列,队列长度,status initqueue(sqQueue,int queuelength(sqQueue Q)return(Q.rear-Q.front+MAXQUEUESIZE)%MAXQUEUESIZE;,#define MAXQUEUESIZE 100 typedef struct Qelemtype*base;int front，rear;sqQueue;,入队算法,出队算法,status EnQueue(SqQueue,status DeQueue(SqQueue,
