引子：只有学习才是激情的生命，才是燃烧的岁月，才是完美的人生
声明：本笔记由《嵌入式系统软件设计中的数据结构》产生，旨在提升自己的软件设计水平，绝无侵权行为，望转载者备注说明
一 队列逻辑结构
1 是一种只允许在表的一端-“队尾“进行插入，而在另一端-”队头“进行删除的线性表。实则为线性表的一种特例。也称为先进先出表
2 当队列中没有结点时称为空队列。队列的修改是依照先进先出的原则进行的
二 队列的基本运算
置空队 SetNull(Q)：将队列 Q 置成空的队列
判队空 Empty(Q)：若 Q 为空队列，返回”真“，否则为”假“
取头结点 GetFront(Q)：读取队列 Q 的头结点的值，队列中的结点保持不变
入队 InQuery(Q, x)：将结点 x 插入到队列 Q 的队尾
出队 DeQuery(Q)：删除队列头结点
三 队列分类
1 顺序队列
采用顺序存储结构，实则为运算受限的顺序表，可用一维数组来存放结点数据
front 指示队列当前队头结点的数组下标的位置
rear 指示队列当前队尾结点的数组下标的位置
结构描述
+++++++++++++++++++++++++++++++++++++++++++++++
#define maxsize 1024
typedef int datatype;
typedef struct
{
datatype data[maxsize]; //存放数据元素的一维数组
int front; //头结点
int rear; //尾结点
}sequery;
++++++++++++++++++++++++++++++++++++++++++++++++
顺序队列的队头和队尾的标志位置分析
front指向当前队列头结点的前一个位置
rear指向当前队列尾结点的位置
队列的溢出情况分析
出队运算：front++；//头指针 +1
当空队时，front = rear，若再做出队操作，会产生“下溢”
入队运算：rear++；//尾指针 +1
data[rear] = x; //x 入队
当队满时，再做入队操作会产生“上溢”
假上溢 原因：被删除的结点（出队结点）的空间永远不能再使用
2 循环队列
将顺序队列首尾相连，即 data[0] 接在 data[max - 1] 之后
循环队列克服假上溢：
若当前尾指针等于数组的上界（max - 1），再做入队操作时，令尾指针等于数组的下界（0）
入队：rear = (rear + 1) % max;
data[rear] = x;
出队：front = (front + 1) % max;
循环队列队空队满情况：
少用一个结点空间，即头结点指向的空间不使用
队空：front = rear
队满：(rear + 1) % max = front;
循环队列的运算
+++++++++++++++++++++++++++++++++++++++++++++++++++++
/* 置空队 */
void SetNull(sequeue * sq)
{
sq->front = 0;
sq->rear = 0;
}
/* 判队空 */
int Empty(sequeue * sq)
{
if (sq->rear == sq->front)
return 1;
else
return 0;
}
/* 取头结点 */
datatype GetFront(sequeue *sq)
{
if (Empty(sq))
{
printf("queue is null");
return(NULL);
/**
* For GCC Warning
*/
}
else
return(sq->data[(sq->front+1)%max]);
}
/* 入队 */
int InQueue(sequeue * sq, datatype x)
{
if ((rear + 1)%max == sq->front)
{
printf("queue is full");
return(NULL);
}
else
{
sq->rear = (sq->rear+1)%max;
sq->data[sq->rear] = x;
return 1;
}
}
/* 出队 */
datatype DeQueue(sequeue * sq)
{
if (Empty(sq))
{
printf("queue is full");
return(NULL);
}
else
{
sq->front = (sq->front+1)%max;
return(sq->data[sq->front]);
}
}
+++++++++++++++++++++++++++++++++++++++++++++++++++++
3 链队列
采用链式存储的队列，类似单链表，但其操作受限，只允许在表头删除节点和在表为插入节点
未完待续