前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

问题介绍

原问题
设计一种数据结构，该数据结构具有一个特点：
1、能够连续的接受自然数
2、类似于tcp滑动窗口保证数值的高可靠性，比如输入 1,2,4,5,6,3
当输入1时（开头），输出1即可
当输入2时（发现前面的1和自己连续了），输出2
当输入4时（接受到序列号4的报文），因为没有等到3，所以不输出4
同理接受5,6，但是不输出，因为3还没到
当输入3时，发现接上了1和2，所以输出3456

解决方案

原问题：
数据结构中包含三个数据结构：
1、双向链表节点DoubleNode，lastnode表示当前状态已经输出到哪个地方了
2、Map<Integer,DoubleNode> headlist,表示出现过的数和以该数为头节点的节点DoubleNode(需要保证输入不会有重复（通过set进行筛选）)
3、Map<Integer,DoubleNode> headlist,表示出现过的数和以该数为尾节点的节点DoubleNode

· 当获取到一个数num时，判断num+1是否存在于map中，如果存在说明这个数将可能成为新的头结点（就不会成为尾结点了）
· 判断num-1是否存在于map中，如果存在说明这个数可能成为新的尾节点（就不会成为头结点了）
· 如果都不再map中，说明自己成一个集合，放入map中即可

代码编写

java语言版本

原问题：
原问题：

public class MessageBoxCp {

    /**
     * 头节点列表：key代表某个值，value代表以该值为头的区间头结点
     */
    private Map<Integer, DoubleNode> headList;

    /**
     * 尾节点列表：key代表某个值，value代表以改值为尾的区间尾节点
     */
    private Map<Integer, DoubleNode> tailList;

    /**
     * 已经打印的节点列表的最后一个节点
     */
    private DoubleNode lastNode;


    public MessageBoxCp() {
        this.headList = new HashMap<>();
        this.tailList = new HashMap<>();
        this.lastNode = new DoubleNode(0);
    }

    /**
     * 接收值
     * @param num
     */
    public void reveive(Integer num) {
        if (num < 0) {
            return;
        }
        // 首先自成区间
        DoubleNode cur = new DoubleNode(num);
        headList.put(num, cur);
        tailList.put(num, cur);
        // 判断前面是否能连上
        if (tailList.containsKey(num - 1)) {
            // 1、更新上一个链表结尾
            DoubleNode last = tailList.get(num - 1);
            last.setNext(cur);
            // 2、删除上一个尾巴，cur为新的尾巴
            tailList.remove(num - 1);
            // 3、num为新的尾巴就不会是头了
            headList.remove(num);
        }
        if (headList.containsKey(num + 1)) {
            // 1、更新链表节点
            cur.setNext(headList.get(num + 1));
            // 2、删除老头
            headList.remove(num + 1);
            // 3、num为新的头就不会是尾巴了
            tailList.remove(num);
        }
        // 判断是否需要打印
        if (num == lastNode.getIntegerValue() + 1) {
            print();
        }
    }

    /**
     * 打印值
     */
    private void print(){
        //打印值
        int curNum = lastNode.getIntegerValue()+1;
        DoubleNode head = headList.get(curNum);
        DoubleNode curNode = head;
        while (curNode.getNext() != null) {
            System.out.println(curNode.getIntegerValue());
            curNode = curNode.getNext();
        }
        // 再输出一个
        System.out.println(curNode.getIntegerValue());
        // 删除头尾节点
        headList.remove(head.getIntegerValue());
        tailList.remove(curNode.getIntegerValue());
        // 更新last
        lastNode = curNode;
    }

    public static void main(String[] args) {
        MessageBoxCp messageBoxCp = new MessageBoxCp();
        messageBoxCp.reveive(1);
        messageBoxCp.reveive(3);
        messageBoxCp.reveive(4);
        messageBoxCp.reveive(2);
    }

}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这种数据结构第一个我想到的就是tcp保证数据有序的高可靠结构，实现原理很相似，其实还可以增加set来进行重复报文的筛选
，增加一个窗口大小当报文超过了窗口的丢弃掉等等。

第二种方式就是map结构用来处理连续数据的方式比较巧妙，利用了双向链表和map来记录一个有序的存储池。
我们可以不要print，lastnode作为滑动游标，保证存储池每一次获取到的值都是连续的，从小到大的

第三种方式我想用到业务中，比如地址池，地址池其实可以用bit数组来存储，但是我觉得这个数据结构能够存储地址段，双向链表和map的数据结构结合能够将一段连续的地址组成地址段，并且具有动态回收和相互融合的能力。

大家有什么业务需要使用的尽管提出来用到自己的业务中去吧！记得map可能存在并发访问，需要用到currenthashmap的哦

元空间

【算法】【算法杂谈】一种类似于滑动窗口的结构设计

目录

前言