---

队列

1.概念

和栈相反，队列(queue)是一种先进先出的线性表，它只允许在一端进行插入，而在另一端被删除。这和生活中的排队是类似的，最先排队的最先离开。在队列中运行被插入的一端叫做队尾，允许被删除的一端叫做队尾。

2. 生活中队列应用

比如我们去银行办理业务的时候需要去抽号机器上取一个号码，这起始就是队列的应用。每当有一个人取号后机器就会把这个号码入队列进行排队。等窗口工作人员进行叫号办理业务。

3. 队列的实现

队列可以用数组或者链表实现，使用链表实现会更加合适一些，因为如果使用数组实现在出队的时候效率会比较低。

队列的定义

因为是链表实现所以还要定义一个节点结构体，队列的结构题包含两个指针一个队头指针和一个队尾指针

typedef int QDataType;typedef struct QListNode {QDataType data;struct QListNode* next;//下一个节点
}QNode;typedef struct Queue
{QNode* front;//队头QNode* rear;//队尾
}Queue;// 初始化队列
void QueueInit(Queue* q);
// 动态申请节点
QNode* BuyQNode(QDataType data);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

初始化队列

初始化队列比较简单，让队头和队尾指向NULL，因为此时队列里没有任何元素。

// 初始化队列
void QueueInit(Queue* q)
{assert(q);q->front = NULL;q->rear = NULL;
}

因为这是链表实现所以还要定义个动态申请节点的函数

// 动态申请节点
QNode* BuyQNode(QDataType data)
{QNode* node = (QNode*)(malloc(sizeof(QNode)));if (node == NULL){printf("申请失败\n");exit(-1);}node->data = data;node->next = NULL;return node;
}

入队列

入队列需要考虑两种情况，第一种是队列为空的情况，队列为空要把队头和队尾指针都指向第一个元素，其他情况只需要把节点插入到队尾指针后面，再让对队尾指针往后走即可。

// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* node = BuyQNode(data);if (q->front == NULL){q->front = node;q->rear = node;}else{q->rear->next = node;q->rear = q->rear->next;}
}

出队列

出队列要考虑到队列是否为空，为空是不能进行出队列操作的。出队列只需要让队头指针往后走，再释放队头节点。

// 队头出队列
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));QNode* cur = q->front;q->front = q->front->next;free(cur);
}

获取队头元素

// 获取队列头部元素
QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->front->data;
}

获取队尾元素

// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->rear->data;
}

获取队列中元素个数

和链表求长度是一样的

// 获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);QNode* cur = q->front;int count = 0;while (cur != NULL){count++;cur = cur->next;}return count;
}

判断队列是否为空

当队头指向NULL时说明队列为空

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{assert(q);return q->front == NULL;
}

销毁队列

销毁队列遍历一边队列，把每个节点给释放掉。

// 销毁队列
void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->front;while (cur != NULL){q->front = cur->next;free(cur);cur = q->front;}q->front = NULL;q->rear = NULL;
}

2. 循环队列

循环队列也是一种队列，再队列的顺序存储结构中，除了用一组连续的存储单元依次存放队头到队尾元素外，还需要两指针 front 和 rear 分别指向队头和队尾。

我们约定，初始化空队列时，让 front 和 rear 都赋为0，也就是指向数组的0下标。每当插入元素时尾指针加1，每当删除元素时头指针加1。

因为这时一个循环队列，当 $front==rear$时，无法判断循环是满还是空。所以可以有两种选择，一种是做一个标记判断是否为满了，而是创建队列的时候多开一个空间，浪费掉这个空间方便判断。

我们采用第二种方式，约定$fron==rear$表示队列为空，$rear+1==fron$表示队列满了。

还有一个问题就是这是一个循环队列，当尾指针走到最后一个位置时如何走到下标为0的位置，我们可以巧妙的用一个公式，假设队列大小为 size。

头指针向后走：$(fron+1)\%size$

尾指针向后走：$(rear+1)\%size$

代码实现

typedef struct {int* arr;int front;int rear;int size;//容量
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* QUeue(int k) {MyCircularQueue* obj = (MyCircularQueue*)(malloc(sizeof(MyCircularQueue)));//创建容量为k+1大小的队列，浪费1个空间obj->arr = (int*)(malloc(sizeof(int)*(k+1)));obj->front = 0;obj->rear = 0;obj->size = k+1;return obj;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj) == true){return false;//满了}else{obj->arr[obj->rear] = value;obj->rear = (obj->rear+1) % (obj->size);return true;}}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false;}else{obj->front = (obj->front+1) % (obj->size);return true;}
}int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj) == true){return -1;}return obj->arr[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return (obj->rear == 0) ? (obj->arr[obj->size-1]) : (obj->arr[obj->rear-1]);
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//约定 头位相遇就是空，尾+1是头就是满if (obj->front == obj->rear){return true;}return false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {//约定 头位相遇就是空，尾+1是头就是满if (((obj->rear)+1)%obj->size == (obj->front)){return true;}return false;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);obj->front = NULL;obj->rear = NULL;free(obj);
}

---