队列(queue)的概念及常见应用

队列是一种先进先出的数据模型，它的应用场景比较常见，比如日常生活中我们打10086的电话需要排队时、吃饭排号时的小票、Windows GUI程序的消息队列等等都是基于队列实现的。先进入队列的也是先从队列出去的。他的模型如下：

【顺序线性表实现队列】

顺序线性表可以实现队列的模型，线性表中哪一端作为队头或者队尾都可以的。具体实现代码如下（需要用到线性表顺序存储的头文件 SeqList.h 和 SeqList.c）：

#ifndef _SEQQUEUE_H_
#define _SEQQUEUE_H_

typedef void SeqQueue;


//创建队列
SeqQueue* SeqQueue_Create(int capacity);

//销毁队列
void SeqQueue_Destroy(SeqQueue* queue);

//清空队列
void SeqQueue_Clear(SeqQueue* queue);

//进队列
int SeqQueue_Push(SeqQueue* queue, void* item);

//出队列
void* SeqQueue_Pop(SeqQueue* queue);

//获取队头元素
void* SeqQueue_Front(SeqQueue* queue);

//获取队列的长度
int SeqQueue_Size(SeqQueue* queue);

#endif //_SEQQUEUE_H_

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "SeqQueue.h"
#include "SeqList.h"

//用顺序线性表来实现

//创建队列
SeqQueue* SeqQueue_Create(int capacity)
{
	//创建一个线性表
	return SeqList_Create(capacity);
}

//销毁队列
void SeqQueue_Destroy(SeqQueue* queue)
{
	//销毁线性表
	SeqList_Destroy(queue);
}


//清空队列
void SeqQueue_Clear(SeqQueue* queue)
{
	//重置线性表
	SeqList_Clear(queue);
}


//进队列
int SeqQueue_Push(SeqQueue* queue, void* item)
{
	//数组的尾部作为队尾
	//在信息表尾部插入元素
	int ret = SeqList_Insert(queue, (SeqListNode*)item, SeqList_Length(queue));
	return ret;
}


//出队列
void* SeqQueue_Pop(SeqQueue* queue)
{
	//数组的头部作为队头
	//线性表的头部删除元素
	SeqListNode* pNode = SeqList_Delete(queue, 0);
	return pNode;
}


//获取队头元素
void* SeqQueue_Front(SeqQueue* queue)
{
	//获取线性表第一个元素
	SeqListNode* pNode = SeqList_Get(queue, 0);
	return pNode;
}


//获取队列的长度
int SeqQueue_Size(SeqQueue* queue)
{
	//线性表长度
	return SeqList_Length(queue);
}

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "SeqQueue.h"

//定义结构体
typedef struct tag_Value
{
	int v;
}Value;


int main()
{
	int i;
	Value val[10];
	SeqQueue* queue = NULL;
	//创建队列
	queue = SeqQueue_Create(20);
	//初始化结构体数组
	for (i = 0; i < sizeof(val) / sizeof(Value); i++)
	{
		val[i].v = i;
		//进队列
		SeqQueue_Push(queue, (void*)&val[i]);
	}

	//打印队列 的长度
	printf("Queue size = %d\n", SeqQueue_Size(queue));
	//打印对队头元素
	printf("Queue front element = %d\n", ((Value*)SeqQueue_Front(queue))->v);

	//所有元素出队列
	while (SeqQueue_Size(queue) > 0)
	{
		//打印对队头元素, 并弹出
		printf("POP -- Queue front element = %d\n", ((Value*)SeqQueue_Pop(queue))->v);
	}

	//销毁队列
	SeqQueue_Destroy(queue);

	printf("Good good study, day day up!!!\n");
	system("pause");
	return 0;
}

【链式线性表实现队列】

使用顺序线性表可以实现队列的模型，同样链式线性表也是可以的，使用链表来实现队列模型如下：

实现代码（需要用到链式线性表头文件 LinkList.h 和 LinkList.c ）：

#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_

typedef void LinkQueue;

//创建队列
LinkQueue* LinkQueue_Create();

//销毁队列
void LinkQueue_Destory(LinkQueue* queue);

//清空队列
void LinkQueue_Clear(LinkQueue* queue);

//进队列
int LinkQueue_Push(LinkQueue* queue, void* item);

//出队列
void* LinkQueue_Pop(LinkQueue* queue);

//获取队头元素
void* LinkQueue_Front(LinkQueue* queue);

//获取队列长度
int LinkQueue_Size(LinkQueue* queue);

#endif //_LINKQUEUE_H_

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkQueue.h"
#include "LinkList.h"

//定义一个队列节点结构体
typedef struct tag_listqueueNode
{
	//包含一个链表节点
	LinkListNode node;
	//存储数据
	void* data;
}ListQueueNode;


//创建队列 ==> 创建链表
LinkQueue* LinkQueue_Create()
{
	//创建一个链表
	return LinkList_Create();
}

//销毁队列
void LinkQueue_Destory(LinkQueue* queue)
{
	//释放掉所有分配的存储空间
	LinkQueue_Clear(queue);
	//销毁这个链表
	LinkList_Destory(queue);
}


//清空队列 ==> 清空链表
//因为动态分配了内存, 所有需要释放
void LinkQueue_Clear(LinkQueue* queue)
{
	//释放掉所有分配的存储空间
	while (LinkQueue_Size(queue) > 0)
	{
		LinkQueue_Pop(queue);
	}
	//清空链表
	LinkList_Clear(queue);
}


//进队列 ==> 在链表尾部添加元素
int LinkQueue_Push(LinkQueue* queue, void* item)
{
	//创建队列节点
	ListQueueNode* pNew = (ListQueueNode*)malloc(sizeof(ListQueueNode));
	if (pNew == NULL)
	{
		//创建节点失败,直接返回
		return -1;
	}
	//初始化
	pNew->data = item;
	pNew->node.next = NULL;

	//链表 的尾部作为队尾
	//在链表 的尾部插入元素
	int ret = LinkList_Insert(queue, (LinkListNode*)pNew, LinkList_Length(queue));
	if (ret != 0)
	{
		//释放内存
		free(pNew);
	}
	return ret;
}


//出队列 ==> 在链表头部删除元素
void* LinkQueue_Pop(LinkQueue* queue)
{
	//链表的头部作为队头
	//删除链表的第一个数据节点
	LinkListNode *pDel = LinkList_Delete(queue, 0);
	if (pDel == NULL)
	{
		return NULL;
	}
	void* data = ((ListQueueNode*)pDel)->data;
	//释放内存
	free(pDel);

	return data;
}


//获取队头元素 ==> 获取链表的第一个数据节点
void* LinkQueue_Front(LinkQueue* queue)
{
	//获取链表的第一个数据节点
	LinkListNode* pNode = LinkList_Get(queue, 0);
	return ((ListQueueNode*)pNode)->data;
}


//获取队列长度 ==> 获取链表的长度
int LinkQueue_Size(LinkQueue* queue)
{
	//链表长度
	return LinkList_Length(queue);
}

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkQueue.h"

int main()
{
	int i;
	int array[10] = { 0 };
	LinkQueue* queue = NULL;
	//创建队列
	queue = LinkQueue_Create();
	//数组赋值
	for (i = 0; i < sizeof(array) / sizeof(int); i++)
	{
		array[i] = i;
		//进队列
		LinkQueue_Push(queue, (void*)&array[i]);
	}

	//打印队列的长度
	printf("Queue size = %d\n", LinkQueue_Size(queue));
	//打印队头元素
	printf("Queue Front element = %d\n", *(int*)LinkQueue_Front(queue));

	//将所有元素出队列
	while (LinkQueue_Size(queue) > 0)
	{
		//打印队头元素, 并弹出
		printf("POP == Queue Front element = %d\n", *(int*)LinkQueue_Pop(queue));
	}
	//销毁队列
	LinkQueue_Destory(queue);

	printf("Good good study, day day up!!!\n");
	system("pause");
	return 0;
}