抽象数据类型之队列ADT接口包

mingcxx

这个是队列ADT的接口包了，只是一些简单的功能。以后需要什么再向里面添加就行。

//queue.h -- 队列接口头文件

#ifndef _QUEUE_H_
#define _QUEUE_H_

#include <stdbool.h>

/*在这里键入Item的类型定义*/
//例如
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;

/*操作：初始化队列
操作前：pq指向一个队列
操作后：该队列被初始化为空队列*/
void InitializeQueue(Queue * pq);


/*操作：检查队列是否为空
操作前：pq指向一个已初始化的队列
操作后：如果队列为空，则返回true；
否则返回false*/
bool QueueIsEmpty(const Queue * pq);


/*操作：检查队列是否已满
操作前：pq指向一个已初始化的队列
操作后：如果队列已满，则返回true；
否则返回false*/
bool QueueIsFull(const Queue * pq);


/*操作：确定队列中项目的个数
操作前：pq指向一个已初始化的队列
操作后：返回一个队列中项目的个数*/
int QueueItemCount(const Queue * pq);


/*操作：向队列尾端添加项目
操作前：pq指向一个已初始化的队列
item是要添加到队列尾的项目
操作后：如果队列未满，则将该项目
添加到队列尾，函数返回true；否则
返回false*/
bool EnQueue(Item item, Queue * pq);


/*操作：从队列首端删除项目
操作前：pq指向一个已初始化的队列
操作后：如果队列非空，队列首端的
项目被复制到*pitem,并从队列中删
除，函数返回true；如果这个操作使
队列为空，把队列重置为空队列
如果队列开始时为空，不改变队列，
函数返回false*/
bool DeQueue(Item * pitem, Queue * pq);


/*操作：清空队列
操作前：pq指向一个已经初始化的队列
操作后：队列被清空*/
void EmptyTheQueue(Queue * pq);


#endif // !_QUEUE_H_

//queue.c -- 队列类型的实现文件

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


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

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

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

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

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(EXIT_FAILURE);
        }

        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 item;

        while (!QueueIsEmpty(pq))
        {
                DeQueue(&item, pq);
        }
}

//局部函数定义
static void CopyToNode(Item item, Node * pnode)
{
        pnode->item = item;
}

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