实验三栈和队列的应用
预备知识：
在实际应用中，有相当一类问题需要找出它的解集合，或者要求找出某些约束条件下的最优解。求解时经常使用一种称为回溯的方法来解决。所谓回溯就是走回路，该方法是在一定的约束下试探地搜索前进，若前进中受阻，则回头另择通路继续搜索。为了能够沿原路逆序回退，需用栈来保存曾经到达的每一个状态，栈顶的状态即为回退的第一站，因此回溯法均可利用栈来实现。而解决八皇后问题就是利用回溯法和栈来实现的。
一、八皇后问题
（一）设计要求与分析
八皇后问题是在８＊８的国际象棋棋盘上，安放８个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上皇后占据棋盘上的同一行、同一列或同一条对角线。
先将一些明显不满足问题要求的格局排除掉。每一行只放置一个皇后。因此将第i个皇后放置在第i行上，这样放置第i个皇后时，只要考虑它与前i-1皇后处于不同列和不同对角线即可。算法基本思想如下：
从第１行起逐行放置皇后，每放置一个皇后均需要依次对第１，２，…，８列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不与已放置的其它皇后冲突，则该行的位置保存在栈中，然后继续在下一行寻找安全位置；若当前试探的列位置不安全，则用下一列进行试探，当８列位置试探完毕都未找到安全位置，就退回到上一行，修改栈顶保存的皇后位置，然后继续试探。
算法描述：
１、置当前行当前列均为１；
２、While ( 当前行号≦８)
３、｛检查当前行，从当前列起逐列试探，寻找安全列号；
４、If (找到安全号)
５、 放置皇后，将列号记入栈中，并将下一行置成当前行，第１列置为当前行； ６、Else
７、
退栈回溯到上一行，移去该行已放置的皇后，以皇后所在列的下一列作为当前 列；
８、｝//结束程序
（二）算法求精
１、数据及其类型：
（１）i—当前行；j—当前列；
用数组s[1..8]表示顺序栈，下标表示皇后所在的行号，栈的内容是皇后所在的列号。
（２）检查皇后是否冲突
EnumBoolean {flase,true};
EnumBoolean a[9],b[17],c[17];
Ints[9];
其中，a[j]为真时，表示第j列上无皇后。
b[k]为真时，表示该方向“左/”的第k条线对角线上无皇后。其列坐标从2－16c[k]为真时，表示该方向“右\”的第k条线对角线上无皇后。其列坐标从-7－7b[i+j]和c[i-j+9]的真假就分别表示通过位置（i,j）的两条对角线上无皇后。
位置(i,j)的安全性可用a[i]&&b[i+j]&&c[i-j+9]表示。即在位置(i,j)上放置皇后后，相当于
将a[i]，b[i+j]和c[i-j+9]为假；移去(i,j)上的皇后相当于将a[i]，b[i+j]和c[i-j+9]为真。
voideightqueen1()
{int i,j;
for(i=2;i<=16;i++){
if(i>=2&&i<=9)a[i-1]=true;
b[i]=true;c[i]=true;
}
i=1;j=1;
while(i<=8){
while(j<=8){//在当前行i上寻找安全位置； if(a[i]&&b[i+j]&&c[i-j+9])break;
j++;
}
if(j<=8){//找到安全位置(i,j)
a[j]=false;b[i+j]=false;c[i-j+9]=false;
s[i]=j;//皇后位置j入栈
i++;j=1;//准备下一个皇后
}
else{
i--;j=s[i];//退栈，回溯到上一行
a[j]=true;b[i+j]=true;c[i-j+9]=true;
j++;//修改栈顶皇后的位置
}
}
｝
以上得到一个皇后的问题的解。
（三）算法扩充
要求出所有满足约束条件的解，关键在于以下两个问题：
从问题的一个解求出下一个解；确定所有解都已求出。
voideightqueen1()
{int i,j;
for(i=2;i<=16;i++){
if(i>=2&&i<=9)a[i-1]=true;
b[i]=true;c[i]=true;
}
i=1;j=1;
while(i>=1){//当i=0时终止循环
while(j<=8){//在当前行i上寻找安全位置； if(a[i]&&b[i+j]&&c[i-j+9])break;
j++;
}
if(j<=8){//找到安全位置(i,j)
a[j]=false;b[i+j]=false;c[i-j+9]=false;
s[i]=j;//皇后位置j入栈
if(i==8){//找到一个解，输出解
print();打印输出一个解
movequeen(i,j)//移去位置(i,j)上的皇后 i＝i-1;j=s[i];//退栈，回溯到上一个皇后 movequeen(i,j)//移去位置(i,j)上的皇后 j++;//修改栈顶皇后的位置
｝
else{
i++;j=1;//准备放置下一个皇后
｝
}
else{
i--;//退栈
if(i>=1){//栈不空，移去皇后
j=s[i];
movequeen(i,j);//移去皇后
j++;
}
}
｝
｝
（四）算法的实现
//**********************************
//求八皇后问题所有解的程序
//**********************************
enumBoolean {flase,true};
enumBoolean a[9],b[17],c[17];
ints[9];
#include<stdio.h>
voidmain()
{
viodprint( ),movequeen( ),eightqueen( );//函数声明 eightqueen();//调用求解八皇后问题
}
//在此位置插入eightqueen()函数
//*****************************
//打印输出一个解的函数
//*****************************
voidprint()
{intk;
printf(“\n行号：１２ ３ ４ ５ ６ ７ ８\n”);printf(“列号：”);
for(k=1;k<=8;k++)
printf(“%4d”,s[k];printf(“\n\n”));
}
voidmovequeen(int i,int j)
{a[j]=true;b[i+j]=true;c[i-j+9]=true;
}
二、算术表达式的求值问题
运算规则：有括号先算括号；无括号时，先做乘除法，再做加减法；对于相同级别的运算按
从左到右次序计算。
（一）设计要求与分析
问题：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，利用给定的算符
优先关系，实现对算术四则运算表达式的求值，并演示在求值过程中运算符栈、操作数栈、
输入字符和主要操作的变化过程。
算法思想：顺序扫描算术表达式，当读到数字时直接将其送至输出队列中；当读到运算符时，
将栈中所有优先级高于或等于该运算符的运算符弹出，送至输出队列中，再将当前运算符；
当读入左括号时，即入栈；当读入右括号时，将靠近栈顶的第一个左括号上面的运算符全部
依次弹出，送至输出队列中，再删除栈中的左括号。
（二）算法实现：
＃include<stdio.h>
#defineStackSize 100
#defineQueueSize 100
typedefchar DataType;
typedefstruct {
chardata[100];
intfront,rear;
}SeqQueue;//定义队列类型
voidinitQueue(SeqQueue *Q)//初始化队列
｛
Ｑ->front=0;Q->rear=0;
｝
voidQueueEmpty(SeqQueue *Q)
{
returnQ->front=Q->rear;
}
voidEnQueue(SeqQueue *Q,Datatype x)
{
If((Q->rear+1) %QueueSize==Q->front)
printf(“Queueoverflow”);
else
{Q->data[Q-rear]=x;
Q->rear=(Q->rear+1) %QueueSize ;}
}
typedefstruct{
Datatyepdata[100];
Inttop;
}SeqStack;//栈的类型定义
voidinitStack(SeqStack *S)
{
S->top=-1;
}
voidPush(SeqStack *S,DataType x)
{
If(S->top==StackSize=-1)
printf(“Stackoverflow”);
else{
S->top=S->top+1;
S->data[S->top]=x;
}
}
voidPop(SeqStack *S)
{
If(S->top== -1)
printf(“Stackunderflow”);
else{
returnS->data[S->top--];
}
}
voidGetTop(SeqStack *S)
{
If(S->top== -1)
printf(“Stackempty”);
else{
returnS->data[S->top];
}
}
voidmain()
{
SeqQueue*Q;
SeqQueuePostQ;
Q=&PostQ;
initQueue(Q);
CTpostExp(Q);
while(!QueueEmpty(Q))
printf(“%2c”,DeQueue(Q));
}