队列学习笔记–链队和顺序队
参考书籍–《数据结构 c语言版》严蔚敏
1.队列（循环队列）
在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个整型变最 front 和 rear分别指示队列头元素及队列尾元素的位置（后面分别称为头指针和尾指针）。
每当插入新的队列尾元素时，尾指针 rear增1; 每当删除队列头元素时， 头指针 front增1。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。
循环队列可充分利用空间，且减少了时间复杂度，通过移动frong和rear来实现。
如何判断队满与空：
少用一个元素空间， 即队列空间大小为m时，有m-1个元素就认为是队满。这样判断队空的条件即当头、 尾指针的值相同时，则认为队空；而当尾指针在循环意义上加1后是等于头指针， 则认为队满。
全部代码如下
//顺序队列常规操作
#include<stdio.h>
#include<stdlib.h>
#define MAXQSIZE 10 //队列可能达到的最大长度
typedef int QElemType; //元素类型是整型
typedef struct {
QElemType data[MAXQSIZE]; //定义一个数组来存放数据
int front; //头号
int rear; //尾号
} sqQueue;
sqQueue *QueueCreate() {
sqQueue *q = (sqQueue *)malloc(sizeof(sqQueue)); //分配空间，取基地址
q->front = q->rear = 0;
printf("初始化完成！\n");
return q;
}
//求队列长度（循环队列）
void QueueLength(sqQueue *q) {
printf("队列长度：%d\n",(q->rear-q->front+MAXQSIZE) % MAXQSIZE); //尾号可能比头号大，所以要注意长度的求法
}
//入队
void EnterQueue(sqQueue *q, QElemType a) {
if ((q->rear + 1) % MAXQSIZE == q->front) {
printf("队满！\n");
}
else {
q->data[q->rear] = a;
q->rear = (q->rear + 1) % MAXQSIZE;
}
}
//出队
void ExitQueue(sqQueue *q) {
if (q->front == q->rear) {
printf("队空！");
}
else {
printf("出队元素：%d\n", q->data[q->front]);
q -> front = (q->front + 1) % MAXQSIZE;
}
}
//打印队列
void PrintQueue(sqQueue *q) {
int t = q->front;
while (q->front != q->rear) {
printf("%d ", q->data[t]);
++t;
t %= MAXQSIZE;
if (t == q->rear) {
printf("\n");
break;
}
}
}
int main() {
sqQueue *q;
int le;
q = QueueCreate(); //初始化
for (int i = 1; i < 6; ++i) {
EnterQueue(q, i); //1-5依次入队
}
PrintQueue(q); //打印显示一下
ExitQueue(q); //出对，删除队首元素
QueueLength(q); //输出队列长度
ExitQueue(q);
QueueLength(q);
PrintQueue(q);
EnterQueue(q, 10);
EnterQueue(q, 20); //再入队两个元素 10， 20
PrintQueue(q); //输出看看
return 0;
}
2.链队
一个链队显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。
链队的操作即为单链表插入和删除操作的特殊情况，只是需进一步修改尾指针或头指针。链队只在链表头处插入，在链表尾部删除。
在链队出队操作时还要考虑当队列中最后一个元素被删后，队列尾指针也丢
失了，因此需对队尾指针重新赋值（指向头结点）。
队列的链式存储结构：
这与单链表有些不同，多了头指针和尾指针，而单链表只有头结点或头指针
typedef int QElemType;
typedef struct QueueNode {
QElemType data; //数据类型
struct QueueNode *next; //下一节点
} Queuenode, *QueuePtr;
typedef struct {
QueuePtr front; //头指针
QueuePtr rear; //尾指针
} LinkQueue;
全部代码如下：
//链栈队列常规操作
#include<stdio.h>
#include<stdlib.h>
#define N 10
typedef int QElemType;
typedef struct QueueNode {
QElemType data; //数据类型
struct QueueNode *next; //下一节点
} Queuenode, *QueuePtr;
typedef struct {
QueuePtr front; //头指针
QueuePtr rear; //尾指针
} LinkQueue;
//初始化创建一个头结点的队列
LinkQueue CreateQueuelist(LinkQueue Q) {
QueuePtr L = (QueuePtr)malloc(sizeof(Queuenode)); //创建头结点
Q.front = Q.rear = L; // 队头和队尾指针指向此结点
Q.front->next = NULL; //头结点指针域置空
return Q;
}
/* //入队
Queuenode *EntQueuelist(LinkQueue Q, QElemType a) {
QueuePtr temp = (QueuePtr)malloc(sizeof(Queuenode)); //为入队元素分配结点空间，用指针temp指向
temp->data = a; //将新结点数据域置为e
temp->next = NULL; //指针域置空
Q.rear->next = temp; //将新结点插入到队尾
Q.rear = temp; //修改队尾指针为remp
return Q.rear; //此处得返回Q.next，否则链表始终只有最新入队的一个元素
} */ //因为Q.rear是一个局部指针变量，返回之后就回到初始化的值了，以至于每次入队都只是入队新的元素，而以前的就没了
//也可以采取下面这种，把Q返回去，道理同上面
LinkQueue EntQueuelist(LinkQueue Q, QElemType a) {
QueuePtr temp = (QueuePtr)malloc(sizeof(Queuenode)); //为入队元素分配结点空间，用指针temp指向
temp->data = a; //将新结点数据域置为e
temp->next = NULL; //指针域置空
Q.rear->next = temp; //将新结点插入到队尾
Q.rear = temp; //修改队尾指针为remp
return Q;
}
//出队
void ExtQueuelist(LinkQueue Q) {
if (Q.front == Q.rear) { //判断队列是否为空
printf("空队列！\n");
}
else {
QueuePtr temp;
temp = Q.front->next; //临时保存队头元素的空间，以备释放。
Q.front->next = temp->next;
printf("出队元素：%d\n", temp->data);
if (Q.rear == temp) { //判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值， 指向头结点。
Q.rear = Q.front;
}
free(temp); //释放放原队头元素的空间
}
}
//打印队列
void PrintQueue(LinkQueue Q) {
QueuePtr h;
h = Q.front->next;
if (h == NULL) {
printf("空链表\n");
}
while (h) {
printf("%d ", h->data);
h = h->next;
}
printf("\n");
}
int main() {
LinkQueue Q;
Q = CreateQueuelist(Q);
for (int i = 0; i < 6; ++i) { //循环利用入队赋值
// Q.rear = EntQueuelist(Q, i+1);
Q = EntQueuelist(Q, i+1);
}
PrintQueue(Q); //打印此时链表的元素
ExtQueuelist(Q); //出队队首元素，也即链表首元元素
Q = EntQueuelist(Q, 100);
// Q.rear = EntQueuelist(Q, 100);
ExtQueuelist(Q);
PrintQueue(Q);
return 0;
}