特点

与普通队列不同的是，普通队列是在一端删除(头)，另一端添加(尾)
而双端队列是两端都可以删除、添加

双向链表实现双端队列

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

/**
 * 基于双向环形链表实现双端队列
 *
 * @param <E>-队列中的元素类型
 */
public class LinkedListDeque<E> implements Deque<E>, Iterable<E> {

    @Override
    public boolean offerFirst(E e) {
        if (isFull()) {
            return false;
        }
        //新加的节点的上一个是哨兵
        Node<E> a = sentinel;
        Node<E> b = sentinel.next;
        Node<E> added = new Node<>(a, e, b);
        a.next = added;
        b.prev = added;
        size++;
        return true;
    }

    @Override
    public boolean offerLast(E e) {
        if (isFull()) {
            return false;
        }
        //如果是尾部添加的话那么它的下一个就是哨兵
        Node<E> a = sentinel.prev;
        Node<E> b = sentinel;
        Node<E> added = new Node<>(a, e, b);
        a.next = added;
        b.prev = added;
        size++;
        return true;
    }

    @Override
    public E pollFirst() {
        if (isEmpty()) {
            return null;
        }
        Node<E> a = sentinel;
        Node<E> removed = sentinel.next;
        Node<E> b = removed.next;
        a.next = b;
        b.prev = a;
        size--;
        return removed.value;
    }

    @Override
    public E pollLast() {
        if (isEmpty()) {
            return null;
        }
        Node<E> b = sentinel;
        Node<E> removed = sentinel.prev;
        Node<E> a = removed.prev;
        a.next = b;
        b.prev = a;
        size--;
        return removed.value;
    }

    @Override
    public E peekFirst() {
        if(isEmpty()) {
            return null;
        }
        return sentinel.next.value;
    }

    @Override
    public E peekLast() {
        if(isEmpty()) {
            return null;
        }
        return sentinel.prev.value;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = sentinel.next;

            @Override
            public boolean hasNext() {
                return p != sentinel;
            }

            @Override
            public E next() {
                E value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    static class Node<E> {
        Node<E> prev;
        E value;
        Node<E> next;

        public Node(Node<E> prev, E value, Node<E> next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    int capacity;
    int size;
    Node<E> sentinel = new Node<>(null, null, null);

    public LinkedListDeque(int capacity) {
        this.capacity = capacity;
        //环形双向链表
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }
}

环形数组实现双端队列

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

/**
 * 基于循环数组实现双端队列
 * - tail停下来的位置不存储，会浪费一个位置
 * @param <E>-队列中元素类型
 */
public class ArrayDeque1<E> implements Deque<E>, Iterable<E> {

    //索引判断越界
    static int inc(int i, int length) {
        if(i + 1 >= length) {
            return 0;
        }
        return i + 1;
    }

    static int dec(int i, int length) {
        if(i - 1 < 0) {
            return length - 1;
        }
        return i - 1;
    }

    E[] array;
    int head;
    int tail;

    @SuppressWarnings("all")
    public ArrayDeque1(int capacity) {
        array = (E[]) new Object[capacity + 1];
    }

    @Override
    public boolean offerFirst(E e) {
        if(isFull()) {
            return false;
        }
        //在头部添加元素要先移动指针
        head = dec(head, array.length);
        array[head] = e;
        return true;
    }

    @Override
    public boolean offerLast(E e) {
        if(isFull()) {
            return false;
        }
        //在尾部添加元素要先添加再移动
        array[head] = e;
        tail = inc(tail, array.length);
        return true;
    }

    @Override
    public E pollFirst() {
        if(isEmpty()) {
            return null;
        }
        //先添加值再移动指针
        E e = array[head];
        array[head] = null; //垃圾回收，不占用字节不占用内存
        head = inc(head, array.length);
        return e;
    }

    @Override
    public E pollLast() {
        if(isEmpty()) {
            return null;
        }
        //先移动指针再删除
        tail = dec(tail, array.length);
        E e = array[tail];
        array[tail] = null; //垃圾回收，不占用内存
        return e;
    }

    @Override
    public E peekFirst() {
        if(isEmpty()) {
            return null;
        }
        return array[head];
    }

    @Override
    public E peekLast() {
        if(isEmpty()) {
            return null;
        }
        //因为尾指针不存储值，所以要取它前一个
        return array[dec(tail, array.length)];
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public boolean isFull() {
        if(tail > head) {
            return tail - head == array.length - 1;
        } else if(tail < head) {
            return head - tail == 1;
        } else {
            return false;
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;
            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public E next() {
                E e = array[p];
                p = inc(p, array.length);
                return e;
            }
        };
    }
}

练习:二叉树s字层序遍历

基本思想和普通遍历一致，但是s型遍历需要用双端队列，奇数列在尾部添加，偶数列在头部添加
这样就可以实现s型遍历

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
/*
            1
           / \
          2   3
         / \  / \
        4  5  6  7
    
    遍历结果：[[1], [3, 2], [4, 5, 6, 7]]
*/
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if(root == null) {
        return result;
    }
    //链表没有容量限制
    LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();
    queue.offer(root);
    int c1 = 1;//当前节点数
    boolean odd = true; //奇数层
    while(!queue.isEmpty()) {
        LinkedList<Integer> level = new LinkedList<>(); //保存每一轮结果
        int c2 = 0; //下一层节点数
        for (int i = 0; i < c1; i++) {
            //从头部获取元素
            TreeNode n = queue.pool();

            if(odd) {
                //奇数层在尾部添加
                level.offerLast(n.val);
            } else {
                //偶数层在头部添加
                level.offerFirst(n.val);
            }

            if(n.left != null) {
                queue.offer(n.left);
                c2++;
            }
            if(n.right != null) {
                queue.offer(n.right);
                c2++;
            }
        }
        //循环结束变奇数偶数
        odd = !odd;
        result.add(level);
        c1 = c2;
    }
    return result;
}