C Primer+Plus（十七）高级数据表示（二）

第十七章高级数据表示

三、队列ADT

前面通过一个单链表形式来构建一个数据堆，单链表是通过在结点中设置一个指向下一节点的指针成员来实现组合。对于队列形式，有几个特点：1、依然是线性序列；2、只能在队尾部增加节点；3、只能在队首部删除节点。

1、队列ADT的定义描述

//依据实际需求定制Item内容
typedef something Item;

//对队列节点的描述与链表类似，通过保存后续节点地址即可连接
typedef struct node
{
   Item item;
   struct node *next;
}Node;

//依据队列的特点，通过描述队列首节点和尾节点来描述队列，同时增加了队列的长度。
typedef struct queue
{
    Node *front;
    Node *rear;
    int size;
}Queue；

2、队列ADT的操作描述及实现

（1）初始化一个队列：队首指向空，队尾指向空，同时节点数置零。

void InitializeQueue(Queue *pq)
{
    pq->front=NULL;
    pq->rear=NULL;
    pq->size=0;
}

(2)判断队列是否已满，判断队列是否空。这里因为描述队列的数据类型Queue中已有一个描述节点数量的成员，所以很简单实现。这里以判断是否为满为例（假设队列节点上限为Max_number)：

int QueueIsFull(const Queue *pq)
{
   if(pq->size==Max_number)
       return 1;
   else return 0;
}

（3）添加元素：队列中只能在队列尾部添加节点。那我们设想该函数的参数应该有两个：队列参数以及节点参数。可看书上却采用了队列参数和项目参数，这里面有什么讲究的地方么？

因为对于数据堆使用者而言，他不关心数据堆是怎么建立起来的，不关心数据堆中的节点是何种方式描述，他更关心实际应用中的项目以及依据这个项目创建的这个ADT可以提供哪些功能接口（即操作）。所以这里参数选用队列和项目作为参数。（当然用节点作为参数也绝对可行，只是这样的话使用者就必须清楚这些节点的信息细节，实际上他们是无需关心的）。

int EnQueue(Item item,Queue *pq)
{
   Node *newnod;
//若队列满，则退出，返回0   
   if(QueueIsFull(pq))
   {     printf("The Queue is Full.Cann't ADDing.
");
          return 0;
    }
//分配空间
    newnode=(Node*)malloc(sizeof(Node));
    if(newnode==NULL)
    {     printf("RAM is Full.Malloc Error.
");
          return 0;
    }
//分配空间成功则构造节点
    newnode->item=item;       //添加项目信息至节点
    newnode->next=NULL;      //因为添加在队尾，所以设其next为空

    if(QueueIsEmpty(pq))      //若队空，则将队首队尾都指向该节点
          pq->front=pq->rear=newnode;
     else
     {        
          pq->rear->next=newnode;   //之前队尾节点指向新增节点
          pq->rear=newnode;           //新队列的队尾成员指向新增节点
    }
     pq->size++;
     return 1;
}

(4)删除元素：同样以项目和队列作为参数。队列的删除很简单，因为是从队首出列的。

//书上的实现是通过两个参数：一个项目类型参数，以及一个队列类型参数
//通过删除队首节点，并将该节点内的项目传递给项目参数
//下面换另外一种方式实现，因为对队列进行删除节点的话，一定是从队首
//因此仅用队列作为参数，同时将被删除节点的项目作为返回值
Item DeQueue(Queue *pq)
{
   Node *newnode;
   Item pitem;
   if(QueueIsEmpty(pq))
   {
       printf("DELETING Error:Queue is emty!
");
       exit(1);
   }
   newnode=pq->front;
   if(QueueItemCount(pq)==1)
   {
        pq->front=NULL;
        pq->rear=NULL;
    }
    else 
        pq->front=pq->front->next;
    pitem=newnode->item;
    free(newnode);
    pq->size--;
    return pitem;
}

(5)清空队列：从队首开始，逐个删除节点、释放空间

void EmptyQueue(Queue *pq)
{
    node *newnode;
    while(pq->front!=NULL)
    {
       newnode=pq->front;
       pq->front=pq->front->next;
       free(newnode);
     }
}

如果利用删除元素的接口就更简单：

void EmptyQueue(Queue *pq)
{  Item pitem;
   while(!QueueIsEmpty(pq))
      pitem=DeQueue(pq);
}