akm(1
3) 6 1 3 g=akm(1
2); akm(m-1
g)
2
akm(1
2) 6 1 2 g=akm(1
1); akm(m-1
g)
3
akm(1
1) 6 1 1 g=akm(1
0)=2; akm(m-1
g)=akm(0
2)
4
akm(0
2) 7 0 2 akm=n+1=3 退栈
akm(2
1) 0 2 1 g=akm(2
0)=3; akm=akm(1
3)
1
akm(1
3) 6 1 3 g=akm(1
2); akm(m-1
g)
2
akm(1
2) 6 1 2 g=akm(1
1); akm(m-1
g)
3
akm(1
1) 6 1 1 g=akm(1
0)=2; akm(m-1
g)=akm(0
2)=3退栈
akm(2
1) 0 2 1 g=akm(2
0)=3; akm=akm(1
3)
1
akm(1
3) 6 1 3 g=akm(1
2); akm(m-1
g)
2
akm(1
2) 6 1 2 g=akm(1
1)=3; akm(m-1
g)=akm(0
3)
3
akm(0
3) 7 0 3 akm=n+1=4 退栈
akm(2
1) 0 2 1 g=akm(2
0)=3; akm=akm(1
3)
1
akm(1
3) 6 1 3 g=akm(1
2); akm(m-1
g)
2
akm(1
2) 6 1 2 g=akm(1
1)=3; akm(m-1
g)=akm(0
3)=4 退栈
akm(2
1) 0 2 1 g=akm(2
0)=3; akm=akm(1
3)
1
akm(1
3) 6 1 3 g=akm(1
2)=4; akm(m-1
g)=akm(0
4)
2
akm(0
4) 7 0 4 akm=n+1=5 退栈
akm(2
1) 0 2 1 g=akm(2
0)=3; akm=akm(1
3)
1
akm(1
3) 6 1 3 g=akm(1
2)=4; akm(m-1
g)=akm(0
4)=5退栈
akm(2
1) 0 2 1 g=akm(2
0)=3; akm=akm(1
3)=5退栈
akm(2
1)=5;
3.28 假设以带头结点的循环链表表示队列
并且只设一个指针指向队尾元素结点（注意不设头指针） 试编写相应的队列初始化、入队列何处队列的算法
解：
typedef int ElemType;
typedef struct NodeType{
ElemType data;
NodeType *next;
}QNode
*QPtr;
typedef struct{
QPtr rear;
int size;
}Queue;
Status InitQueue(Queue& q)
{
q.rear=NULL;
q.size=0;
return OK;
}
Status EnQueue(Queue& q
ElemType e)
{
QPtr p;
p=new QNode;
if(!p) return FALSE;
p->data=e;
if(!q.rear){
q.rear=p;
p->next=q.rear;
}
else{
p->next=q.rear->next;
q.rear->next=p;
q.rear=p;
}
q.size++;
return OK;
}
Status DeQueue(Queue& q
ElemType& e)
{
QPtr p;
if(q.size==0)return FALSE;
if(q.size==1){
p=q.rear;
e=p->data;
q.rear=NULL;
delete p;
}
else{
p=q.rear->next;
e=p->data;
q.rear->next=p->next;
delete p;
}
q.size--;
return OK;
}
3.29 如果希望循环队列中的元素都能得到利用 则需设置一个标志域tag
并以tag的值为0和1来区分