队列ADT

C语言中使用抽象数据类型方法编程的三个步骤

1. 以抽象、通用的方式描述一个类型，包括该类型的操作。
2. 设计一个函数接口表示这个新类型。
3. 编写具体代码实现这个接口。

定义队列抽象数据类型

队列（queue）是具有两个特殊属性的链表：

• 新项只能添加到链表末尾；
• 只能从链表开头移除项；

队列是一种先进先出（FIFO）的数据形式。

抽象定义：

定义接口（queue.h接口头文件）

//Queue的接口
#ifndef _QUEUE_H_
#define _QUEUE_H_
#include<stdbool.h>

typedef int Item;

#define MAXQUEUE 10

typedef struct node{
    Item item;
    struct node * next;
} Node;

typedef struct queue{
    Node * front;   //指向队列首项的指针 
    Node * rear;   //指向队列尾项的指针 
    int items;    //队列中的项数 
} Queue;

//初始化队列
void InitializeQueue(Queue * pq);

//检查队列是否已满
bool QueueIsFull(const Queue * pq);

//检查队列是否为空
bool QueueIsEmpty(const Queue * pq);

//确定队列中的项数
int QueueItemCount(const Queue * pq);

//在队列末尾添加项
bool EnQueue(Item item, Queue * pq);

//在队列开头删除项
bool DeQueue(Item *pitem, Queue * pq);

//清空队列
void EmptyTheQueue(Queue * pq);

#endif   

实现接口函数（queue.c）

//Queue类型的实现
#include<stdio.h>
#include<stdlib.h>
#include"queue.h"

//局部函数
static void CopyToNode(Item item, Node * pn);
static void CopyToItem(Node * pn, Item * pi);

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

bool QueueIsFull(const Queue * pq)
{
    return pq->items == MAXQUEUE; 
}

bool QueueIsEmpty(const Queue * pq)
{
    return pq->items == 0;    
}

int QueueItemCount(const Queue * pq)
{
    return pq->items;
}

bool EnQueue(Item item, Queue * pq)
{
    Node * pnew;

    if (QueueIsFull(pq))
        return false;
    pnew = (Node *)malloc(sizeof(Node));
    if (pnew == NULL)
    {
        fprintf(stderr, "Unable to allocate memory!\n");
        exit(1);
    }
    CopyToNode(item,pnew);
    pnew->next = NULL;
    if (QueueIsEmpty(pq))
        pq->front = pnew;      //项位于首端 
    else
        pq->rear->next = pnew; //项位于末端 
    pq->rear = pnew;
    pq->items++; //项数+1 

    return true;
}

bool DeQueue(Item * pitem, Queue * pq)
{
    Node * pt;

    if(QueueIsEmpty(pq))
        return false;
    CopyToItem(pq->front, pitem);
    pt = pq->front;
    pq->front = pq->front->next;
    free(pt);
    pq->items--;
    if(pq->items == 0)
        pq->rear == NULL;

    return true;

} 

void EmptyTheQueue(Queue * pq)
{
    Item dummy;
    while(!QueueIsEmpty(pq))
        DeQueue(&dummy, pq);
}

static void CopyToNode(Item item, Node * pn)
{
    pn->item = item;
 }

static void CopyToItem(Node * pn, Item * pi)
{
    *pi = pn->item;
 } 

测试队列（驱动程序 use_q.c）

//驱动程序测试Queue接口

#include<stdio.h>
#include"queue.h"

int main(void)
{
    Queue line;
    Item temp;
    char ch;

    InitializeQueue(&line);
    puts("Testing the Queue interface. Type a to add a value,");
    puts("type d to delete a value, and type q to quit.");
    while ((ch = getchar()) != 'q')
    {
        if (ch != 'a' && ch != 'd')
            continue;//忽略其他输出
        if (ch == 'a')
        {
            printf("Integer to add: ");
            scanf("%d", &temp);
            if (!QueueIsFull(&line))
            {
                printf("Putting %d into queue.\n", temp);
                EnQueue(temp,&line);
            }
            else
                puts("Queue is full!"); 
         }
        else
        {
            if(QueueIsEmpty(&line))
                puts("Nothing to delete.");
            else
            {
                DeQueue(&temp, &line);
                printf("Delete %d from queue.\n", temp);
            }    
        }
        printf("%d items in queue.\n", QueueItemCount(&line));
        puts("Type a to add. d to delete, q to quit:");
    }

    EmptyTheQueue(&line);
    puts("88");

    return 0;
}