其他
359，数据结构-3,队列
基础知识
队列是一种特殊的线性表，他的特殊性在于我们只能操作他头部和尾部的元素，中间的元素我们操作不了，我们只能在他的头部进行删除，尾部进行添加。就像大家排队到银行取钱一样，先来的肯定要排到前面，后来的只能排在队尾，所有元素都要遵守这个操作，没有VIP会员，所以走后门插队的现象是不可能存在的，他是一种先进先出的数据结构。我们来看一下队列的数据结构是什么样的
1，一般队列
他只能从左边进，右边出，队列实现方式一般有两种，一种是基于数组的，还一种是基于链表的，如果基于链表的倒还好说，因为链表的长度是随时都可以变的，这个实现起来比较简单。如果是基于数组的，就会稍微有点不同，因为数组的大小在初始化的时候就已经固定了，我们来看一下基于数组的实现，假如我们初始化一个长度是10的队列
front指向的是队列的头，tail指向的是队列尾的下一个存储空间，最初始的时候front=0，tail=0，每添加一个元素tail就加1，每移除一个元素front就加1，但是这样会有一个问题，如果一个元素不停的加入队列，然后再不停的从队列中移除，会导致tail和front越来越大，最后会导致队列无法再加入数据了，但实际上队列前面全部都是空的，这导致空间的极大浪费。我们自己来写一个简单的队列看一下
1public class MyQueue<E> {
2
3 private final Object[] data;
4 private final int maxSize;
5 private int size;
6 private int front = 0;
7 private int tail = 0;
8
9 public MyQueue(int maxSize) {
10 if (maxSize <= 0) {
11 throw new IllegalArgumentException("队列容量必须大于0 : " + maxSize);
12 }
13 this.maxSize = maxSize;
14 data = new Object[this.maxSize];
15 }
16
17 public void add(E e) {
18 if (isFull()) {//这地方可以扩容也可以抛异常，为了方便这里我们就不在扩容了。
19 throw new IllegalStateException("队列已经满了，无法再加入……");
20 }
21 data[tail++] = e;
22 size++;
23 }
24
25 public E remove() {
26 if (isEmpty()) {
27 throw new IllegalStateException("队列是空的，无法移除……");
28 }
29 E t = (E) data[front];
30 data[front++] = null;
31 size--;
32 return t;
33 }
34
35 //队列头和队列尾指向同一空间的时候，并且没到队尾，表示队列是空的
36 public boolean isEmpty() {
37 return front == tail && !isFull();
38 }
39
40 public boolean isFull() {//最后一个位置是不存储数据的
41 return tail == maxSize - 1;
42 }
43
44 public int getSize() {
45 return size;
46 }
47}
代码非常简单，当然队列的实现不一定是这一种方式，比如我们可以让tail指向队尾的元素，或者以链表的形式来实现都是可以的，不同的实现方式会导致上面的方法有所不同。我们来测试一下
1public static void main(String[] args) {
2 MyQueue myQueue = new MyQueue(10);
3 System.out.println("isEmpty()=" + myQueue.isEmpty());
4 System.out.println("isFull()=" + myQueue.isFull());
5 System.out.println("getSize()=" + myQueue.getSize());
6 for (int i = 0; i < 9; i++) {
7 myQueue.add(i * 100);
8 myQueue.remove();
9 }
10 System.out.println("----------------------------");
11 System.out.println("isEmpty()=" + myQueue.isEmpty());
12 System.out.println("isFull()=" + myQueue.isFull());
13 System.out.println("getSize()=" + myQueue.getSize());
14}
看一下打印的结果
1 isEmpty()=true
2 isFull()=false
3 getSize()=0
4 ----------------------------
5 isEmpty()=false
6 isFull()=true
7 getSize()=0
我们添加了9次，然后又移除了9次，结果队列竟然满了，如果我们再添加一次的话肯定会抛异常，但实际上队列的size是0，还是空的，也就是说数组的每个位置只能使用一次，这样就造成了极大的浪费。那么前面使用过的空间还能不能再次利用了呢，实际上是可以的，我们可以把队列看成是环形的，当tail到达数组末尾的时候，如果数组的前面有空位子，我们可以让tail从头开始，这个时候一个新的队列就产生了，那就是双端队列。
2，双端队列
双端队列也是有两个指针，front指向队首，tail指向队尾的下一个存储单元，并且双端队列的队首和队尾都可以添加和删除元素，我们来看一下图
这样空间就可以循环利用了，不会造成浪费，我们来看下代码
1public class MyQueue<E> {
2
3 //存储的元素
4 private Object[] data;
5
6 //指向队列头，这个头并不是数组的第0个元素，如果这样
7 // front就没有意义了，这个从下面的addFirst(E e)方
8 // 法也可以看出，如果当front等于0的时候，在添加到
9 // first，那么会添加到数组的末尾，并且front也指向
10 // 数组的末尾
11 private int front;
12
13 //指向队列尾的下一个空间，可以这样理解，front指向
14 // 的是第一个元素，tail指向的是最后一个元素的下一
15 // 个，指的是空的。
16 private int tail;
17
18
19 public MyQueue(int numElements) {
20 data = new Object[numElements];
21 }
22
23 //空间扩容，我们这里选择扩大一倍，当然也可以选择其
24 // 他值，仅仅当满的时候才能触发扩容， 这时候front
25 // 和tail都会指向同一个元素
26 private void doubleCapacity() {
27 int p = front;
28 int n = data.length;//数组的长度
29 //关键是r不好理解，举个例子，在数组中，front
30 // 不一定是之前0位置的，他可以指向其他位置，
31 // 比如原来空间大小为16，front为13，也就是第
32 // 14个元素（数组是从0开始的），那么r就是16-13=3，
33 // 也就是从front往后还有多少元素，待会copy的时候
34 // 也是先从最后的r个元素开始
35 int r = n - p;
36 Object[] a = new Object[n << 1];//扩大一倍
37 System.arraycopy(data, p, a, 0, r);//先copy后面的r个
38 System.arraycopy(data, 0, a, r, p);//再copy前面的p个
39 data = a;
40 //重新调整front和tail的值
41 front = 0;
42 tail = n;
43 }
44
45 public void addFirst(E e) {
46 //添加到front的前面，所以front-1
47 front = (front - 1 + data.length) % data.length;
48 data[front] = e;
49 if (front == tail)//判断是否满了
50 doubleCapacity();
51 }
52
53 public void addLast(E e) {
54 //添加到最后一个，这个方法和addFirst有很明显的不同，
55 // addFirst是添加的时候就要计算front的位置，而addLast
56 // 方法是存值之后在计算tail的，/因为tail位置是没有
57 // 存值的，他表示的末端元素的下一个，是空，所以存值之后
58 //要计算tail的值
59 data[tail] = e;
60 tail = (tail + 1) % data.length;
61 if (tail == front)//判断是否满
62 doubleCapacity();
63 }
64
65 public E removeFirst() {//删除第一个
66 if (isEmpty())
67 throw new IllegalStateException("队列是空的，无法移除……");
68 E result = (E) data[front];
69 data[front] = null;
70 // 删除第一个，这里的所有第一我们都认为是front所指的，
71 // 不是数组的0位置，然后在计算front的值
72 front = (front + 1) % data.length;
73 return result;
74 }
75
76 public E removeLast() {//删除最后一个
77 if (isEmpty())
78 throw new IllegalStateException("队列是空的，无法移除……");
79 tail = (tail - 1 + data.length) % data.length;
80 E result = (E) data[tail];
81 data[tail] = null;
82 return result;
83 }
84
85 public E peekFirst() {
86 if (isEmpty())
87 throw new IllegalStateException("队列是空的，无法获取……");
88 return (E) data[front];
89 }
90
91 public E peekLast() {
92 if (isEmpty())
93 throw new IllegalStateException("队列是空的，无法获取……");
94 return (E) data[(tail - 1 + data.length) % data.length];
95 }
96
97 public int size() {//元素的size
98 return (tail - front + data.length) % data.length;
99 }
100
101 //是否为空，在上面添加元素的时候也可能front==tail，当添加
102 // 元素之后front==tail的时候就认为是满了，然后扩容，重新
103 // 调整front和tail的值,所以扩容之后front就不可能等于tail。
104 //如果没有触发上面添加元素的时候front等于tail我们就认为他是空的。
105 public boolean isEmpty() {
106 return front == tail;
107 }
108}
代码中都有详细的注释，就不在过多介绍。