队列(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;
}