(三)数据结构之线性表的简单实现：队列

朱雀 2022-06-08 06:13 130阅读 0赞

## 1、队列的简单定义 ##

队列：具有一定操作约束的线性表；只能在一端插入，在另一端删除；先进先出：First In First Out（FIFO）。

## 2、队列的顺从存储实现 ##

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素的位置变量rear组成。为了不造成存储空间上的浪费常定义位循环队列。

### 2.1 基本数据结构 ###

/* 定义队列的基本数据结果 */
    #define MaxSize		20
    typedef int ElementType;
    typedef struct _Queue{
    	ElementType Data[ MaxSize ];
    	int rear;
    	int front;
    } Queue;

### 2.2 创建一个空队列 ###

/* 创建一个空队列 */
    Queue *CreatQueue()
    {
    	Queue *Q = (Queue*)malloc(sizeof(Queue));
    	if(NULL != Q)
    	{
    		Q->front = 0;
    		Q->rear = 0;
    	}
    	return Q;
    }

### 2.3 插入操作 ###

/* 向循环队列尾部插入一个元素 */
    void AddQ( Queue *PtrQ, ElementType item)
    {
    	if ( IsFullQ(PtrQ) )
    	{
    		printf("The queue is full!\n");
    		return;
    	}
    	PtrQ->rear = (PtrQ->rear+1)% MaxSize;
    	PtrQ->Data[PtrQ->rear] = item;
    }

### 2.4 删除操作 ###

/* 删除循环队列的队头的元素 */
    ElementType DeleteQ ( Queue *PtrQ )
    {
    	if ( IsEmptyQ(PtrQ) ) 
    	{
    		printf("The queue is empty!\n");
    		return -1;
    	} 
    	else 
    	{
    		PtrQ->front = (PtrQ->front+1)% MaxSize;
    		return PtrQ->Data[PtrQ->front];
    	}
    }

### 2.5 完整的示例代码实现 ###

/* 循环队列的顺序存储实现 */
    #include <stdio.h>
    #include <stdlib.h>
    
    /* 定义队列的基本数据结果 */
    #define MaxSize		20
    typedef int ElementType;
    typedef struct _Queue{
    	ElementType Data[ MaxSize ];
    	int rear;
    	int front;
    } Queue;
    
    /* 创建一个空队列 */
    Queue *CreatQueue()
    {
    	Queue *Q = (Queue*)malloc(sizeof(Queue));
    	if(NULL != Q)
    	{
    		Q->front = 0;
    		Q->rear = 0;
    	}
    	return Q;
    }
    
    /* 消除一个队列 */
    void DestroyQueue(Queue *PtrQ)
    {
    	if(NULL != PtrQ)
    		free(PtrQ);
    	PtrQ = NULL;
    }
    
    /* 判断队列是否为空，1为空，0非空 */
    int IsEmptyQ( Queue *PtrQ )
    {
    	return (PtrQ->front == PtrQ->rear);
    }
    
    /* 判断队列是否为满，1为满，0为空 */
    int IsFullQ( Queue *PtrQ )
    {
    	return ((PtrQ->rear+1)%MaxSize == PtrQ->front);
    }
    
    /* 向循环队列尾部插入一个元素 */
    void AddQ( Queue *PtrQ, ElementType item)
    {
    	if ( IsFullQ(PtrQ) )
    	{
    		printf("The queue is full!\n");
    		return;
    	}
    	PtrQ->rear = (PtrQ->rear+1)% MaxSize;
    	PtrQ->Data[PtrQ->rear] = item;
    }
    
    /* 删除循环队列的队头的元素 */
    ElementType DeleteQ ( Queue *PtrQ )
    {
    	if ( IsEmptyQ(PtrQ) ) 
    	{
    		printf("The queue is empty!\n");
    		return -1;
    	} 
    	else 
    	{
    		PtrQ->front = (PtrQ->front+1)% MaxSize;
    		return PtrQ->Data[PtrQ->front];
    	}
    }
    
    /* 遍历一个循环队列 */
    void TraversalQ( Queue *PtrQ )
    {
    	int front, rear, i;
    	if(!IsEmptyQ(PtrQ))
    	{
    		front = PtrQ->front;
    		rear = PtrQ->rear;
    		for(i = front; i != rear; i = (i+1)%MaxSize)
    			printf("%d ", PtrQ->Data[(i+1)%MaxSize]);
    		printf("\n");
    	}
    }
    
    
    /* 程序入口 */
    int main()
    {
    	int i;
    	ElementType temp;
    	Queue *queue = NULL;
    
    	/* 创建一个循环队列 */
    	queue = CreatQueue();
    	if(NULL == queue)
    	{
    		printf("CreatQueue is failed!\n");
    		return -1;
    	}
    
    	/* 向循环队列中插入五个元素 */
    	printf("Input 5 numbers : ");
    	for(i = 0; i < 5; i++)
    	{
    		scanf("%d", &temp);
    		AddQ(queue, temp);
    	}
    
    	printf("****************************************TraversalQ*******************************\n");
    	TraversalQ(queue);
    
    	printf("****************************************AddQ once********************************\n");
    	printf("Input 1 number : ");
    	scanf("%d", &temp);
    	AddQ(queue, temp);
    	TraversalQ(queue);
    
    	printf("****************************************DeleteQ twice****************************\n");
    	DeleteQ(queue);
    	DeleteQ(queue);
    	TraversalQ(queue);
    
    	DestroyQueue(queue);	// 销毁一个循环队列
    
    	return 0;
    }

## 3、队列的链式存储实现 ##

队列的链式存储结构也可以用一个单链表实现。删除和插入操作分别在链表的两头进行，执行删除的一端是表头，执行插入的一端是表尾。

### 3.1 基本数据结构实现 ###

/* 定义链式队列的基本数据结构 */
    typedef int ElementType;
    typedef struct Node{
    	ElementType Data;
    	struct Node *Next;
    }QNode;
    typedef struct { 		/* 链队列结构 */
    	QNode *rear; 		/* 指向队尾结点 */
    	QNode *front; 		/* 指向队头结点 */
    } LinkQueue;

### 3.2 创建一个空队列 ###

/* 创建一个空队列 */
    LinkQueue *CreatQueue()
    {
    	LinkQueue *Q = (LinkQueue *)malloc(sizeof(LinkQueue));
    	if(NULL != Q)
    	{
    		Q->front = NULL;
    		Q->rear = NULL;
    	}
    	return Q;
    }

### 3.3 插入操作 ###

/* 向队列尾部插入一个元素 */
    void AddQ( LinkQueue *PtrQ, ElementType item)
    {
    	QNode *TempCell = NULL;
    
    	TempCell = (QNode*)malloc(sizeof(QNode));
    	if(NULL == TempCell)
    	{
    		printf("Malloc is failed!\n");
    		return;
    	}
    	TempCell->Data = item;	// 赋值给分配的结点
    	if ( IsEmptyQ(PtrQ) ) 	// 判断队列是否为空
    	{
    		PtrQ->rear = PtrQ->front= TempCell;
    		TempCell->Next = NULL;
    	}
    	else
    	{
    		PtrQ->rear->Next = TempCell;
    		TempCell->Next = NULL;
    		PtrQ->rear = TempCell;
    	}
    }

### 3.4 删除操作 ###

/* 从队列头部删除一个元素 */
    ElementType DeleteQ ( LinkQueue *PtrQ )
    { 
    	QNode *FrontCell;
    	ElementType FrontElem;
    	if ( IsEmptyQ(PtrQ) ) 
    	{
    		printf("The link queue is empty!\n"); 
    		return -1;
    	}
    	FrontCell = PtrQ->front;
    	if ( PtrQ->front == PtrQ->rear) 		/* 若队列只有一个元素 */
    		PtrQ->front = PtrQ->rear = NULL; 	/* 删除后队列置为空 */
    	else
    		PtrQ->front = PtrQ->front->Next;
    	FrontElem = FrontCell->Data;
    	free( FrontCell ); 			/* 释放被删除结点空间 */
    	return FrontElem;
    }

### 3.5 完整的示例代码实现 ###

/* 队列的链式存储实现 */
    #include <stdio.h>
    #include <stdlib.h>
    
    /* 定义链式队列的基本数据结构 */
    typedef int ElementType;
    typedef struct Node{
    	ElementType Data;
    	struct Node *Next;
    }QNode;
    typedef struct { 		/* 链队列结构 */
    	QNode *rear; 		/* 指向队尾结点 */
    	QNode *front; 		/* 指向队头结点 */
    } LinkQueue;
    
    /* 创建一个空队列 */
    LinkQueue *CreatQueue()
    {
    	LinkQueue *Q = (LinkQueue *)malloc(sizeof(LinkQueue));
    	if(NULL != Q)
    	{
    		Q->front = NULL;
    		Q->rear = NULL;
    	}
    	return Q;
    }
    
    /* 消除一个队列 */
    void DestroyQueue(LinkQueue *PtrQ)
    {
    	while(!IsEmptyQ(PtrQ))
    	{
    		DeleteQ(PtrQ);
    	}
    	free(PtrQ);
    	PtrQ = NULL;
    }
    
    /* 判断队列是否为空，1为空，0非空 */
    int IsEmptyQ( LinkQueue *PtrQ )
    {
    	return (PtrQ->front == NULL);
    }
    
    /* 向队列尾部插入一个元素 */
    void AddQ( LinkQueue *PtrQ, ElementType item)
    {
    	QNode *TempCell = NULL;
    
    	TempCell = (QNode*)malloc(sizeof(QNode));
    	if(NULL == TempCell)
    	{
    		printf("Malloc is failed!\n");
    		return;
    	}
    	TempCell->Data = item;	// 赋值给分配的结点
    	if ( IsEmptyQ(PtrQ) ) 	// 判断队列是否为空
    	{
    		PtrQ->rear = PtrQ->front= TempCell;
    		TempCell->Next = NULL;
    	}
    	else
    	{
    		PtrQ->rear->Next = TempCell;
    		TempCell->Next = NULL;
    		PtrQ->rear = TempCell;
    	}
    }
    
    
    /* 从队列头部删除一个元素 */
    ElementType DeleteQ ( LinkQueue *PtrQ )
    { 
    	QNode *FrontCell;
    	ElementType FrontElem;
    	if ( IsEmptyQ(PtrQ) ) 
    	{
    		printf("The link queue is empty!\n"); 
    		return -1;
    	}
    	FrontCell = PtrQ->front;
    	if ( PtrQ->front == PtrQ->rear) 		/* 若队列只有一个元素 */
    		PtrQ->front = PtrQ->rear = NULL; 	/* 删除后队列置为空 */
    	else
    		PtrQ->front = PtrQ->front->Next;
    	FrontElem = FrontCell->Data;
    	free( FrontCell ); 			/* 释放被删除结点空间 */
    	return FrontElem;
    }
    
    /* 遍历一个队列 */
    void TraversalQ( LinkQueue *PtrQ )
    {
    	QNode *FrontCell;
    	QNode *RearCell;
    	if(!IsEmptyQ(PtrQ))
    	{
    		FrontCell = PtrQ->front;
    		RearCell = PtrQ->rear;
    		while(FrontCell != RearCell)	// 把前面n-1个结点元素值打印出来
    		{
    			printf("%d ", FrontCell->Data);
    			FrontCell = FrontCell->Next;
    		}
    		printf("%d ", RearCell->Data);	// 把最后一个结点元素值打印出来
    		printf("\n");
    	}
    }
    
    /* 程序入口 */
    int main()
    {
    	int i;
    	ElementType temp;
    	LinkQueue *queue = NULL;
    
    	/* 创建一个循环队列 */
    	queue = CreatQueue();
    	if(NULL == queue)
    	{
    		printf("CreatQueue is failed!\n");
    		return -1;
    	}
    
    	/* 向循环队列中插入五个元素 */
    	printf("Input 5 numbers : ");
    	for(i = 0; i < 5; i++)
    	{
    		scanf("%d", &temp);
    		AddQ(queue, temp);
    	}
    
    	printf("****************************************TraversalQ*******************************\n");
    	TraversalQ(queue);
    
    	printf("****************************************AddQ once********************************\n");
    	printf("Input 1 number : ");
    	scanf("%d", &temp);
    	AddQ(queue, temp);
    	TraversalQ(queue);
    
    	printf("****************************************DeleteQ twice****************************\n");
    	DeleteQ(queue);
    	DeleteQ(queue);
    	TraversalQ(queue);
    
    	DestroyQueue(queue);	// 销毁一个队列
    
    	return 0;
    }