目录

• 一.队列
• • 1.队列的概念及结构
  • 2.队列的实现
  • • Queue.h
    • Queue.c
• 二.循环队列
• • 1.循环队列的实现
  • 2.设计循环队列
  • • 解题思路
    • 代码

一.队列

1.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（First in first out）的特性
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

2.队列的实现

队列也可以用数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，在数组头部出队列，效率会很低。

• 如果队列使用顺序表的结构实现，进行出队操作时，有两种方法，1是将对头指针指向下一个位置，这会造成空间上的浪费。
  2是将对头后的所有数据向前移动一个位置，出队操作的时间复杂度就会变大，所以使用顺序表实现队列是不可取的。
• 因为队列要对对头和队尾进行操作，所以我们需要使用两个结构体指针，分别指向队头和队尾。

Queue.h

存放队列的所有函数的声明

#pragma once
#include
#includetypedef int QDataType;typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* front;QNode* tail;int size;
}Queue;void QueueInit(Queue* q);//初始化队列void QueuePush(Queue* q, QDataType x);//队尾入队列void QueuePop(Queue* q);//对头出队列QDataType QueueFront(Queue* q);//获取队列头部元素QDataType QueueTail(Queue* q);//获取队队尾元素int QueueSize(Queue* q);//查看队列中有效元素的个数int QueueEmpty(Queue* q);//查看队列是否为空，若是非空返回非零结果，若是为空，返回0void QueueDestroy(Queue* q);//销毁队列void QueuePrint(Queue* p);//打印队列

Queue.c

存放所有函数的实现

1.初始化队列

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

将对头和队尾全部置为空，当进行入队操作时，在使这两个指针分别指向对应的空间。

2.队尾入队列

//队尾入队列
void QueuePush(Queue* q, QDataType x)
{assert(q);QNode* newNode = (QNode*)malloc(sizeof(QNode));if (!newNode){perror("malloc fail");exit(-1);}newNode->data = x;newNode->next = NULL;if (!q->front){q->front = q->tail = newNode;}else{q->tail->next = newNode;q->tail = newNode;}q->size++;
}

向内存申请一个存放数据的空间，并向其存放数据。
判断此时队列中是否有数据，如果没有，对头和队尾都指向申请的空间，如果有，将队尾指向的空间的next赋值为新申请的空间，在将队尾指向新申请的空间。
最后将队列的大小加1，完成入队操作

3.队头出队列

//对头出队列
void QueuePop(Queue* q)
{assert(q);//当队列中没有元素时assert(q->front);if (q->front == q->tail){q->front = q->tail = NULL;}else{QNode* newNode = q->front;q->front = q->front->next;free(newNode);}q->size--;
}

首先判断，队列是否为空，若为空，无法进行出队列操作。
其次判断队列是否只要一个数据，若对头和队尾只写同一个空间，即只有一个数据，此时将两个指针都置为空，完成出队列操作。
如果，队列不为空，且队列中有多个数据，则队头进行操作，将对头指向的下一个位置变为对头，将之前的位置释放(队列中的空间是向内存申请的，需要释放，否则会造成内存泄漏)，完成出队操作。

4.获取对头数据

//获取队列头部元素
QDataType QueueFront(Queue* q)
{assert(q);//查看队列是否为空assert(q->front);//查看队列头部是否为空return q->front->data;
}

当队列不为空时，返回对头指向的空间所存储的数据即可。

5.获取队尾数据

//获取队队尾元素
QDataType QueueTail(Queue* q)
{assert(q);assert(q->front);return q->tail->data;
}

若队列不为空，返回队尾指针指向的空间所存储的数据。

6.查看队列中有效元素的个数

//查看队列中有效元素的个数
int QueueSize(Queue* q)
{assert(q);assert(q->front);//QNode* cur = q->front;//int size = 0;//while (cur)//{//	size++;//	cur = cur->next;//}//return size;return q->size;
}

有两种方法，
方法1：我们在设置队列的结构体时，定义了队列的长度size，此时返回size的大小即可。
方法2：若没有定义，则需要我们遍历队列，判断队列的长度
在实际应用队列时，我们不知道队列的结构体是如何设置的，我们只能通过这个函数来获取队列的有效元素的个数。

7.查看队列是否为空

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

8.销毁队列

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

队列中的空间都是向内存申请的，需要自己主动去释放，将队头的地址赋给一个临时的指针，由该指针去释放，当该指针为空时，表示已释放完毕。
最后我们将对头和队尾置空，将队列的大小改为0即可。

9.Queue.c完整代码

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"//初始化队列
void QueueInit(Queue* q)
{q->front = NULL;q->tail = NULL;q->size = 0;
}//队尾入队列
void QueuePush(Queue* q, QDataType x)
{assert(q);QNode* newNode = (QNode*)malloc(sizeof(QNode));if (!newNode){perror("malloc fail");exit(-1);}newNode->data = x;newNode->next = NULL;if (!q->front){q->front = q->tail = newNode;}else{q->tail->next = newNode;q->tail = newNode;}q->size++;
}//对头出队列
void QueuePop(Queue* q)
{assert(q);//当队列中没有元素时assert(q->front);if (q->front == q->tail){q->front = q->tail = NULL;}else{QNode* newNode = q->front;q->front = q->front->next;free(newNode);}q->size--;
}//获取队列头部元素
QDataType QueueFront(Queue* q)
{assert(q);//查看队列是否为空assert(q->front);//查看队列头部是否为空return q->front->data;
}//获取队队尾元素
QDataType QueueTail(Queue* q)
{assert(q);assert(q->front);return q->tail->data;
}//查看队列中有效元素的个数
int QueueSize(Queue* q)
{assert(q);assert(q->front);//QNode* cur = q->front;//int size = 0;//while (cur)//{//	size++;//	cur = cur->next;//}//return size;return q->size;
}//查看队列是否为空，若是非空返回非零结果，若是为空，返回0
int QueueEmpty(Queue* q)
{assert(q);return q->front == NULL && q->tail == NULL;
}//销毁队列
void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->front;while (cur){QNode* temp = cur;cur = cur->next;free(temp);}q->front = q->tail = NULL;q->size = 0;
}//打印队列
void QueuePrint(Queue* p)
{assert(p);QNode* cur = p->front;while (cur){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

二.循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模式时可以使用循环队列。
循环队列可以使用数组实现，也可以使用循环链表实现。
这里我们使用数组实现，因为一般循环队列的长度是固定的，数组可以很好的契合这一标准。

1.循环队列的实现

环形队列可以用数组实现，也可以用循环链表实现。
根据不同的情况，我们选择不同的实现方法：
当给定的循环链表的大小是固定时，使用数组更为简单，可以少掉链表的插入和删除，直接根据下标解决问题。
当给定的循环链表的大小不是固定时，可以试着使用循环链表，也可以少掉很多麻烦。

• 这里我们根据Leetcode上的一道循环链表题来讲解这个知识点。

2.设计循环队列

设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

• MyCircularQueue(k): 构造器，设置队列长度为 k 。
• Front: 从队首获取元素。如果队列为空，返回 -1 。
• Rear: 获取队尾元素。如果队列为空，返回 -1 。
• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
• isEmpty(): 检查循环队列是否为空。
• isFull(): 检查循环队列是否已满。

解题思路

该题中，循环队列给定了固定的大小，我们就可以使用顺序表实现它。
首先给出的数组大小为7个整形：

当队列为空时，我们将对头和队尾都指向下标为0的位置，
当插入元素时，我们将对头和队尾移动到下标为1~7的位置

这题的难点就是对队列入队和出队的操作，解决这两个问题，其他的在这两个的基础上也就迎刃而解。
这时我们就要分情况讨论了，

• 当队列已满时，有这几种情况
  
  所以当我们判断队列是否已满，或进行入队操作时，可以根据这两种情况判断
• 当进行出队操作时，又有这两种特殊种情况
  
  情况1：出队后队尾的位置加1等于对头的位置，表明此时队列为空，将对头和队尾置为0，表示此时队列为空
  情况2：出队后对头的位置大于所给出队列的大小，需将队头位置改为1
  其他出队情况直接将对头位置加1即可
  

代码

typedef struct {int* arr;int head;int rear;int size;
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(!obj){perror("malloc fail!");exit(-1);}obj->arr = (int*)malloc(sizeof(int)*(k+1));obj->head = obj->rear = 0;obj->size = k;return obj;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {assert(obj);if(obj->head == 0){obj->arr[++obj->head] = value;obj->rear++;return true;}else if(obj->rear < obj->size && (obj->rear+1 < obj->head || obj->rear >= obj->head)){obj->arr[++obj->rear] = value;return true;}else if(obj->rear == obj->size && obj->head > 1){obj->arr[1] = value;obj->rear = 1;return true;}return false;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {assert(obj);if(obj->head){obj->head++;if(obj->head == obj->rear+1)obj->head = obj->rear = 0;else if(obj->head > obj->size)obj->head = 1;return true;}return false;
}int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);if(!myCircularQueueIsEmpty(obj))return obj->arr[obj->head];return -1;
}int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);if(!myCircularQueueIsEmpty(obj))return obj->arr[obj->rear];return -1;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);if(obj->head == 0)return true;return false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);if(obj->rear+1 == obj->head)return true;if(obj->rear == obj->size && obj->head == 1)return true;return false;
}void myCircularQueueFree(MyCircularQueue* obj) {assert(obj);free(obj->arr);obj->arr = NULL;obj->head = obj->rear = obj->size = 0;
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/