(2)出队。
ElemType DeIQueue (STACK *SI,STACK kS2) { ElemType x;
if(S2->top! =-1) Pop (S2, &x); else{
while( 1Empty (S1)){
Pop (S1, &x); Push (S2,x); }
Pop (S2, &x); }
return X; }
(3)判断队空。
int EmptyQueue (STACK *S1, STACK *S2) { if(S1->top==-1 ＆＆S2->top==-l)
return 1; //两个栈同时为空，则表示队空 return O; //队不空，返回O }
2．注意两侧的铁道均为单向行驶道，且两侧不相通。故车辆都必须通过“栈道”进行调度。
typedef char ElemType;
int attemper (STACK *p, STACK *q)
{//将p栈道的车厢，经调度之后入q栈道，使软席车厢调整到硬席车厢之前 STACK *temp; ElemType e;
InitStack (temp); while(! Empty (p)){ P0p(p，＆e);
if(e=='S') Push(q，e); else Push (temp,e); }
while(! Empty (temp))
{ Pop (temp; &e); Push (q,e);} }
本题本质上是对两类数据执行排序操作，将其中一类置于另一类之前。 3．(1)递归算法如下： int gcd（int m，int n） { int k;
if(n==O) return (m);
else return (gcd (n, m%n)); }
(2)可以不使用栈而得到非递归函数gcd20如下： int gcd2 (int m，int n) { int r; do f
r=m%n. m=n; n=r;
} while (r); return m; )
(3)计算gcd(20，6)之值，栈变化过程如下图所示。
在top=3时，n的值为0，退栈，并返回2作为最后结果。 4．标志位tag的初值置为“0”。一旦元素入队，使rear==front时，需置tag为“1”;反之，一旦元素出队列使front=rear时，需置tag为“0”，以便使下一次进行入队列或出队列操作时(此时front= =rear)，可由标志位tag的值来区别队列当时的状态是“满”，还是“空”。
#define MaxSize 100 typedef struct f
ElemType data [MaxSize]; int front，rear; int tag; } SqQueue;
int EnQueue (SqQueue *q, ElemType e)
{/插入元素e为q的新队尾元素，如队列满，则置tag=l if(q->rear==q->front＆＆tag==l) return 0; q->data[q->rear] =e;
q->rear=(q->rear+l))%MaxSize; if(q->rear==q->front) tag=l; return 1： }
int DeQueue (SqQueue *q, ElemType *e)
{//若队列不空，则删除q的队头元素，用e返回;如队列空，则置tag=0 if (q->rear==q->front＆＆tag==0) return O; *e=q->data [q->front];
q->front=( q->front+l) %MaxSize; if (q->rear==q->front) tag=0; return 1; }
从空间角度看，设标记节省了一个空间(ElemType)，但在队列的使用过程中增加了算法复杂性。而不设标记正好相反。故当循环队列容量较小而队列中每个元素占的空间较多时，可通过在结构体中增加一个标记位来最大限度地使用循环队列容量。 5．依题意，定义单链表结点类型如下： typedef struct Lnode( ElemType data;
struct Lnode *next; }LinkNode;
根据单链表的特点，实现队列的5种运算的函数如下：
void SetNull (LinkNode **front, LinkNode **rear) { *f ront=NULL; *rear=NULL;)
int GetFirst (LinkNode *front, ElemType *x) { if (front==NULL) return O; else {
x=front->data; return 1;) }
int EnQueue (LinkNode **front, LinkNode **rear,ElemType x) { LinkNode *p;
if (*rear==NULL){//若队列为空，则直接建立一个链表 *rear=( LinkNode*)malloc( sizeof( LinkNode)); ( *rear) ->d.ata=x;*front=*rear; }
else { //若不为空，则建立一个结点将其链表链接到末尾 p= (LinkNode*)malloc (sizeof( LinkNode)); p->data=x; p->next=NULL; (*rear) ->next=p; *rear=p; }
return 1; }
int DeQueue (LinkNode **front, LinkNode**rear, ElemType *x) { LinkNode *p;
if (*front==NULL) return O; else{
p=*front; x=p->data; *front= (*front) ->next; free (p);
if (*front==NULL) *rear=NULL; return l; } }
int QueueEmpty (LinkNode **front) { if (*front==NULL) return l; else return O; }
6．这里使用的循环链表不带头结点，规定p始终指向队尾结点，p->next即为队头结点。当p= =NULL时队列为空。队列插入和删除算法如下： typedef struct node( ElemType data; struct node *next; } QNode;
void EnQueue (QNode **p, ElemType x) //队列插入 { QNode *s;
s= (QNode*)malloc( sizeof( QNode)); s->data=x; if (*p==NULL)(
*p=s; (*p)一>next=*p; } else{
s->next= (*p) ->next; //将s作为*p之后的结点 (*p) ->next=s;
*p=s; //*p指向*s } }
int DeQueue (QNode **p, ElemType *x) //队列删除 { QNode *s;
if (*p==NULL) return 0;
if( (*p)->next==NULL){ //只有一个结点的情况 x= (*p)->data; free (*p); *p=NUIL; }
else{//将*p之后结点的data域值赋给x，然后删除之 s= (*p) ->next; *x=s->data; (*p)->next=s->next; free (s); }
return 1; }
7．使用一个栈起到过渡的作用。先将sq队列中元素出队并将其入栈ss，直到队列空为止;然后初始化队列，即sq->front=sq->rear=n;再出栈并将其入队列，直到栈空为止。对应的算法如下： #define n 100
void reverse (squeue *sq) { ElemType x; STACK *ss;
ss- (STACK *)malloc (sizeof (STACK)); //栈初始化 ss->top=-l;
while(sq->front! =sq->rear){ //队不空时，出队并入栈 sq->front=(sq->front+l) %n;
if (sq->front==0) sq->front=n; //队列元素下标从1到n x=sq->data[sq->front];
ss->top++; ss->data[ ss->top]=x; //将x入栈 }
sq->front=sq->rear=n; while(ss->top>=0){ x=ss->data[ss->top]; ss->top--;
sq->rear=(sq->rear+l)%n;
sq->data[ sq->rear] =x; } }
8．计算Ack(m,n)的非递归算法为fun0函数。在fun0中采用一个二维数组作为栈，其内容如下：
st (top,O)存储标记，该标记为l(m=0)、2(m≠O，n=0)或3 (m+0, n+0)。 st (top,1)存储Ack (m,n)之值，初值为0。 st (top,2)存储m。 st (top,3)存储n。 #define MaxSize 5000
int no (int m，int n) //根据m，n之值返回相应的标志 { if(m==0) return 1; else if(n==O) return 2; else return 3： }
int fun (int m，int n)
{ int st [MaxSize][4],top=0, ml, nl; //top初值为O st [top] [0] =no (m,n); top++; //先移动栈指针
st [top] [1] =0; //初值O入栈 st [top] [2] =m; //初值m入栈 st [top] [3] =n; //初值n入栈 do{
if(st[top][1]==O)f if(st[top][O]==3){ top++; //入栈 st [top][1]=0;
st[top] [2]=st [top-l][2]; st [top][3]=st [top-l][3]-1;
st [top][0] =no (st[top][2], st[top] [3]); }
else if (st [top] [0] ==2){ top++; //入栈 st [top][1]=0;
st[top][2] =st [top-l] [2] -1; st [top][3] =1;
st[top] [0] =no(st[top] [2], st [top] [3]); }
if (st[top][0] ==1)
st[top] [1] =st[top][3]+1; //求值 }
if (top>=l&＆st[top] [1] !=0＆＆st [top-l] [0]==2){ st [top-l] [1] =st [top] [1]; top--; //出栈 }
else if (top>=l＆＆st[top] [1] 1=0＆&st[top一1][O]==3)f
nl=st [top] [1]; ml=st[top-l][2] -1; top--; //出栈 st [top] [1] =0; st [top] [2] =ml; st [top] [3] =nl;
st [top][0] =no (st [top] [2], st [top] [3]); }
if (top==l＆&st [top] [1] !=0) break;
//栈中只有1个元素，且已计算出值，则退出循环 )while (top>=l);
return (st [1] [1]); //st [1][1]就是所求的函数值 }