3.29.c

数据结构习题及答案

3.29③ 如果希望循环队列中的元素都能得到利用，
则需设置一个标志域tag，并以tag的值为0或1来区
分，尾指针和头指针值相同时的队列状态是"空"还
是"满"。试编写与此结构相应的入队列和出队列的
算法，并从时间和空间角度讨论设标志和不设标志
这两种方法的使用范围（比如，当循环队列容量较
小而队列中每个元素占的空间较多时，那一种方法
较好？）。

实现下列函数：
Status EnCQueue(CTagQueue &Q, QElemType x);
Status DeCQueue(CTagQueue &Q, QElemType &x);

本题的循环队列CTagQueue的类型定义如下：
typedef char QElemType;
typedef struct {
    QElemType elem[MAXQSIZE];
    int tag;
    int front;
    int rear;
} CTagQueue;
Status EnCQueue(CTagQueue &Q, QElemType x)
{ 
  if(Q.front==Q.rear&&Q.tag==1)  return ERROR;  //没有空间剩余
  Q.elem[Q.rear]=x;
  Q.rear=(Q.rear+1+MAXQSIZE)%MAXSIZE;
  if(Q.front==Q.rear) Q.tag=1;                     //队列满
  return OK;
}

Status DeCQueue(CTagQueue &Q, QElemType &x)
{ if(Q.front==Q.rear&&Q.tag==0) return ERROR; //队列为空
  x=Q.elem[Q.front];
  Q.front=(Q.front+1+MAXSIZE)%MAXSIZE;
  if(Q.front==Q.rear) Q.tag=0;                     //队列空
  return OK;   
}