【数据结构与算法】系列六 - 队列

发表于 | 分类于 ，
| 字数统计 1.5k 字 | 阅读时长 7 分钟

……

一、队列

队列（Queue）是一种特殊的线性表，只能在头尾两端进行操作。先进先出的原则，First In First Out，FIFO。

队尾（rear）：只能从队尾添加元素，一般叫做入队（enQueue）。

队头（front）：只能从队头移除元素，一般叫做出队（deQueue）。

接口设计

队列的内部实现可以利用动态数组、链表实现，但是优先使用双向链表，因为队列主要是往头尾操作元素，复杂度是O(1)。

接口：

1
2
3
4
5
6
int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void clear(); // 清空
void enQueue(E element); // 入队
E deQueue(); // 出队
E front(); // 获取队列的头元素

代码：

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
public class Queue<E> {
    private List<E> list = new LinkedList<>();

    public int size() {
      return list.size();
    }

    public boolean isEmpty() {
      return list.isEmpty();
    }

    public void clear() {
      list.clear();
    }

    public void enQueue(E element) {
      list.add(element);
    }

    public E deQueue() {
      return list.remove(0);
    }

    public E front() {
      return list.get(0);
    }
}

Java官方队列源码：java.util.Queue

二、双端队列

双端队列（deque：double ended queue）是能在头尾两端添加、删除的队列。

接口设计

接口：

1
2
3
4
5
6
7
8
9
int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void clear(); // 清空
void enQueueRear(E element); // 从队尾入队
E deQueueFront(); // 从队头出队
void enQueueFront(E element); // 从队头入队
E deQueueRear(); // 从队尾出队
E front(); // 获取队列的头元素
E rear(); // 获取队列的尾元素

代码（基于链表）：

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
public class Deque<E> {
    private List<E> list = new LinkedList<>();

    public int size() {
      return list.size();
    }

    public boolean isEmpty() {
      return list.isEmpty();
    }

    public void clear() {
      list.clear();
    }

    public void enQueueRear(E element) {
      list.add(element);
    }

    public E deQueueFront() {
      return list.remove(0);
    }

    public void enQueueFront(E element) {
      list.add(0, element);
    }

    public E deQueueRear() {
      return list.remove(list.size() - 1);
    }

    public E front() {
      return list.get(0);
    }

    public E rear() {
      return list.get(list.size() - 1);
    }
}

三、循环队列

其实队列底层也可以使用动态数组实现，并且各项接口也可以优化到O(1)的时间复杂度，这个用数组实现并且优化之后的队列也叫做：循环队列（Circle Queue）。

核心：指向头部的指针（front指向的位置就是队头，注意扩容时的对应关系）。

关键代码：索引转换(i + front) % elements.length

代码：

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
public class CircleQueue<E> {
    private int front;
    private int size;
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;

    public CircleQueue() {
      elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    public int size() {
      return size;
    }

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

    public void clear() {
      for (int i = 0; i < size; i++) {
        elements[index(i)] = null;
      }
      front = 0;
      size = 0;
    }

    public void enQueue(E element) {
      ensureCapacity(size + 1);
      
      // 优化前（模）：elements[(front + size) % elements.length] = element;
      // 优化后（去模）：elements[index(size)] = element;
      elements[index(size)] = element;
      
      size++;
    }

    public E deQueue() {
      E frontElement = elements[front];
      elements[front] = null;
      // 优化前（模）：front = (front + 1) % elements.length;
      // 优化后（去模）：front = index(1);
      front = index(1);
      size--;
      return frontElement;
    }

    public E front() {
      return elements[front];
    }

    // 封装索引
    private int index(int index) {
      index += front;
      return index - (index >= elements.length ? elements.length : 0);
    }

    /**
     * 保证要有capacity的容量
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
      int oldCapacity = elements.length;
      if (oldCapacity >= capacity) return;
      
      // 新容量为旧容量的1.5倍
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      E[] newElements = (E[]) new Object[newCapacity];
      for (int i = 0; i < size; i++) {
        // 优化前（模）：newElements[i] = elements[(i + front) % elements.length];
        // 优化后（去模）：newElements[i] = elements[index(i)];
        newElements[i] = elements[index(i)];
      }
      elements = newElements;
      
      // 重置front
      front = 0;
    }
}

四、循环双端队列

循环双端队列是可以进行两端添加、删除操作的循环队列。

尾部不需要指针，只需要头部指针索引加上元素数量模上数组长度。

代码：

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
public class CircleDeque<E> {
    private int front;
    private int size;
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;

    public CircleDeque() {
      elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    public int size() {
      return size;
    }

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

    public void clear() {
      for (int i = 0; i < size; i++) {
        elements[index(i)] = null;
      }
      front = 0;
      size = 0;
    }

    /**
     * 从尾部入队
     * @param element
     */
    public void enQueueRear(E element) {
      ensureCapacity(size + 1);
      
      elements[index(size)] = element;
      size++;
    }

    /**
     * 从头部出队
     * @param element
     */
    public E deQueueFront() {
      E frontElement = elements[front];
      elements[front] = null;
      front = index(1);
      size--;
      return frontElement;
    }

    /**
     * 从头部入队
     * @param element
     */
    public void enQueueFront(E element) {
      ensureCapacity(size + 1);
      
      front = index(-1);
      elements[front] = element;
      size++;
    }

    /**
     * 从尾部出队
     * @param element
     */
    public E deQueueRear() {
      int rearIndex = index(size - 1);
      E rear = elements[rearIndex];
      elements[rearIndex] = null;
      size--;
      return rear;
    }

    public E front() {
      return elements[front];
    }

    public E rear() {
      return elements[index(size - 1)];
    }

    private int index(int index) {
      index += front;
      if (index < 0) {
        return index + elements.length;
      }
      return index - (index >= elements.length ? elements.length : 0);
    }

    /**
     * 保证要有capacity的容量
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
      int oldCapacity = elements.length;
      if (oldCapacity >= capacity) return;
      
      // 新容量为旧容量的1.5倍
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      E[] newElements = (E[]) new Object[newCapacity];
      for (int i = 0; i < size; i++) {
        newElements[i] = elements[index(i)];
      }
      elements = newElements;
      
      // 重置front
      front = 0;
    }
}

五、运算符优化

尽量避免使用乘*、除/、模%、浮点数运算，效率低下。

模运算符：

假设有n，m两个数，且n >= 0, m > 0，当两个数相差在两倍（不含）以内时（n < 2m）：

  • n >= m，n % m的运算结果就是n - m
  • n < m，n % m的运算结果就是n
  • 结论（已知前提条件下）：n % m等价于n - (n >= m ? m : 0)

例如上面代码中的模运算符：

优化前:

1
2
3
private int index(int index) {
  return (front + index) % elements.length;
}

优化后:

1
2
3
4
private int index(int index) {
  index += front;
  return index - (elements.length > index ? 0 : elements.length);
}

六、LeetCode

用栈实现队列

题目：


题解：
将一个栈当作输入栈，用于压入push传入的数据；另一个栈当作输出栈，用于pop和peek操作。

每次pop或peek时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

代码：

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
class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public MyQueue() {
        inStack = new LinkedList<Integer>();
        outStack = new LinkedList<Integer>();
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.pop();
    }
    
    public int peek() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}