前言
近日，在我的编程书上学习到了一种我之前未了解的数据结构——队列（Queue）。按照书上的解释，他是一种采用先进先出(FIFO)策略的抽象数据结构。
对于先进先出策略，在消息处理队列上应用再好不过了。在此之前，我一直头疼，我该如何规划多线程处理才能使那些线程们不打架，不抢占同一个全局变量，又可以做到先来的先用。但是很惭愧，我一直没得解决。我曾试过易语言的“许可区”，但是只能做到不打架，不能做到先来先得，而且有时候也会失效。
终于，在学会队列这一数据结构后，我尝试将其应用在我的机器人插件上，取得了巨大成功！
队列数据结构的实现
队列需要两个指针，front 和 end，来分别标记队头和队尾。
入队和出队的操作很简单。入队时，将 end 指针向后移动，并在该指针对应的数据空间上填上数据；出队时，删除 front 指针对应的数据空间，并将 front 指针向后移动。
听起来很简单是不是？ 但你没发现这像是一次性的数组吗？
当 end 移动到数组底部，队列将无法添加新内容，但可能在该数组变量的开头已经有好几组数据已经出队，数据空间被白白浪费。像这样的情况，我们称之为「假溢出」。
你或许可以等到 front 同样移动到底部后重置该队列，但我们有个更优的实现方法： 循环队列。
循环队列的思想，就是在 end 触碰底部后，回到头部。
循环队列也会出现些许问题，譬如循环到头部后与 front 撞车，或是误判 front 跑到了 end 前面导致队列卡住。而此时，你也将无法像之前一样简单的判断队列是否已满，搞不好就会真的 overflow 了。
这种情况，你可以考虑在每次入队出队时判断 front 与 end 指针大小与差值来确认队列情况。你也可以再使用一个指针来标记列队中的数据总数，又或是标记一个必为空的数据跟在front之前。
理论部分还要靠你细细琢磨，队列只是一种思想，没有架死的框架。
应用到消息处理上
如何把队列这一数据结构思想用到我的机器人插件上呢？
我的思路是，在每次事件处理函数被调用时，申请加入队列，并等到该我出队之后，开始处理函数，再申请出队。
这样做会遇到几个问题，一是如果队列加不进（overflow）咋办？ 我的方法是重新尝试加入队列。 一味的调大队列的长度在平时无实际用途，还吃内存，不如在这种特殊情况下特殊处理，忽略这些还未进入队列的线程，让其按循环的运气加入队列。 另，我的队列上限是 100。
二是，如何判断是否该我出队了？ 我的方法是用一个 while 循环，在加入队列后，不断请求一个给定的函数，取目前的队列头，如果是我，那么就跳出循环，开始处理函数。
三是，我的消息并发过大，结果抢着进队列的同一个位置怎么办？ 我在加入队列时，申请了指针之后，再次判断指针是否为空，如果不为空，则说明指针被抢走了，那么重新递归调用入队。我认为这在一定程度上可以规避队列里打架的问题出现。
四是，我的循环列队如何处理，如果卡住了怎么办，消息队列会不会全部卡住无法恢复？我的解决方案是，在新入队、退出队、判断队头时，都会检查队头是不是真实的，如果不是，则直接将队头指针 +1，并且判断队头时，若一个队头占用队头的时间超过 60秒，将直接踢出，下移指针。
后文
队列虽然是一个数据结构，但将其思想应用在消息队列上，又何尝不是一种尝试呢？我已经将应用了队列的版本更新包推送，静待用户们的反馈。
0 评论