5.队列
在C语言中，队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构。它只允许在队列 的一端（队尾）进行插入操作（入队），在另一端（队头）进行删除操作（出队）
队列并不特指某种具体某种数据结构，而是一种思想，只要具备先进先出，后进后出的思想的数据结构 都可称作为队列
例如：医院排队挂号
入队：队伍新增一个挂号的人。（应当要排在队伍最后面）
出队：有一个挂完号离开队伍。（应当是队伍第一个人）
1.1 顺序队列
1.1.1 普通顺序队列
使用数组和两个索引，队头和队尾。 front （队头）和 数组的起始位置
-
当队列为空时，队头与队尾重叠。
-
当向栈中添加元素时，队尾索引会增加，并将新元素放置在队尾索引指向的位置。
-
当从栈中删除元素时，队头索引会减少，并移除队头索引指向的元素
数组+整型数据的结构体（类）
struct 队列名 { 数据类型 数组名[长度]; // 队列元素存放的空间 int front; // 队头元素的下标。 int rear; // 队尾元素的下标。 };注意：顺序队列在取元素的时候其实没有删除元素的，只是把下标移动了，在下一次增加元素就会覆盖 原来的元素
-
插入
- 删除
#include <iostream>
using namespace std;
#define MAXSIZE 100//顺序队列
typedef struct queue
{int buf[MAXSIZE];int head;int tail;
}queue; // 队列初始化函数
void initqueue(queue *q_queue)
{q_queue->head = 0;q_queue->tail= 0;//ail指针始终指向队列中下一个可以插入元素的位置，而不是队列的最后一个有效元素。}// 获取队列的梳子个数
int sizeQueue(const queue *q_queue)
{return q_queue->tail - q_queue->head ;// 取决初始化
}// 判断是空
bool queue_isEmpty( queue *q_queue)
{return q_queue->head ==q_queue->tail;
}// 判断是满
bool queue_isFull( queue *q_queue)
{return q_queue->tail >= MAXSIZE;
}// 队列插入
bool push_queue(queue *q_queue, int num)
{// 队列是满if(q_queue->tail >= MAXSIZE){cout << "已满" << endl;return false;}//队列插入尾下标后移q_queue->buf[q_queue->tail] = num;q_queue->tail++;return true;
}
// 队列删除（获取删除元素）
bool pop_queue(queue *q_queue, int *p_num)
{// 队列是空if(q_queue->head >= q_queue->tail){cout << "空的" << endl;return false;}// 获取数字*p_num = q_queue->buf[q_queue->head];//队列删除元素，头下标后移q_queue->head++;return true;
}// 获取队列元素不会删除
bool front_queue(queue *q_queue, int *p_num)
{// 队列是空if(q_queue->head >= q_queue->tail){cout << "空的" << endl;return false;}// 获取数字*p_num = q_queue->buf[q_queue->head];return true;
}
int main()
{queue q ={0};initqueue(&q);push_queue(&q, 1);push_queue(&q, 2);push_queue(&q, 3);int popNum = 0;if(pop_queue(&q, &popNum)){cout << "队列出队的元素" << popNum << endl;}int frontNum = 0;if(front_queue (&q, &frontNum)){cout << "队列队头的元素" << frontNum << endl;}return 0;
}遇到问题：在拆入元素函数里面如果这样写
q_queue->tail++;q_queue->buf[q_queue->tail] = num;
tail和head的处理方式会导致无法准确判断队列是空还是有一个元素。这是因为tail在插入元素时先自增，然后再赋值，这会导致tail指向的位置始终是尚未使用的，而head指向的是第一个有效元素。因此，当tail == head时，无法区分队列是空还是有一个元素。所以还是先复制在++，让队尾不指向有效元素，但是要注意遍历不能遍历到队尾，要到队尾-1，当然
q_queue->tail++;q_queue->buf[q_queue->tail] = num;
也可以，但是要放弃0号元素，因为它不指向有效元素，直接把它弹出就行
1.1.2 循环队列
循环队列是一种使用有限数组来模拟队列这种数据结构的方式，它有效地利用了数组的存储空间。在循 环队列中，当数组的尾部空间被用完时，新元素会从数组的头部开始插入，形成一个循环的效果。
循环队列判断元素数量比较麻烦，因此加入一个成员变量来记录元素数量。
格式：
struct 队列名
{
数据类型 数组名[长度]; // 队列元素存放的空间
int front; // 队头元素的下标。
int rear; // 队尾元素的下标。
int num;//元素数量
};
遍历队列（队尾不能遍历，队头-队尾-1）
#include <iostream>
using namespace std;
#define MAXSIZE 100//循环顺序队列
typedef struct queue
{int buf[MAXSIZE];//队列元素存放的空间int head;//队头int tail;//队尾int num;//元素数量
}queue; // 队列初始化函数
void initqueue(queue *q_queue)
{q_queue->head = 0;q_queue->tail = 0;//ail指针始终指向队列中下一个可以插入元素的位置，而不是队列的最后一个有效元素。q_queue->num = 0;
}// 获取队列的梳子个数
int sizeQueue(const queue *q_queue)
{return q_queue->num;
}// 判断是空
bool queue_isEmpty( queue *q_queue)
{return q_queue->num == 0;
}// 判断是满
bool queue_isFull( queue *q_queue)
{return q_queue->num >= MAXSIZE;
}// 队列插入
bool push_queue(queue *q_queue, int m_num)
{// 队列是满if( queue_isFull(q_queue)){cout << "已满" << endl;return false;}//队列插入尾下标后移q_queue->buf[q_queue->tail] = m_num;q_queue->tail++;if(q_queue->tail == MAXSIZE){q_queue->tail = 0;}q_queue->num++;return true;
}
// 队列删除（获取删除元素）
bool pop_queue(queue *q_queue, int *p_num)
{// 队列是空if(queue_isEmpty( q_queue)){cout << "空的" << endl;return false;}// 获取数字*p_num = q_queue->buf[q_queue->head];//队列删除元素，头下标后移q_queue->head++;// 满了就重新循环if(q_queue->head == MAXSIZE){q_queue->head = 0;}q_queue->num--;return true;
}// 获取队列元素不会删除
bool front_queue(queue *q_queue, int *p_num)
{// 队列是空if(queue_isEmpty( q_queue)){cout << "空的" << endl;return false;}// 获取数字*p_num = q_queue->buf[q_queue->head];return true;
}
int main()
{queue q ={0};initqueue(&q);push_queue(&q, 1);push_queue(&q, 2);push_queue(&q, 3);int popNum = 0;if(pop_queue(&q, &popNum)){cout << "队列出队的元素" << popNum << endl;}int frontNum = 0;if(front_queue (&q, &frontNum)){cout << "队列队头的元素" << frontNum << endl;}if(front_queue (&q, &frontNum)){cout << "队列队头的元素" << frontNum << endl;}return 0;
}这个就是加了一个统计元素的成员，因为循环队列判断元素数量，其实他的判断头和尾满的公司是
q_queue->tail = (q_queue->tail + 1) % MAXSIZ或者q_queue->head= (q_queue->head + 1) % MAXSIZ
不过有些冗余，就写成上面那样
遍历队列（队尾不能遍历，对头+长度遍历）
顺序队列不太好用
