⚡️数据结构-第一章
⚡️抽象数据类型案例
⚡️数据结构-第二章（1）-线性结构
⚡️数据结构-第二章（2）-线性表的顺序表示和实现
⚡️数据结构-第二章（3）-顺序表（含代码）
⚡️数据结构-第二章（4）-顺序表案例（含代码）
⚡️数据结构-第二章（5）-链式存储结构
⚡️数据结构-第二章（6）-单链表基本操作的实现
⚡️数据结构-第二章（7）-双向链表和循环链表
⚡️数据结构-第二章（8）-线性表的应用（线性表合并）
数据结构队列
队列的抽象数据类型定义顺序循环队列
假溢出问题 循环队列的初始化循环队列-求队列长度入队出队取队头元素 总结
队列和栈相反队列（queue）是一种先进先出（first in first out，缩写为 FIFO）的线性表。只允许在表的一端进行插入，而在另一端删除元素。
队列也有两种存储表示，顺序表示和链式表示。 常用的就是循环顺序队列。
双端队列
队列的抽象数据类型定义 顺序循环队列#define MAXQSIZE 100 //队列可能达到的最大长度
typedef struct
{
QElemType *base; //存储空间的基地址
int front; //头指针
int rear; //尾指针
}SqQueue;
为了在 c 语言中描述方便起见，在此约定：初始化创建空队列时，令front=rear=0，每当插入新队列尾元素时，尾指针rear加1；每当删除队列头元素时，头指针front加1.因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。
怎样解决这种“假溢出”问题呢？一个巧妙的办法是将顺序队列变为一个环状的空间，称之为循环队列。
头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针“依环加1”的操作可用“模”运算来实现。通过取模，头指针和尾指针就可以在顺序表空间以头尾衔接的方式“循环”移动。
对于循环队列不能以头尾指针的值是否相同来判别队列空间是“满”还是“空”。通常有以下两种处理方法：
① 少用一个元素空间，即队列空间大小为m时，有m-1个元素就认为是队满。这样判断队空的条件不变，即，当头尾指针的值相同时，则认为队空；而当尾指针在循环意义上加1后是等于头指针，则认为队满。因此，在循环队列中队空和队满的条件是：
队空的条件：
Q
.
f
r
o
n
t
=
=
Q
.
r
e
a
r
Q.front == Q.rear
Q.front==Q.rear
队满的条件：
(
Q
.
r
e
a
r
+
1
)
(Q.rear + 1)%MAXQSIZE = Q.front
(Q.rear+1)
② 另设一个标志位以区别队列是“空”还是“满”。
③ 另设一个变量计数
【算法步骤】
① 为队列分配一个最大容量为MAXQSIZE的数组空间，base指向数组空间的首地址。
② 头指针和尾指针置为零，表示队列为空。
【算法描述】
Status InitQueue(SqQueue &Q)
{//构造一个空队列Q
Q.base = new QElemType【MAXQSIZE】; //为队列分配一个空间
//Q.base = (QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
if(!Q.base) exit(OVERFLOW);//存储空间分配失败
Q.front=Q.rear=0;//头指针和尾指针置为零，队列为空
return OK;
}
循环队列-求队列长度
对于非循环队列，尾指针和头指针的差值便是队列长度，而对于循环队列，差值可能为负数，所以需要将差值加上 M A X Q S I Z E MAXQSIZE MAXQSIZE，然后与 M A X Q S I Z E MAXQSIZE MAXQSIZE求余。
【算法描述】
int QueueLength(SqQueue Q)
{
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
入队
【算法步骤】
① 判断队列是否满，若满则返回ERROR。
② 将新元素插入队尾。
③ 队尾指针加1。
【算法描述】
Status EnQueue(SqQueue &q, QElemType e)
{
if((q.rear+1)%MAXQSIZE==Q.front)
return ERROR;//队满情况
q.base【q.rear】 = e;//新元素插入队尾
q.rear=(q.rear+1)%MAXQSIZE;//队尾指针加1
return OK;
}
出队
【算法步骤】
① 判断队列是否为空，若空则返回ERROR
② 保存队头元素
③ 队头指针加1
【算法描述】
Status DeQueue(SqQueue &Q, QElemType &e)
{
if(Q.front == Q.rear) return ERROR;//队空
e=Q.base【front】;//返回队头元素的值
Q.front=【Q.front+1】%MAXQSIZE; //头指针加1
return OK;
}
取队头元素
QElemType GetHead(SqQueue q)
{
if(Q.front != Q.rear)//队列非空
return Q.base【Q.front】;//返回队头元素的值，队头指针不变
}
总结
期待大家和我交流，留言或者私信，一起学习，一起进步！
