queue.h

1 #ifndef _QUEUE_H_ 2 #define _QUEUE_H_ 3 #include 
     
       4 #define MAXQUEUE 10 5  6 // 定义队列类型 7 typedef int Item;  8  9 // 队列的节点10 typedef struct node11 {12     Item item;13     struct node * next;14 }Node;15 16 typedef struct queue17 {18     Node * front; // 记录队列的第一项19     Node * rear; // 记录队列的最后一项20     int items; // 记录项数21 }Queue;22 23 void InitQueue(Queue * pq);24 bool QueueIsFull(const Queue * pq);25 bool QueueIsEmpty(const Queue * pq);26 int QueueItemCount(const Queue * pq);27 bool EnQueue(Item item, Queue * pq);28 bool DeQueue(Item * pitem, Queue * pq);29 void EmptyTheQueue(Queue * pq);30 31 #endif
     

use_q.c /*功能函数的实现*/

1 #include 
     
       2 #include 
      
        3 #include "queue.h" 4  5 static void CopyToNode(Item item, Node * pn) // 将内容复制到节点中 6 { 7     pn->item = item; 8 } 9 static void CopyToItem(Node * pn, Item * pi) //将一个项中的item内容复制给一个Item变量 10 {11     *pi = pn->item;12 }13 14 void InitQueue(Queue * pq) // 初始化队列15 {16     pq->front = pq->rear = NULL; // 将队列的首尾指针都初始化为NULL17     pq->items = 0;// 将项数初始化为018 }19 bool QueueIsFull(const Queue * pq) 20 {21     return pq->items == MAXQUEUE;22 }23 bool QueueIsEmpty(const Queue * pq)24 {25     return pq->items == 0;26 }27 int QueueItemCount(const Queue * pq)28 {29     return pq->items;30 }31 bool EnQueue(Item item, Queue * pq) // 在队列最后添加项32 {33     Node * pnew; // 创建一个新的节点34     35     if (QueueIsFull(pq))36         return false;37     pnew = (Node *)malloc(sizeof(Node)); // 为新节点申请空间38     if (pnew == NULL)39     {40         fprintf(stderr, "Unable to allocate memory!\n");41         exit(EXIT_FAILURE);42     }43     CopyToNode(item, pnew); // 把item内容复制到新节点中44     pnew->next = NULL; // 将新节点的next成员置为NULL，以表明这是当前队列的最后一项45     if (QueueIsEmpty(pq)) // 如果队列是空的，将新节点作为队列的头项46         pq->front = pnew;47     else // 否则将新节点的地址放在队列尾项的next成员中48         pq->rear->next = pnew;49     pq->rear = pnew; // 将新节点作为队列的尾项50     pq->items++;51     52     return true;53 }54 55 bool DeQueue(Item * pitem, Queue * pq)56 {57     Node * pt;58     // 这里的 pitem 和 pt 都用来存放删除项的内容  59     if (QueueIsEmpty(pq))60         return false;61     // 将删除项的内容复制给临时指针中62     CopyToItem(pq->front, pitem);63     pt = pq->front;64     65     pq->front = pq->front->next;66     free(pt);67     pq->items--;68     if (pq->items == 0) // 在删除最后一项时，要将尾指针和头指针同时设为NULL。69         pq->rear = NULL;70     return true;71 }72 void EmptyTheQueue(Queue * pq)73 {74     Item dummy;75     while (!QueueIsEmpty(pq))76         DeQueue(&dummy, pq);77 }
      
     

main.c /* 用户接口 */

1 #include 
     
       2 #include "queue.h" 3  4 int main(void) 5 { 6     Queue line; 7     Item temp; 8     char ch; 9 10     InitQueue(&line);11     puts("Testing the Queue interface.Type a to add a value,");12     puts("type d to delete a value,and type q to quit.");13     while ((ch = getchar()) != 'q')14     {15         if (ch != 'a'&&ch != 'd')16             continue;17         if (ch == 'a')18         {19             printf("Interger to add:");20             scanf("%d", &temp);21             if (!QueueIsFull(&line))22             {23                 printf("Putting %d into queue\n", temp);24                 EnQueue(temp, &line);25             }26             else27                 puts("Queue is full!");28         }29         else30         {31             if (QueueIsEmpty(&line))32                 puts("Nothing to delete!");33             else34             {35                 DeQueue(&temp, &line);36                 printf("%Removing %d from queue\n", temp);37             }38         }39         printf("%d items in queue\n", QueueItemCount(&line));40         puts("Type a to add,d to delete,q to quit:");41     }42     EmptyTheQueue(&line);43     puts("Bye!");44 45     return 0;46 }