栈和队列讲义（精品）.pptVIP

(a)空队列； front = rear = 0 (b)J1、J2和J3，相继入队列； (b)J1和J2相继被删除； (d)J4、J5和J6相继插入队列之后J3、 J4被删除。 (a) (b) ( c ) (d) 图3.12 头、尾指针和队列中元素之间的关系 Q.rear Q.front J1 J2 J3 Q.rear Q.front J3 Q.front Q.rear J5 J6 Q.front Q.rear 假设当前为队列分配的最大空间为6，则当队列处于图3.12(d)的状态时不可再继续插入新的队尾元素，否则会因数组越界而遭致程序代码被破坏。然而此时又不宜如顺序栈那样，进行存储再分配扩大数组空间，因为队列的实际可用空间并未占满。一个较巧妙的办法是将顺序队列臆造为一个环状的空间，如图3.13所示，称之为循环队列。 Q.front Q.rear 1 0 maxsize-1 图 3.13 空闲空间 循环队列类型的模块说明如下： #define MAXQSIZE 100 //最大队列长度 typedef struct { QElemType *base；//初始化的动态分配存储空间 int front；//头指针，若队列不空，指向队列头元素 int rear；//尾指针，若队列不空，指向队列尾元素的下一个位置 }SqQueue ； Status InitQueue (SqQueue Q){ //构造一个空队列Q Q.base=( QElemType)malloc (MAXQSIZE*sizeof(QElemType))； if(!Q.base)exit(OVERFLOW)； //存储分配失败 Q.front = Q.rear = 0； return OK； } 构造一个空循环队列 Int QueueLength (SqQueue Q){ //返回Q的元素个数，即队列的长度 return(Q.rear– Q.front + MAXQSIZE) % MAXQSIZE； } 循环队列长度 求迷宫中一条从入口到出口的路径的算法可简单描述 如下： 设定当前位置的初值为入口位置； do{ 若当前位置可通， 则{ 将当前位置插入栈顶； 若该位置是出口位置，则结束； //位置求得路径存放在栈中 否则切换当前位置的东邻方块为新的当前 位置； } 否则{ 若栈不空且栈顶位置尚有其他方向未经探索， 则设定新的当前位置为沿顺时针方向旋转找 到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则{ 删去栈顶位置； //从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，直至 找到一个可通的相邻块或出栈至栈空； } } }while(栈不空)； 表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的又一个典型例子。这里介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。 要把一个表