int x; SeqStack S; InitStack( &S);
while (! QueueEmpty( Q ))
{x=DeQueue( Q); Push( &S,x);} while (! StackEmpty( &s))
{ x=Pop(&S); EnQueue( Q,x );} }// Demo3
(5) CirQueue Q1, Q2; // 设DataType 为int 型 int x, i , n= 0;
... // 设Q1已有内容， Q2已初始化过 while ( ! QueueEmpty( &Q1) )
{ x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;} for (i=0; i< n; i++) { x=DeQueue(&Q2) ;
EnQueue( &Q1, x) ; EnQueue( &Q2, x);}
答：
(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。 (2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。
(3)程序段的功能是利用栈T，将一个非空栈S中值等于m的元素全部删去。 (4)程序段的功能是将一个循环队列Q经过S栈的处理，反向排列，原来的队头变成队尾，原来的队尾变成队头。
(5)这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。 关闭
3.6 回文是指正读反读均相同的字符序列，如\和\均是回文，但\不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 解：
根据提示，算法可设计为： //以下为顺序栈的存储结构定义
#define StackSize 100 //假定预分配的栈空间最多为100个元素 typedef char DataType;//假定栈元素的数据类型为字符 typedef struct{
DataType data[StackSize]; int top; }SeqStack;
int IsHuiwen( char *t)
{//判断t字符向量是否为回文，若是，返回1，否则返回0 SeqStack s; int i , len;
char temp;
InitStack( &s);
len=strlen(t); //求向量长度
for ( i=0; i while( !EmptyStack( &s)) {// 每弹出一个字符与相应字符比较 temp=Pop (&s); if( temp!=S) return 0 ;// 不等则返回0 else i++; } return 1 ; // 比较完毕均相等则返回 1 } 关闭 3.7 利用栈的基本操作，写一个将栈S中所有结点均删去的算法void ClearStack( SeqStack *S)，并说明S为何要作为指针参数? 解： 算法如下 void ClearStack (SeqStack *S) { // 删除栈中所有结点 S->Top = -1; //其实只是将栈置空 } 因为要置空的是栈S，如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。 关闭 3.8 利用栈的基本操作， 写一个返回S中结点个数的算法 int StackSize( SeqStack S),并说明S为何不作为指针参数? 解： 算法如下： int StackSize (SeqStack S) {//计算栈中结点个数 int n=0; if(!EmptyStack(&S)) { Pop(&S); n++; } return n; } 上述算法的目的只要得到S栈的结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数，以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数。 关闭 3.9 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示： 对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。 解： 根据提示，可以设计算法如下： int PairBracket( char *SR) {//检查表达式ST中括号是否配对 int i; SeqStack S; //定义一个栈 InitStack (&s); for (i=0; i if ( S=='(' ) Push(&S, SR); //遇'('时进栈 if ( S==')' ) //遇')' if (!StackEmpty(S))//栈不为空时，将栈顶元素出栈 Pop(&s); else return 0;//不匹配，返回0 } if EmptyStack(&s) return 1;// 匹配，返回1 else return 0;//不匹配，返回0 } 关闭 3.10 一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。 解： 双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下： //双向栈的栈结构类型与以前定义略有不同 #define StackSize 100 // 假定分配了100个元素的向量空间 #define char DataType typedef struct{ DataType Data[StackSize] int top0; //需设两个指针 int top1; }DblStack void InitStack( DblStack *S ) { //初始化双向栈 S->top0 = -1; S->top1 = StackSize; //这里的top2也指出了向量空间，但由于是作为栈底，因此不会出错 } int EmptyStack( DblStack *S, int i ) { //判栈空(栈号 i) return (i == 0 && S->top0 == -1|| i == 1 && S->top1== StackSize) ; } int FullStack( DblStack *S) { //判栈满,满时肯定两头相遇 return (S->top0 == S-top1-1); } void Push(DblStack *S, int i, DataType x) { //进栈(栈号i) if (FullStack( S )) Error(\上溢、退出运行 if ( i == 0) S->Data[ ++ S->top0]= x; //栈0入栈 if ( i == 1) S->Data[ -- S->top1]= x; // 栈1入栈 } DataType Pop(DblStack *S, int i) { //出栈(栈号i) if (EmptyStack ( S,i) ) Error(\下溢退出 if( i==0 ) return ( S->Data[ S->top0--] );//返回栈顶元素，指针值减1 if( i==1 ) return ( S->Data[ S->top1++] ); //因为这个栈是以另一端为底的，所以指针值加1。 } 关闭 3.11 Ackerman 函数定义如下：请写出递归算法。 ┌ n+1 当m=0时 AKM ( m , n ) = │ AKM( m-1 ,1) 当m≠0 ，n=0时 └ AKM( m-1, AKM( m,n-1)) 当m≠0, n ≠ 0时 解： 算法如下 int AKM( int m, int n) { if ( m== 0) return n+1; if ( m<>0 && n==0 ) return AKM( m-1, 1); if ( m<>0 && n<>0 ) return AKM( m-1, AKM( m, n-1)); } 关闭 3.12 用第二种方法 ，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。 解： 算法设计如下: //循环队列的定义 #define QueueSize 100 typedef char Datatype ; //设元素的类型为char型 typedef struct { int front; int rear; DataType Data[QueueSize]; }CirQueue; (1)置空队 void InitQueue ( CirQueue *Q) { // 置空队 Q->front=Q->rear=0; } (2)判队空 int EmptyQueue( CirQueue *Q) { //判队空 return Q->front==Q->rear; } (3)判队满 int FullQueue( CirQueue *Q) { // 判队满//如果尾指针加1后等于头指针，则认为满 return (Q->rear+1)%QueueSize== Q->front; } (4)出队 DataType DeQueue( CirQueue *Q) { //出队 DataType temp; if(EmptyQueue(Q)) Error(\队已空，无元素可以出队\ temp=Q->Data[Q->front] ;//保存元素值 Q->front= ( Q->front+1 ) %QueueSize;//循环意义上的加1 return temp; //返回元素值 } (5)入队 void EnQueue (CirQueue *Q, DataType x) { // 入队 if( FullQueue( Q))