队列结构
概念:
队列(queue):和栈相似,也是一种特殊的线性表。和栈不同的是,队列只允许在表的一端进行插入操作,而在另一端进行删除操作。一般来说,进行插入操作的一端称为队尾,进行删除操作的一端称为队头。队列中没有元素时成为空队列。
队列结构采取“先进先出”的原则处理结点数据。
分类:
以存储结构划分,分为两类:
顺序队列结构
使用一组地址连续的内存单元依次保存在队列中的数据。在程序中,可以定义一个指定大小的结构数组来作为队列。
链式队列结构
使用链表形式保存队列中各元素的值
队列的基本操作:
-
入队列:将一个元素添加到队尾(相当于到队列最后等候)
-
出队列:将队头的元素取出,同时删除该元素,使后一个元素成为队头。
队列的程序设计
准备数据:
准备在队列操作中要用到的变量以及数据结构
#define QUEUELEN 15
typedef struct
{
char name[10];
int age;
}DATA;
typedef struct
{
DATA data[QUEUELEN]; //队列数组
int head;
int tail;
}SQType;
这里定义了队列结构的最大长度QUEUELEN,队列结构数据元素的类型DATA以及队列结构的数据结构 SQType 。在数据结构 SQType 中,data 为数据元素,head 为队头的序号,tail 为队尾的序号。当 head=0 时表示队列为空,当 tail=QUEUELEN 时表示队列为满。
初始化队列结构:
创建一个空的顺序队列。步骤如下:
-
按符号常量 QUEUELEN 指定的大小申请一块内存空间,用来保存队列中的数据。
-
设置head=0 和 tail=0,表示是一个空栈。
初始化顺序队列的示例代码如下:
SQType* SRTpyeInit()
{
SQType* q;
if (q = (SQType*)malloc(sizeof(SQType))) //申请内存
{
q->head = 0; //设置队头
q->tail = 0; //设置队尾
return q;
}
else
{
return NULL; //返回空
}
}
这里采用 malloc() 申请内存,申请成功后设置队头和队尾,返回申请内存的首地址。如果申请内存失败,将返回NULL。
判断队列:
判断空队列
int SQTypeIsEmpty(SQType* q)
{
int temp;
temp = q->head == q->tail;
return temp;
}
在这里,输入一个参数 q 为一个指向操作的队列的指针。程序中,根据队列 head 是否等于 tail ,判断队列是否为空。
判断满队列
int SQTypeIsFull(SQType* q)
{
int temp;
temp = q->tail == QUEUELEN;
return temp;
}
在这里,输入一个参数 q 为一个指向操作的队列的指针。程序中,根据队列 tail 是否等于符号常量QUEUELEN ,判断队列是否为满。
清空队列:
void SQTypeClear(SQType* q)
{
q->head = 0; //设置队头
q->tail = 0; //设置队尾
}
在这里,输入一个参数 q 为一个指向操作的队列的指针。程序中,将队列顶指针 head和 tail 设置为 0,表示执行清空队列操作。
释放空间:
释放队列结构所占用的内存单元。由前面可知,在初始化队列结构时,使用了malloc()函数分配内存空间。虽然可以使用清空队列的操作,但是清空队列操作并没有释放内存空间,所以需要用free()释放所分配的内存。
void SQTypeFree(SQType* q)
{
if (q != NULL)
free(q);
}
在这里,输入一个参数 q 为一个指向操作的队列的指针。程序中,直接调用free()释放所分配的内存。多用于程序结束时。
出入队列:
入队列
将数据元素保存到队列结构。具体步骤如下:
-
首先判断队列顶 tail,如果 tail 等于QUEUELEN,则表示溢出,进行出错处理。
-
设置 tail=tail+1 (队列顶指针+1,指向入队列地址)
-
将队列元素保存到 tail 指向的位置。
代码示例:
int InSQType(SQType* q,DATA data)
{
if (q->tail == QUEUELEN)
{
printf("队列已满操作失败!n");
}
else
{
q->data[q->tail++] = data; //将元素入队列
return 1;
}
}
出队列
从队列顶弹出一个数据元素。具体步骤如下:
-
判断队列 head,如果 head 等于 tail,则表示为空指针,进行出错处理。
-
从队列首部取出队头元素(返回队头元素的指针)
-
设修改队头 head 的序号,使其指向后一个元素。
代码示例:
DATA* OutSQType(SQType* q)
{
if (q->tail == q->tail)
{
printf("队列已空,操作失败!n");
exit(0);
}
else
{
return &(q->data[q->head++]);
}
}
读取结点数据
与出队列不同,读结点的操作只是显示内容,而出队列会使该数据不再存在。
代码示例:
DATA* OutSQType(SQType* q)
{
if (SQTypeIsEmpty(q))
{
printf("空队列!n");
return NULL;
}
else
{
return &(q->data[q->head]);
}
}
原文链接: https://www.cnblogs.com/liubaili/p/14850408.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/211148
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!