一种消息接收并打印的结构设计

消息流吐出 2,一种结构接收而不打印 2,因为 1 还没出现。
消息流吐出 1,一种结构接收 1,并且打印:1,2。
消息流吐出 4,一种结构接收而不打印 4,因为 3 还没出现。
消息流吐出 5,一种结构接收而不打印 5,因为 3 还没出现。
消息流吐出 7,一种结构接收而不打印 7,因为 3 还没出现。
消息流吐出 3,一种结构接收 3,并且打印:3,4,5。
消息流吐出 9,一种结构接收而不打印 9,因为 6 还没出现。
消息流吐出 8,一种结构接收而不打印 8,因为 6 还没出现。
消息流吐出 6,一种结构接收 6,并且打印:6,7,8,9。
已知一个消息流会不断地吐出整数1~N，但不一定按照顺序吐出。如果上次打印的数为i，那么当i+1出现时,请打印i+1及其之后接收过的并且连续的所有数,直到1~N全部接收并打印完，请设计这种接收并打印的结构。

应用udp和滑动窗口

思路

把每一个吐出的消息都看成单独的一个集合，每当进入新的集合n时候就进行合并。
与上面n-1合并，与下面的n+1合并
合并的过程就是查找是否有该值，因此使用hashMap分别存放未打印的可能成为头和尾的结点
然后根据即将打印的值，判断本次是否可以打印

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//节点信息
public static class Node{
	int value;
	Node next;
	public Node(int value){
		this.value = value;
	}
}
public static class MessageBox{
	HashMap<Integer, Node> headMap;
	HashMap<Integer, Node> tailMap;
	//即将打印的数字
	int printNum;
	public MessageBox(){
		//表示未打印集合中的头结点
		headMap = new HashMap<Integer, Node>();
		//表示未打印集合中的尾结点
		tailMap = new HashMap<Integer, Node>();
		printNum = 1;
	}
	
	public void receive(int value) {
		if(value < 1){
			return;
		}
		//把node看做单独的节点
		Node node = new Node(value);
		headMap.put(value, node);
		tailMap.put(value, node);
		//由于value-1是头，因此hand中应该包含，而tail中不应该包含
		//因此tail去掉value-1,head去掉value
		if(tailMap.containsKey(value-1)){
			tailMap.get(value-1).next = node;
			headMap.remove(value);
			tailMap.remove(value-1);
		}
		//value+1是尾，tail中应该包含，而head中不应该有
		//因此head去掉value+1，tail去掉value
		if(headMap.containsKey(value+1)){
			node.next = headMap.get(value+1);
			tailMap.remove(value);
			headMap.remove(value+1);
		}
		//打印，看头结点是否有即将打印的数字
		if(headMap.containsKey(printNum)){
			printNode();
		}
	}
	public void printNode(){
		Node node = headMap.get(printNum);
		//因为已经打印，所以head中要去掉
		headMap.remove(printNum--);
		while (node != null) {
			System.out.print(node.value + " ");
			node = node.next;
			printNum++;
		}
		System.out.println();
		//打印完成后去掉尾结点
		tailMap.remove(printNum);
		printNum++;
	}
}