Java数据结构与算法笔记——双端队列_java 前后端组合

双端队列简介

双端队列就是一个两端都是结尾或者开头的队列。队列的每一端都可以进行插入数据项和移除数据项，这些方法可以叫做：addFirst()、addLast()、removeFrist()、removeLast()

如果只用addFirst()和removeFrist()，或者只使用addLast()和removeLast()，就是栈，先进后出

如果交叉使用addFirst()插入数据，removeLast()取数据（反之亦然）就是前面讲的普通队列，先进先出

实现思路

1.和集合一样，双端队列在内部数组容量不足时，能动态的扩容。

2.双端队列内部有“头部下标”和“尾部下标”，头部下标指向的是队列中的第一位元素，尾部下标指向的是下一个尾部元素插入的位置（一个空位置）。

• 从头部下标开始，到尾部下标截止（左闭右开区间），连续保存着队列中的全部元素。
• 当头部元素入队时，头部下标向左移动一位；头部元素出队时，头部下标向右移动一位。
• 当尾部元素入队时，尾部下标向右移动一位；尾部元素出队时，尾部下标向左移动一位。

3.当元素下标的移动达到了边界时，需要将数组从逻辑上看成一个环，其头尾是相邻的。

• 下标在数组第0位时，向左移动一位，会跳转到数组的最后一位。
• 下标从数组最后一位时，向右移动一位，会跳转到数组的第0位。

下标越界时的跳转操作，在细节上是通过下标取模实现的。

两个重要的算法

取模运算

在jdk中基于数组的双端队列实现中，强制保持内部数组容量为2的某次方（初始化时容量为2²2，也就是16，每次自动扩容容量*2），因此其取模运算可以通过按位与(&)运算来加快计算速度。因为二进制运算速率高。

2ⁿ-1和其他的数字进行按位与运算有很明显的特点。
例如：
-1 & 15 =15
2 & 15 = 2
16 & 15 = 0
17 & 15 = 1

    //取模计算，实现指针在数组中无限的循环
    public int getMod(int index){//传入的index为移动之后的指针值
        return index & (maxSize-1); //按位与运算
    }
1
2
3
4

扩容操作

size*2创建一个新的数组。
将前端插入的元素（红色）放在最前面，后端插入的元素（蓝色）放在前端元素的后面，后面的保持为空。

    //扩容
    public void expand(){
        int newSize = maxSize << 1; //左位移，数据值翻倍
        Object[] newObjArr = new Object[newSize];
        //获取前端插入的数据的个数
        int n = maxSize - head;
        //获取后端插入的元素的个数，=head
        System.arraycopy(elements,head,newObjArr,0,n);//复制前端插入数据
            //(老数组，开始位置，新数组，开始位置，复制元素个数)
        System.arraycopy(elements,0,newObjArr,n,head);//复制后端插入的数据

        head = 0;
        tail = maxSize;
        maxSize = newSize;
        elements = newObjArr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

代码实现

package queue;

public class QueueTest2 {
    public static void main(String[] args) {
        //把双端队列当栈来用
        DoubleEndedQueue queue = new DoubleEndedQueue();
        queue.addFirst(1);
        queue.addFirst(2);
        System.out.println(queue.peekFirst());
        //把双端队列当普通队列来用
        DoubleEndedQueue queue1 = new DoubleEndedQueue();
        queue1.addFirst(1);
        queue1.addFirst(2);
        System.out.println(queue1.peekLast());
        //使用双端队列本身
        DoubleEndedQueue queue2 = new DoubleEndedQueue();
        queue2.addFirst(1);
        queue2.addFirst(2);
        for (int i=3;i<16;i++){
            queue2.addLast(i);
        }
        queue2.addLast(16);
        queue2.addLast(17);

        while (!queue2.isEmpty()){
            System.out.println(queue2.removeFirst());
        }
    }
}

class DoubleEndedQueue{
    private Object[] elements;//内部封装的数组，初始化长度定义为16（2^2^2）
    private int maxSize;//最大长度
    private  int head;//队列的头部下标
    private int tail;//队列尾部下标

    //构造方法，初始化属性
    public DoubleEndedQueue(){
        elements = new Object[16];//初始化长度定义为16（2^2^2）
        maxSize = 16;
        head = 0;
        tail = 0;
        // 双端队列只有在空队列（或者满队列）的时候，head才会等于tail。
        // 后面的程序执行中，添加了数据后，再遇到head=tail就说明队满了
    }

    //取模计算，实现指针在数组中无限的循环
    public int getMod(int index){//传入的index为移动之后的指针值
//        if(index < 0){
//            index = index + maxSize;
//        }
//        if(index >= maxSize){
//            index = index - maxSize;
//        }
//        return index;
        return index & (maxSize-1); //按位与运算
    }

    //头部插入元素
    public void addFirst(Object data){
        //head = getMod(head-1);
        head = (head-1)&(maxSize-1);//取模运算,头部指针向左移动一位
        elements[head] = data; // 插入元素
        if (head == tail){//队列已满
            //扩容，长度进行扩容
            expand();
        }
    }

    //尾部插入元素
    public void addLast(Object data){
        //先把数据插入
        elements[tail] = data;
        tail = getMod(tail+1);//实现尾部指针右移一位
        if (head == tail){//队列已满
            //扩容，长度进行扩容
            expand();
        }
    }

    //实现头部移除
    public Object removeFirst(){
        Object removeObj = null;
        if (head != tail){//不是空队列
            removeObj = elements[head];
            elements[head] = null; //删除要移除的数据
            head = getMod(head+1); //头部指针向右移动一位
        }
        return removeObj;
    }

    //实现尾部删除数据
    public Object removeLast(){
        Object removeObj = null;
        if (head != tail) {//不是空队列
            tail = getMod(tail-1);
            removeObj = elements[tail];
            elements[tail] = null;
        }
        return removeObj;
    }

    //获取头部元素，不删除
    public Object peekFirst(){
        if (tail!=head){
            return elements[head];
        }else{
            return null;
        }
    }

    //获取尾部元素，不删除
    public Object peekLast(){
        if (head != tail){
            return elements[getMod(tail-1)];//只要是移动指针，就需要取模运算
        }else {
            return null;
        }
    }

    //扩容
    public void expand(){
        int newSize = maxSize << 1; //左位移，数据值翻倍
        Object[] newObjArr = new Object[newSize];
        //获取前端插入的数据的个数
        int n = maxSize - head;
        //获取后端插入的元素的个数，=head
        System.arraycopy(elements,head,newObjArr,0,n);//复制前端插入数据
            //(老数组，开始位置，新数组，开始位置，复制元素个数)
        System.arraycopy(elements,0,newObjArr,n,head);//复制后端插入的数据

        head = 0;
        tail = maxSize;
        maxSize = newSize;
        elements = newObjArr;
    }

    //获取双端队列的元素个数
    public int getSize(){
        return getMod(tail-head);
    }

    //判断队列是否为空
    public boolean isEmpty(){
        return (head == tail);
    }
}
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147