抽象数据类型(ADT)—

抽象数据类型(ADT)——队列

作者：追风剑情发布于：2020-4-22 10:34 分类：C

示例：实现一个队列

queue.h

//#pragma once
#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;
 
/* 操作:		初始化队列		*/
/* 前提条件:	pq指向一个队列	*/
/* 后置条件:	队列被初始化	*/
void InitializeQueue(Queue * pq);
 
/* 操作:		检查队列是否已满						*/
/* 前提条件:	pq指向之前被初始化的队列				*/
/* 后置条件:	如果队列已满则返回true，否则返回false	*/
bool QueueIsFull(const Queue * pq);
 
/* 操作:		检查队列是否为空						*/
/* 前提条件:	pq指向之前被初始化的队列				*/
/* 后置条件:	如果队列为空则返回true，否则返回false	*/
bool QueueIsEmpty(const Queue * pq);
 
/* 操作:		确定队列中的项数						*/
/* 前提条件:	pq指向之前被初始化的队列				*/
/* 后置条件:	返回队列中的项数						*/
int QueueItemCount(const Queue * pq);
 
/* 操作:		在队列末尾添加项						*/
/* 前提条件:	pq指向之前被初始化的队列				*/
/*				item是要被添加在队列末尾的项			*/
/* 后置条件:	如果队列不为空，item将被添加在队列的末尾*/
/*				该函数返回true；否则，队列不变，该函数返回false*/
bool EnQueue(Item item, Queue * pq);
 
/* 操作:		从队列的开头删除项						*/
/* 前提条件:	pq指向之前被初始化的队列				*/
/* 后置条件:	如果队列不为空，队列首端的item将被拷贝到*pitem中 */
/*				如果该操作使得队列为空，则重置队列为空	*/
/*				如果队列在操作前为空，该函数返回false	*/
bool DeQueue(Item * pitem, Queue * pq);
 
/* 操作:		清空队列								*/
/* 前提条件:	pq指向之前被初始化的队列				*/
/* 后置条件:	队列被清空								*/
void EmptyTheQueue(Queue * pq);
 
#endif

queue.c

#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;
}

main.c

#define _CRT_SECURE_NO_WARNINGS
//可以用#ifndef指令，防止多次包含一个文件
#include <stdio.h>
//提供malloc()原型
#include <stdlib.h>
//提供strcpy()原型
#include <string.h>
//提供CHAR_BIT的定义，CHAR_BIT表示每字节的位数
#include <limits.h>
//C99定义了bool、true、false
//如果编译器不支持bool,可以用枚举替代enum bool {false, true};
#include <stdbool.h>
#include "queue.h"
 
int main(int argc, char* argv[])
{
	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("Removing %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("Bye!");
 
	system("pause");
	return 0;
}