007-队列
1、基本概念队列（queue）是一种 特殊的线性表；
队列仅在线性表的两端进行操作；
队头（Front）：取出数据元素的一端；
队尾（Rear）: 插入数据元素的一端。
队列不允许在中间位置插入元素或其他操作。
队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。是一种先进先出的线性表（FIFO）.
常用操作：
创建队列；
销毁队列；
清空队列；
进队列；
出队列；
获取队头元素；
获取队列的长度。
2、队列的线性存储
同样由于队列是一种特殊的线性表，其实现也是可以通过线性表来完成的。
通过线性表的顺序存储来实现队列的顺序 存储。
// 创建一个队列相当于 创建一个线性表
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_Append(SeqQueue* queue, void* item)
{
return SeqList_Insert(queue, item, SeqQueue_Length(queue));
}
// 出队 相当于 删除链表头部元素
void* SeqQueue_Retrieve(SeqQueue* queue)
{
return SeqList_Delete(queue, 0);
}
// 获取队列头部元素 相当于 获取线性表头部元素
void* SeqQueue_Header(SeqQueue* queue)
{
return SeqList_Get(queue, 0);
}
// 获取队列长度相当于 获取线性表长度
int SeqQueue_Length(SeqQueue* queue)
{
return SeqList_Length(queue);
}
// 获取队列容量相当于 获取线性表容量
int SeqQueue_Capacity(SeqQueue* queue)
{
return SeqList_Capacity(queue);
}
3、队列的链式存储
和栈类似，队列的链式存储同样涉及到① 队列的业务结点向线性表业务结点的转换 ② 结点的生命周期的管理。
// 队列也是一种特殊的线性表
// 队列的业务结点的数据结构
typedef struct _tag_LinkQueueNode
{
LinkListNode node;
void* item;
}TLinkQueueNode;
// 创建一个队列相当于 创建一个线性表
LinkQueue* LinkQueue_Create()
{
return LinkList_Create();
}
// 销毁一个队列相当于 销毁一个线性表
// 结点的内存管理
void LinkQueue_Destroy(LinkQueue* queue)
{
LinkQueue_Clear(queue);
LinkList_Destroy(queue);
}
// 清空一个队列需要把队列里的每个元素取出来释放掉
void LinkQueue_Clear(LinkQueue* queue)
{
while (LinkQueue_Length(queue) > 0)
{
LinkQueue_Retrieve(queue);
}
LinkList_Clear(queue);
}
// 入队相当于 向线性表添加一个元素
// 头插、尾插都可以，这里选择尾插法
int LinkQueue_Append(LinkQueue* queue, void* item)
{
int ret = 0;
TLinkQueueNode *tmp = NULL;
tmp = (TLinkQueueNode*)malloc(sizeof(TLinkQueueNode));
if (tmp == NULL)
{
ret = -1;
printf("Fun LinkQueue_Append() malloc error:%d", ret);
return ret;
}
memset(tmp, 0, sizeof(TLinkQueueNode));
tmp->item = item;
// 需要把队列的业务结点 转换为 线性表的业务结点
ret = LinkList_Insert(queue, (LinkListNode*)tmp, LinkList_Length(queue));
if (ret != 0)
{
printf("Fun LinkList_Insert() error: %d\n", ret);
if (tmp != NULL)
{
free(tmp);
tmp = NULL;
}
}
return ret;
}
// 从队列中删除一个元素 相当于从线性表中删除一个元素
void* LinkQueue_Retrieve(LinkQueue* queue)
{
TLinkQueueNode *tmp = NULL;
void *ret = NULL;
tmp = (TLinkQueueNode*)LinkList_Delete(queue, 0);
if (tmp == NULL)
{
printf("Fun LinkList_Delete error\n");
return NULL;
}
ret = tmp->item;
if (tmp != NULL)
{
free(tmp);
}
return ret;
}
// 获取队列中头部元素 相当于获取线性表的头部元素
void* LinkQueue_Header(LinkQueue* queue)
{
TLinkQueueNode *tmp = NULL;
void *ret = NULL;
tmp = LinkList_Get(queue, 0);
if (tmp == NULL)
{
printf("func LinkList_Get() reeor\n");
return NULL;
}
return tmp->item;
}
// 求队列的长度 相当于 求线性表的长度
int LinkQueue_Length(LinkQueue* queue)
{
return LinkList_Length(queue);
}
完整代码：
页:
[1]