从小工到专家：设计循环队列
预计阅读时间： 12分钟
题目：
设计你的循环队列实现。
循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”
收益：
解决该问题的最好办法，就是从生活中寻找答案， 如果一个题目在生活中没有经过严格逻辑推理，和成熟产品验证，这样题目根本不是一个好题目。 艺术来源于生活 却又高于生活，必须明白题目后面的背景和前因后果。
背景：
- Linux多线程服务端编程：使用muduo C 网络库 p260页 ，7.10章节 Timing wheel 踢掉空闲连接
- 如何实现应用层的心跳协议？假如我回答 10秒内 三次连连接不上实现了吗，三个实现方案清楚吗
假如 服务端管理着多达数万到数十万，甚至上千万的连接数，因此我们没法为每个连接使用一个Timer，那样太消耗资源。
众所周知寻常的定时器大概有两种，
一种是开阻塞线程，
另一种是开一个任务队列然后定期扫描。
显而易见这两种方式的弊端很明显，前者对线程消耗过大，
后者对时间消耗过大（很多未到时间的任务会被多次重复扫描消耗性能）
为了解决以上两个问题就可以使用TimingWheel数据结构。
George Varghese 和 Tony Lauck 1996 年的论文 Hashed and hierarchical timing wheels: efficient data structures for implementing a timer facility
- 描述Timing wheel 原理 了解吗？
- http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-wheels.pdf
- https://www.singchia.com/2017/11/25/An-Introduction-Of-Hierarchical-Timing-Wheels/
- https://www.youtube.com/watch?v=AftX7rqx-Uc 了解吗
- https://github.com/Xun-Zhou/timing_wheel/blob/master/src/com/utils/TimeWheel.java
- 那些惊艳的算法们（三）—— 时间轮 https://blog.csdn.net/mindfloating/article/details/8033340
场景：XXL-JOB是一个分布式任务调度平台 XL-JOB is a distributed task scheduling framework.
- 定时器如何实现的？https://www.xuxueli.com/blog/
- https://www.youtube.com/watch?v=rvZaS3CXicE 了解吗？
- 基于java的TimingWheel(时间轮算法)分布式任务调度系统
- 阅读：Java there is an implementation with Netty。
https://segmentfault.com/a/1190000010987765
https://zacard.net/2016/12/02/netty-hashedwheeltimer/
一句话输出：
第一句：存在的问题：由于netty动辄管理100w 的连接，每一个连接都会有很多超时任务。比如发送超时、心跳检测间隔等，如果每一个定时任务都启动一个Timer,不仅低效，而且会消耗大量的资源。
第二句：循环队列（HashedWheelTimer） 采用hash（HashedWheelBucket） list（HashedWheelTimeout）实现结构。
思路：
放弃别人技巧，自己真实理解是什么？
拦路虎：
- 这个概念很很清楚，但是让我代码写出来大脑一片空白，不知道如何下手，该如何分析 考虑什么？焦虑紧张，然后让你放弃，放弃远离它。hard
- 不写代码，用文字描述 我描述不出来，感觉就是知道，就是循环利用，array 定义2个变量。
感觉很清楚，但是很多问题，不知道问题哪在里
这个图片描述，有问题，默认情况他们 指向同一个位置。
- 读写速度如何控制，假如一只没有读取，不停的写入，如果是环形结构（缺点），肯定覆盖之前已经写入内容。数组满了不需要写入。 我思路：通过比较 2个指针位置大小，判断这个分为4个情况，很复杂， 别人说看不懂，思路不清楚，不知道为什么？ 自己感觉不好，陷入僵局，你想过比较大小 是个错误思路？
- 但好多人就是不知道如何判定队列是空是满 通过比较 2个指针大小 还是不清楚，感觉不好，不清晰，一下子区分不出来。 你没想一下，这样初始化大小对不对，难道一定必须不一样吗？
这个图片描述，有问题，默认情况他们 指向同一个位置
在这里插入图片描述
解决方案：
代码：
622. 设计循环队列
方法1 需要判断第一元素和最有一个元素特殊情况。
代码语言：javascript复制
class MyCircularQueue1
{
private:
vector<int> m_buffer; //三板斧： 数据结构用数组模拟环，这个大家都知道
int m_capacity; //最大容量
int m_readindex; //代表head，表示已经写入，还没有读取走。前面一个位置已经读取走了。索引小的最早来，最早走。
int m_writeindex; //代表tail，已经写入元素位置，下一个元素才是需要写入的。
//问题1 开始位置等于结束位置时候，如何判断此时是空队列 还是满队列 不清楚
//问题2:如果一直读取，超过写入怎办？
//问题3:如果一直写入，覆盖之前写入怎办？
public:
MyCircularQueue1(int k)
{
m_capacity = k;
m_readindex = -1; //上来不能直接下标获取，不让直接越界了。
m_writeindex = -1;////上来不能直接下标获取，不让直接越界了
m_buffer.resize(k); //
//
}
bool isEmpty()
{
return m_readindex == -1;
}
bool isFull()
{
return (m_writeindex 1)%m_capacity ==m_readindex;
}
//向循环队列插入一个元素。如果成功插入则返回真
bool enQueue(int value)
{
if (isFull())
{
return false;
//超过容量
}
//难点：循环队列插入第一元素：
if (isEmpty())
{
m_writeindex =m_readindex = 0; //运算符优先级 从右到左
}else{
m_writeindex = (m_writeindex 1) % m_capacity;
}
m_buffer[m_writeindex] = value;
return true;
}
bool deQueue()
{
if (isEmpty())
{
return false;
//m_writeindex ==m_readindex == -1;
//如果没有记录
}
//难点：循环队列只剩下最后一个元素。
if (m_readindex == m_writeindex)
{
m_writeindex =m_readindex = -1;
//细节地方1
//假如容量是10，插入5个元素，读取4个，还是剩余最有一个元素，tail=end。
//在读取一个元素。整个循环队列为空。
//此时在写入。位置重写移动回到原来位置。
}else
{
m_readindex = (m_readindex 1) % m_capacity;
}
return true;
}
//从队首获取元素。如果队列为空，返回 -1
int Front()
{
if (true == isEmpty())
{
return -1;
}
return m_buffer[m_readindex];
}
//获取队尾元素。如果队列为空，返回 -1
int Rear()
{
if (isEmpty())
{
return -1;
}
return m_buffer[m_writeindex];
}
};
class MyCircularQueue {
private:
int *data; // 存放循环队列的数据
int head; // 循环队列头
int tail; // 循环队列尾
int len; // 循环队列的最大长度
int count; // 循环队列的元素个数
public:
/** Initialize your data structure here. Set the size of the queue to be k. */
MyCircularQueue(int k) {
data = new int[k];
head = 0;
tail = 0;
len = k;
count = 0;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
bool enQueue(int value) {
if (isFull()) //循环队列满
{
return false;
}
else // 插入元素到队尾，队尾索引值增一，元素个数增一
{
data[tail] = value;
count ;
tail = (tail 1) % len;
return true;
}
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
bool deQueue() {
if (isEmpty()) //循环队列空
{
return false;
}
else // 队头索引值增一，元素个数减一
{
head = (head 1) % len;
count--;
return true;
}
}
/** Get the front item from the queue. */
int Front() {
if (isEmpty()) //循环队列空
{
return -1;
}
else
{
return data[head];
}
}
/** Get the last item from the queue. */
int Rear() {
if (isEmpty()) //循环队列空
{
return -1;
}
// 队尾元素位于队尾索引值减一的位置，但若队尾循环到索引 0 的位置，队尾元素位于数组最后
else
{
int temp = tail == 0 ? (len-1) : (tail-1);
return data[temp];
}
}
/** Checks whether the circular queue is empty or not. */
bool isEmpty() {
return count == 0; // 队列元素个数为零，队列空
}
/** Checks whether the circular queue is full or not. */
bool isFull() {
return count == len; // 队列元素个数为数组最大长度，队列满
}
};
总结：
为什么这么设计（Why’s THE Design）是一系列关于计算机领域中程序设计决策的文章， 我们在这个系列的每一篇文章中都会提出一个具体的问题并从不同的角度讨论这种设计的优缺点、对具体实现造成的影响 里面记录是基于个人学习下的的初步看法，欢迎各位大神斧正！
img
- 线程安全https://leetcode-cn.com/problemset/concurrency/
img
