null第三章 栈和队列 栈和队列是限定插入和删除只能在表的“端点”进行的线性表。 线性表 栈 队列
Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)
1≤i≤n+1
Delete(L, i) Delete(S, n) Delete(Q, 1)
1≤i≤n第三章 栈和队列第三章 栈和队列3.1 栈3.2 栈的应用举例3.3 栈与递归的实现3.4 队列第三章 栈和队列第三章 栈和队列第三章 栈和队列3.1 栈（stack）
栈的定义和特点
定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈
特点：先进后出（FILO）或后进先出（LIFO）null3.1 栈 ADT Stack {
数据对象：
D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：
R1＝{
| ai-1, ai∈D, i=2,...,n }
约定an 端为栈顶，a1 端为栈底。 基本操作： } ADT StacknullInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit()) InitStack(&S)
操作结果：构造一个空栈 S。
DestroyStack(&S)
初始条件：栈 S 已存在。
操作结果：栈 S 被销毁。 InitStack(&S)
操作结果：构造一个空栈 S。
DestroyStack(&S)
初始条件：栈 S 已存在。
操作结果：栈 S 被销毁。StackEmpty(S)
初始条件：栈 S 已存在。
操作结果：若栈 S 为空栈，则返回TRUE，否则 FALE。StackEmpty(S)
初始条件：栈 S 已存在。
操作结果：若栈 S 为空栈，则返回TRUE，否则 FALE。StackLength(S)
初始条件：栈 S 已存在。
操作结果：返回 S 的元素个数，即栈的长度。GetTop(S, &e)
初始条件：栈 S 已存在且非空。
操作结果：用 e 返回 S 的栈顶元素。GetTop(S, &e)
初始条件：栈 S 已存在且非空。
操作结果：用 e 返回 S 的栈顶元素。a1a2an… … ClearStack(&S)
初始条件：栈 S 已存在。
操作结果：将 S 清为空栈。
Pop(&S, &e)
初始条件：栈 S 已存在且非空。
操作结果：删除 S 的栈顶元素，并用 e 返回其值。Pop(&S, &e)
初始条件：栈 S 已存在且非空。
操作结果：删除 S 的栈顶元素，并用 e 返回其值。a1a2anan-1 … …Push(&S, e)
初始条件：栈 S 已存在。
操作结果：插入元素 e 为新的栈顶元素。
a1a2ane … …3.1.2 栈的表示和实现3.1.2 栈的表示和实现null栈的存储结构
栈顺序存储表示——顺序栈
# define STACK_INIT_SIZE 100
# define STACKINCREMENT 10 //存储空间增量
typedef struct
{ Selemtype *base;
//在栈构造之前和销毁之后，base的值为NULL
Selemtype *top; //栈顶指针
int stacksize;
//当前已分配的存储空间，以元素为单位
} sqstack;
栈的基本操作：P46-47null栈顶指针top,指向实际栈顶
后的空位置，初值为0进栈A出栈栈满BCDEFtop=base,栈空，此时出栈，则下溢
top-base= stacksize,栈满，此时入栈，则上溢栈的操作演示：null构造一个空栈status initstack( sqstack&s)
{ s.base=(Selemtype *) malloc(STACK_INIT_SIZE*sizeof(Selemtype));
if (!s.base) exit(overflow);
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return OK;
}null销毁栈status destorystack(sqstack &s)
{ if (!s.base) exit(error);
free(s.base);
s.base=s.top=NULL;
return OK;
} null置栈为空栈 status clearstack(sqstack&s)
{ if (!s.base) exit(error);
s.top=s.base;
return OK;
}判空 int stackempty(sqstack s)
{ return s.base==s.top;
}null取栈顶元素 status gettop(sqstack s ,Selemtype &e)
{ if (s.top==s.base ) exit(error);
e=*(s.top-1);
return OK;
}栈长度 int stacklength(sqstack s)
{ return s.top-s.base; }null入栈
Status Push (SqStack &S, SElemType e)
{ // 若栈不满，则将 e 插入栈顶
if (S.top - S.base >= S.stacksize) //栈满
return OVERFLOW;
*S.top++ = e;
return OK;
}null入栈status push(sqstack&s ,Selemtype e)
{ // 插入元素e为新的栈顶元素
if (s.top-s.base>=s.stacksize)
{ s.base=(Selemtype *) realloc
(s.base,(s.stacksize+STACKINCREMENT) *sizeof(Selemtype));
if (!s.base) exit(overflow);
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREMENT;
}
*s.top++=e;
return OK; }null出栈status pop(sqstack&s,Selemtype&e)
{ if(stackempty(s)) exit(error);
e=*--s.top;
return OK;
}null3.1.2 链栈入栈出栈null
*只在表头操作，故头指针即为top，无需头结点
定义
typedef struct snode {
DataType data;
struct snode *next;
} StackNode;
typedef struct {
StackNode *top;
} LinkStack;
链栈动态分配结点，无需考虑上溢
3.1.2 链栈null
*void InitStack(LinkStack &S) {
S.top=Null; }
int StackEmpty (LinkStack &S) {
return S.top==NULL; }
void Push(LinkStack &S, DataType x) {
StackNode *p=(StackNode*) malloc (sizeof(StackNode));
p->data=x;
p->next=s.top;
s.top=p; }3.1.2 链栈null
*DataType Pop(LinkStack &S) {
DataType x;
StackNode *p=S.top;
if(StackEmpty(S))
Error (“underflow”); // 下溢
x=p->data;
S.top=p->next;
free(p);
return x;
}
3.1.2 链栈第三章 栈和队列3.1 栈3.2 栈的应用举例3.3 栈与递归的实现3.4 队列第三章 栈和队列null3.2 栈的应用举例
数值转换nullvoid conversion () {
InitStack(S);
scanf ("%d",&N);
while (N) {
Push(S, N % 8);
N = N/8;
}
while (!StackEmpty(S)) {
Pop(S,e);
printf ( "%d", e );
}
} // conversionnull回文游戏：顺读与逆读字符串一样（不含空格）算法：
1.读入字符串
2.去掉空格（原串）
3.压入栈
4.原串字符与出栈字符依次比较
若不等，非回文
若直到栈空都相等，回文举例：字符串：“madam im adam”nullstatus ishs () { //判断输入串是否是回文数
InitStack(S);
gets(str); i=j=0;
while (str[i++])
if (str[i]!=‘ ’) {
str1[j++]=str[i]; push(S,str[i]);
}
i=0;
while (!StackEmpty(S)) {
Pop(S,e);
if (e!=str1[i++]) reture false
}
returen true
} // ishsnull括号匹配的检验
假设在表达式中
（［］（））或［（［ ］［ ］）］
等为正确的格式，
［（ ］）或（［（ ））或 (( )])
均为不正确的格式。则 检验括号是否匹配的方法可用
“期待的急迫程度”这个概念来描述。分析可能出现的不匹配的情况:分析可能出现的不匹配的情况:到来的右括弧非是所“期待”的;例如：考虑下列括号序列：
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8栈空，到来的是“不速之客”;直到表达式结束，也没有到来所“期待”的括弧;null算法的
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空
若栈空，则表明该“右括弧”多余
否则和栈顶元素比较：
若相匹配，则“左括弧出栈”
否则表明不匹配表达式检验结束时，
若栈空，则表明表达式中匹配正确
否则表明“左括弧”有余循环执行1),2)nullStatus matching(string& exp) {
int state = 1; i=0;
while (i<=Length(exp) && state) {
switch of exp[i] {
case ‘(’
case ’[’:{Push(S,exp[i]); i++; break;}
case ’]’
case’)’: {
if(NOT StackEmpty(S)&&GetTop(S)=exp[i])
{Pop(S,e); i++;}
else {state = 0;}
break; } }
if (StackEmpty(S)&&state) return OK; …...null例三、行编辑程序问题如何实现？“每接受一个字符即存入存储器” ? 并不恰当！null 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区; 并假设“#”为退格符，“@”为退行符。 在用户输入一行的过程中，允许 用户输入出差错，并在发现有误时 可以及时更正。合理的作法是：null假设从终端接受了这样两行字符：
whli##ilr#e（s#*s)
outcha@putchar(*s=#++);则实际有效的是下列两行：
while (*s)
putchar(*s++);null while (ch != EOF && ch != '\n') {
switch (ch) {
case '#' : Pop(S, c); break;
case '@': ClearStack(S); break;// 重置S为空栈
default : Push(S, ch); break;
}
ch = getchar(); // 从终端接收下一个字符
}ClearStack(S); // 重置S为空栈
if (ch != EOF) ch = getchar();while (ch != EOF) { //EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的
数据区；null子树方向：a[4][2]={ {-1,0}, {0,-1}, {0,-1}, {1,0}}
约束函数: (1)i,j不越界
(2)a[i][j]=1
(3)b[i][j]=0例四、 迷宫求解nullprivate static void backtrack(i,j)
{ if (i==n) &&(j==m) then
输出b
else
for(k=0;k<4;k++){
i=i+a[k][0]; j=j+a[k][1];
if (i>0 && i0&&j1&&b[i][j]<>2) then
{ b[i][j]=1;
backtrack(i,j);
b[i][j]=2;}
} 例四、 迷宫求解null例四、 迷宫求解通常用的是“穷举求解”的方法null1 1 11 2 22 2 23 2 13 3 13 4 42 4 12 5 12 6 41 6 31 5 31 4 43$$$$$$$$ 0 1 2 3 4 5 6 7 8 90
1
2
3
4
5
6
7
8
9求迷宫路径算法的基本思想是：求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。null设定当前位置的初值为入口位置；
do｛
若当前位置可通，
则｛将当前位置插入栈顶；
若该位置是出口位置，则算法结束；
否则切换当前位置的东邻方块为
新的当前位置；
｝
否则 {
｝
｝while (栈不空）；求迷宫中一条从入口到出口的路径的算法： … …null若栈不空且栈顶位置尚有其他方向未被探索，
则设定新的当前位置为: 沿顺时针方向旋转
找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，
则｛删去栈顶位置；// 从路径中删去该通道块
若栈不空，则重新测试新的栈顶位置，
直至找到一个可通的相邻块或出栈至栈空；
｝若栈空，则表明迷宫没有通路。null算术表达式的求值
四则运算的规则：
1）先乘除，后加减；
2）同一个优先级，先左后右；
3) 先括号内，后括号外。
例如： 2+6*(7-4)*3表达式，求值过程为：自左向右扫描表达式，当扫描到2+6时不能马上计算，因为后面可能还有更高的运算。
为此，使用两个工作栈：一个称做OPTR，用以存放运算符；一个称做OPND，用以存放操作数或运算结果。
null* 把运算符和界符统称为算符，根据运算规则，任意两个相继出现的算符 和 之间的优先关系至多是下面3种关系之一：null 左括号“（”在栈外时它的级别最高，而进栈后它的级别则最低 。当遇到右括号“）”时，一直需要对运算符栈出栈，并且做相应的运算，直到遇到栈顶为左括号“(”时，将其出栈，因此右括号“）”级别最低但它是不入栈的。表3-1 运算符优先级关系表(θ1, θ2)*表3-1 运算符优先级关系表(θ1, θ2)θ2θ1null*算法：
1. 置操作数栈OPND为空，运算符栈OPTR的栈底压入#
２. 扫描表达式字符=> c
若c是操作数，则c进操作数栈OPND
若c是 运算符，则与运算符栈OPTR的栈顶元素θ1比优先级并作相应操作：
c> θ1，则进栈；
c< θ1 ，则取出栈顶的运算符，并在数栈中连续取出两个栈顶元素作为运算对象进行运算，并将运算结果存入数栈。
c=θ1相等，弹出栈顶，脱括号
null算法中还调用了两个函数：
Precede( )的功能是判断两个运算符θ1和θ2的优先关系；
Operate( )的功能是求两数a和b作θ运算的结果。
nullOperandType EvaluationExpress()
{
InitStack (OPTR); Push(OPTR,’#’)
InitStack (OPND); c=getchar();
while(c!=‘#’ || GetTop(OPTR!=‘#’)) {
if(!In (c,OP))) //c不是运算符
{ Push (OPND,c); c=getchar(); }
else null switch (Precede(GetTop(OPTR),c))
{ case '<': Push(OPTR,c); c=getchar(); break;
case '=': Pop(OPTR,x); c=getchar(); break;
case '>': Pop(OPTR,theta);
Pop(OPND,b); Pop(OPND,a);
Push (OPND, Operate(a, theta,b));
break;
} //switch
} //while
return(GetTop(OPND));
}null*OPTR栈—存运算符、OPND栈—存操作数和结果。 例如：计算 3*(7-2) #null例 计算 2+4-3*6 （运算符栈底#省略）null 表达式的三种标识方法：设 Exp = S1 + OP + S2则称 OP + S1 + S2 为前缀表示法 S1 + OP + S2 为中缀表示法 S1 + S2 + OP 为后缀表示法 null例如: Exp = a b + (c d / e) f
前缀式: + a b c / d e f
中缀式: a b + c d / e f
后缀式: a b c d e / f + 结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;3）中缀式丢失了括弧信息，
致使运算的次序不确定;4)前缀式的运算规则为:
连续出现的两个操作数和在它们
之前且紧靠它们的运算符构成一
个最小表达式; 5)后缀式的运算规则为:
运算符在式中出现的顺序恰为
表达式的运算顺序;
每个运算符和在它之前出现 且
紧靠它的两个操作数构成一个最小
表达式。如何从后缀式求值？如何从后缀式求值？先找运算符， 再找操作数例如：
a b c d e / f +abd/ec-d/e(c-d/e)fnull表达式求值 中缀表达式 后缀表达式（RPN)
a*b+c ab*c+
a+b*c abc*+
a+(b*c+d)/e abc*d+e/+计算后缀表达式方法：
从左向右扫描表达式=>c
c是操作数,则入栈；
C是运算符，则从栈中取出两个操作数进行当前的计算，然后把结果再入栈；
直到整个表达式结束，这时送入栈顶的值就是结果。null后缀表达式求值步骤：
1、读入表达式一个字符
2、若是操作数，压入栈，转4
3、若是运算符，从栈中弹出2个数，将运算结果再压入栈
4、若表达式输入完毕，栈顶即表达式值；
若表达式未输入完，转1
例 计算 4+3*5后缀表达式：435*+null中缀表达式转换成后缀表达式算法1) 设立操作数栈；2) 设表达式的结束符为“#”，
予设运算符栈的栈底为“#”；3) 若当前字符是操作数，则直接发送给后缀式。4) 若当前运算符的优先数高于栈顶运算符，则进栈；5) 否则，退出栈顶运算符发送给后缀式； 6) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。第三章 栈和队列3.1 栈3.2 栈的应用举例3.3 栈与递归的实现3.4 队列第三章 栈和队列3.3 栈与递归的实现3.3 栈与递归的实现直接或间接地调用自身的算法称为递归算法
应用：
函数的递归定义
数据结构的递归定义
问题的递归求解
null例1 阶乘函数
阶乘函数可递归地定义为：边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。null例2 Fibonacci数列
无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。它可以递归地定义为：
边界条件递归方程第n个Fibonacci数可递归地计算如下：
public static int fibonacci(int n)
{
if (n <= 1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}null例3 Ackerman函数
当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。
Ackerman函数A(n，m)定义如下：
nullmain()
{ int n=4,m=2;
printf(" %ld\n",ackerman(n,m));}
long ackerman(n,m)
{ long y;
if (n==1 && m==0) y=2;
if (n==0 && m>=0) y=1;
if (m==0 && n>=2) y=n+2;
if (n>=1 && m>=1) y=ackerman(ackerman(n-1,m),m-1);
return y;}结果：16null栈实现递归现场保护：将主调函数的变量及返回地址保存。
参数传递：实参和虚参对应传递；
控制转移：将控制转移到被调用函数的入口。 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项工作：null恢复现场：恢复主调函数的变量信息；
结果返回：返回计算结果；
控制返回：将控制转移到主调函数。从被调用函数返回调用函数之前，应该完成下列三项任务：栈实现递归null多个函数嵌套调用的规则是：后调用先返回 ！此时的内存管理实行“栈式管理”例如：
void main( ){ void a( ){ void b( ){
… … …
a( ); b( );
… …
}//main }// a }// bMain的数据区函数a的数据区函数b的数据区 递归函数执行的过程可视为同一函数进行嵌套调用nullnullnull例3-2 Hanoi塔问题
设x,y,z是3个塔座。在塔座x上有一叠共n个圆盘，这些圆盘自下而上由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座x上的这一叠圆盘移到塔座Z上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：
规则1：每次只能移动1个圆盘；
规则2：不允许较大的圆盘压在较小的圆盘之上；
规则3：可将圆盘移至a,b,c中任一塔座上。nullvoid hanoi (int n, char x, char y, char z) {
// 将塔座x上按直径由小到大且至上而下编号为1至n
// 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。
if (n==1)
move(x, 1, z); // 将编号为１的圆盘从x移到z
else {
hanoi(n-1, x, z, y); // 将x上编号为１至n-1的
//圆盘移到y, z作辅助塔
move(x, n, z); // 将编号为n的圆盘从x移到z
hanoi(n-1, y, x, z); // 将y上编号为１至n-1的
//圆盘移到z, x作辅助塔
}
}null8 3 a b c返址 n x y z5 2 a c b5 1 a b c7 1 c a bvoid hanoi (int n, char x, char y, char z) {
1 if (n==1)
2 move(x, 1, z);
3 else {
4 hanoi(n-1, x, z, y);
5 move(x, n, z);
6 hanoi(n-1, y, x, z);
7 }
8 } 递归小结递归小结优点：易读、易写、易证明。
缺点：效率低——递归算法转换为非递归算法
递归中的重复子问题
第三章 栈和队列3.1 栈3.2 栈的应用举例3.3 栈与递归的实现3.4 队列第三章 栈和队列null3.4 队列
队列的定义及特点
定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表
队尾(rear)——允许插入的一端
队头(front)——允许删除的一端
队列特点：先进先出(FIFO)双端队列null ADT Queue {
数据对象：
D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0}
数据关系：
R1＝{ | ai-1, ai ∈D, i=2,...,n}
约定其中a1 端为队列头， an 端为队列尾基本操作：3.4 队列} ADT Queuenull队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit())InitQueue(&Q)
操作结果：构造一个空队列Q。
DestroyQueue(&Q)
初始条件：队列 Q已存在。
操作结果：队列Q被销毁， 不再存在。InitQueue(&Q)
操作结果：构造一个空队列Q。
DestroyQueue(&Q)
初始条件：队列 Q已存在。
操作结果：队列Q被销毁， 不再存在。 QueueEmpty(Q)
初始条件：队列Q已存在。
操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。
QueueLength(Q)
初始条件：队列Q已存在。
操作结果：返回Q的元素个数，即队列的长度。 QueueEmpty(Q)
初始条件：队列Q已存在。
操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。
QueueLength(Q)
初始条件：队列Q已存在。
操作结果：返回Q的元素个数，即队列的长度。ClearQueue(&Q)
初始条件：队列Q已存在。
操作结果：将Q清为空队列。
GetHead(Q, &e)
初始条件：Q为非空队列。
操作结果：用e返回Q的队头元素。ClearQueue(&Q)
初始条件：队列Q已存在。
操作结果：将Q清为空队列。
GetHead(Q, &e)
初始条件：Q为非空队列。
操作结果：用e返回Q的队头元素。a1a2an… … EnQueue(&Q, e)
初始条件：队列Q已存在。
操作结果：插入元素e为Q的新的队尾元素。 EnQueue(&Q, e)
初始条件：队列Q已存在。
操作结果：插入元素e为Q的新的队尾元素。a1a2ane … … DeQueue(&Q, &e)
初始条件：Q为非空队列。
操作结果：删除Q的队头元素，并用e返回其值a1a2an… … null链队列
结点定义typedef struct QNode
{ Qelemtype data;
struct QNode *next;
}Qnode, *QueuePtr;typedef struct{
QueuePtr front;
QueeuPtr rear;
} LinkQueue ; a1∧an…Q.front
Q.rearQ.front
Q.rear∧空队列nullnull构造空队列status InitQueue(LinkQueue &Q) {
Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode));
if (!Q.front) exit(overflow);
Q.front->next=NULL;
return OK;
}null销毁队列Qstatus DestoryQueue(LinkQueue&Q) {
while (Q.front) {
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}null入队算法status EnQueue(LinkQueue&Q,QElemType e)
{ p=(QueuePtr)malloc(sizeof(QNode));
if (!p) exit(overflow);
p->data=e; p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}∧算法思想：
1.建立结点
2.链到尾部
3.尾指针后移null出队算法status DeQueue(LinkQueue&Q,QElemType&e) {
if (Q.front==Q.rear) return(error);
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;//尾结点被删
free(p);
return OK;
}Front->nextQ.front->next算法思想：
1.队列判空
2.结点拆链
3.队列判空
4. 释放结点null顺序队列—队列的顺序存储表示。用一组地址连续的存储单元依次存放从队列头到队列尾的元素，指针front和rear分别指示队头元素和队尾元素的位置
插入新的队尾元素，尾指针增1，rear = rear + 1，
删除队头元素，头指针增1， front = front + 1，
因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。
队满时再进队将溢出
循环队列——队列的顺序表示和实现null循环队列——顺序映象 #define MAXQUEUESIZE 100
typedef struct {
Qelemtype *base;
int front， rear;
} sqQueue;
sqQueue Q;
null队列的顺序存储结构front=0
rear=0队空J1J2J3rear指示队尾元素；
front指示队头元素前一位置
初值front=rear=0空队列条件：front==rear
入队列：sq[++rear]=x;
出队列：x=sq[++front];null存在问题
设顺序空间为M，则：
当front=0,rear=M-1时，再有元素入队发生溢出—真溢出
当front0,rear=M-1时，再有元素入队发生溢出—假溢出
解决方案
队首固定，每次出队剩余元素向下移动——浪费时间
循环队列
基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;实现：利用“模”运算
入队： sq[rear]=x; rear=(rear+1)%M;
出队： x=sq[front]; front=(front+1)%M;
队满、队空判定条件null队空：front==rear
队满：front==rear解决方案：
1.另外设一个标志以区别队空、队满
2.少用一个元素空间：
队空：front==rear
队满：(rear+1)%M==frontnullnull构造空队列status initqueue(sqQueue&Q) {
Q.base=(Qelemtype*)malloc(
MAXQUEUESIZE*sizeof(Qelemtype));
if (!Q.base) exit(OVERFLOW);
Q.front=Q.rear=0;
return OK;
}null队列长度int queuelength(sqQueue Q)
{ return (Q.rear-Q.front+MAXQUEUESIZE)%MAXQUEUESIZE;
}null入队算法status EnQueue(SqQueue&Q, QelemType e)
{ if((Q.rear+1)%MAXQUEUESIZE==Q.front)
exit(overflow);
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQUEUESIZE;
return OK;
}null出队算法status DeQueue(SqQueue&Q, QelemType&e)
{ if (Q.front==Q.rear) exit(error);
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQUEUESIZE;
return OK;
}实验二：基于栈的四则运算实验二：基于栈的四则运算要求：
1.输入四则运算表达式，转换为后缀式并输出
2.利用后缀式完成四则运算并输出
步骤：
定义并实现顺序栈
利用字符数组存储四则运算运算符优先表
实现Precede()函数和Operate()函数
以字符串形式输入四则运算表达式，并转换为后缀表达式并输出
基于后缀表达式，完成四则运算，输出结果null栈顺序存储表示——顺序栈
# define STACK_INIT_SIZE 100
# define STACKINCREMENT 10 //存储空间增量
typedef struct
{ Selemtype *base;
Selemtype *top; //栈顶指针
int stacksize;
//当前已分配的存储空间，以元素为单位
} sqstack;
栈的基本操作：P46-47表3-1 运算符优先级关系表(θ1, θ2)*表3-1 运算符优先级关系表(θ1, θ2)θ2θ1null算法中还调用了两个函数：
Precede( )的功能是判断两个运算符θ1和θ2的优先关系；
Operate( )的功能是求两数a和b作θ运算的结果。
null中缀表达式转换成后缀表达式算法1) 设立操作数栈和运算符栈；2) 设表达式的结束符为“#”，
予设运算符栈的栈底为“#”；3) 若当前字符是操作数，则直接发送给后缀式。4) 若当前运算符的优先数高于栈顶运算符，则进栈；5) 否则，退出栈顶运算符发送给后缀式； 6) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。null本章小结
1. 掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。
2. 熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。
3. 熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。
浙公网安备 33021202002483