---

一、基础知识

• 环形队列：是首尾相连的先进后出的数据结构

• 特点：给定空间大小

• 应用：环形队列广泛用于网络数据收发，和不同程序间数据交换（比如内核与应用程序大量交换数据,从硬件接收大量数据）

• 实现：① 数组环队 ② 链表环队
  

• 一个严重的问题：
  (1) 如何判断队为空？(2) 如何判断队为满？答案:(1)front == tail (2)front == tail
  为了区别两个判断条件的重合问题，需要在数组队/链队预留一个空间的位置
  (1) front == tail (2) (tail+1)%5 == front
  

二、数组实现环队

结构体：

typedef struct CircularQueue
{int* arry; int front;int tail;int size;//数组大小
}CQueue;

2.1 初始化

//初始化
void CQueueInit(CQueue* cq, int k)
{assert(cq);cq->arry = (int*)malloc(sizeof(int) * (k+1));cq->front = cq->tail = 0;cq->size = k;
}

2.2 判断环队是否为空

//判断环形队列是否为空
bool CQueueIsEmpty(CQueue* cq)
{assert(cq);return cq->front == cq->tail;
}

2.3 判断环队是否为满

//判断环形队列是否为满
bool CQueueIsFull(CQueue* cq)
{assert(cq);return (cq->tail + 1) % (cq->size + 1) == cq->front;
}

2.4 入队

//入队
void CQueuePush(CQueue* cq, int x)
{assert(cq);if (CQueueIsFull(cq)){printf("队满！");exit(0);}cq->arry[cq->tail] = x;//赋值cq->tail = (cq->tail + 1) % (cq->size + 1);//tail走一步
}

2.5 出队

//出队
void CQueuePop(CQueue* cq)
{assert(cq);if (CQueueIsEmpty(cq)){printf("队空！");exit(0);}cq->front = (cq->front + 1) % (cq->size + 1);//front走一步
}

2.6 取队头元素

//取队头元素
int CQueueFront(CQueue* cq)
{assert(cq);if (CQueueIsEmpty(cq)){printf("队空！");exit(0);}return cq->arry[cq->front];
}

2.7 取队尾元素

//取队尾元素
int CQueueBack(CQueue* cq)
{assert(cq);if (CQueueIsEmpty(cq)){printf("队空！");exit(0);}int tail_i = (cq->tail + cq->size) % (cq->size + 1);//找到tail的上一个位置return cq->arry[tail_i];
}

2.8 销毁环队

//环形队列的销毁
void CQueueDestroy(CQueue* cq)
{assert(cq);free(cq->arry);free(cq);
}

“向后走”：(cur+1)%(k+1)
“向前走”：(cur+k)%(k+1)

三、链表实现环队

结构体：

typedef int DataType;
typedef struct CQueueNode
{DataType data;CQueueNode* next;
}CQueueNode;
typedef struct CQueue
{CQueueNode* front;CQueueNode* tail;
}CQueue;

3.1 初始化

//初始化
void CQueueInit(CQueue* cq, int k)
{assert(cq);CQueueNode* plist = CreatCQueueList(k + 1);cq->front = cq->tail = plist;
}
//创建k个结点的链表
CQueueNode* CreatCQueueList(int k)
{CQueueNode* phead = NULL;CQueueNode* tail = phead;while (k){CQueueNode* newNode = (CQueueNode*)malloc(sizeof(CQueueNode));newNode->next = NULL;if (phead == NULL){phead = tail =newNode;}else{tail->next = newNode;tail = newNode;}--k;}tail->next = phead;return phead;
}

3.2 判断环队是否为空

//判断环形队列是否为空
bool CQueueIsEmpty(CQueue* cq)
{assert(cq);return cq->front == cq->tail;
}

3.3 判断环队是否为满

//判断环形队列是否为满
bool CQueueIsFull(CQueue* cq)
{assert(cq);return cq->front == cq->tail->next;
}

3.4 入队

//入队
void CQueuePush(CQueue* cq, int x)
{assert(cq);if (CQueueIsFull(cq)){printf("队满！");exit(0);}cq->tail->data = x;cq->tail = cq->tail->next;
}

3.5 出队

//出队
void CQueuePop(CQueue* cq)
{assert(cq);if (CQueueIsEmpty(cq)){printf("队空！");exit(0);}cq->front = cq->front->next;
}

3.6 取队头元素

//取队头元素
int CQueueFront(CQueue* cq)
{assert(cq);if (CQueueIsEmpty(cq)){printf("队空！");exit(0);}return cq->front->data;
}

3.7 取队尾元素

//取队尾元素
int CQueueBack(CQueue* cq)
{assert(cq);if (CQueueIsEmpty(cq)){printf("队空！");exit(0);}CQueueNode* cur = cq->front;while (cur){if (cur->next == cq->tail)break;cur = cur->next;}return cur->data;
}

3.8 销毁环队

//环形队列的销毁
void CQueueDestroy(CQueue* cq)
{assert(cq);//第一层：free链表结点CQueueNode* cur = cq->front;while (cur){CQueueNode* next = cur->next;free(cur);cur = next;}//第二层：free front和tailfree(cq);
}