03 队列(Queue)

队列是一种先进先出的数据结构（First In First Out, FIFO）。本文将以数组分别实现数组队列和循环队列两种底层的数据结构。

1. 队列接口

 1 /**
 2  * @author 阿遠
 3  * Date: 2019/1/14
 4  * Time: 21:21
 5  */
 6 public interface Queue<E> {
 7 
 8     int getSize();
 9     boolean isEmpty();
10     void enqueue(E e); // 入队
11     E dequeue();  // 出队
12     E getFront(); // 获取队头元素
13 }

2.数组队列的实现

  1 /**
  2  * @author 阿遠
  3  * Date: 2019/1/13
  4  * Time: 19:29
  5  */
  6 // 数组操作接口的实现
  7 public class Array<E> {
  8 
  9     private E[] data;
 10     private  int size; // 数组中实际元素数量
 11 
 12     // 构造函数，传入数组的容量capacity构造Array
 13     public Array(int capacity) {
 14         data = (E[]) new Object[capacity];
 15         size = 0;
 16     }
 17     // 默认构造函数，默认数组的容量capacity=10
 18     public Array() {
 19         this(10);
 20     }
 21     // 获取数组中的容量
 22     public int getCapacity() {
 23         return data.length;
 24     }
 25     //获取数组的元素个数
 26     public int getSize() {
 27         return size;
 28     }
 29     // 判断数组是否为空
 30     public boolean isEmpty() {
 31         return size == 0;
 32     }
 33     // 向所有元素后添加一个新元素
 34     public void addLast(E e) {
 35 //        if (size == data.length){
 36 //            throw new IllegalArgumentException("addLast failed!Array is full");
 37 //        }
 38 //        data[size] = e;
 39 //        size++;
 40         // 复用add
 41         add(size, e);
 42     }
 43     //在所有元素前添加新元素
 44     public void addFirst(E e) {
 45         add(0, e);
 46     }
 47     // 在index个位置插入一个新元素,扩容成动态数组，此处我们扩容成原来的2倍，在ArrayList中为1.5倍
 48     public void add(int index, E e) {
 49 
 50         if (index < 0 || index > size) {
 51             throw new IllegalArgumentException("Add failed!Index required >=0 and <size");
 52         }
 53         if (size == data.length){
 54             resize(2 * data.length);
 55         }
 56         for (int i = size-1; i >= index; i--){
 57             data[i+1] = data[i];
 58         }
 59         data[index] = e;
 60         size ++;
 61     }
 62     // 给数组扩容或者缩容
 63     private void resize(int newCapacity) {
 64         E[] newData = (E[]) new  Object[newCapacity];
 65         for (int i = 0; i < size; i++) {
 66             newData[i] = data[i];
 67         }
 68         data = newData;
 69     }
 70     // 获取index索引位置的元素
 71     public E get(int index) {
 72         if (index < 0 || index > size) {
 73             throw new IllegalArgumentException("Get failed!Index is illegal.");
 74         }
 75         return data[index];
 76     }
 77     // 获取数组第一个元素
 78     public E getFirst() {
 79         return get(0);
 80     }
 81     // 获取数组最后一个元素
 82     public E getLast() {
 83         return get(size-1);
 84     }
 85     //修改index元素索引位置的元素为e
 86     public void  set(int index, E e) {
 87         if (index < 0 || index > size) {
 88             throw new IllegalArgumentException("Set failed!Index is illegal.");
 89         }
 90         data[index] = e;
 91     }
 92 
 93     @Override
 94     public  String toString() {
 95         StringBuilder res = new StringBuilder();
 96         res.append(String.format("Array: size = %d, capacity = %d
", size, data.length));
 97         res.append("[");
 98         for (int i = 0; i < size; i++) {
 99             res.append(data[i]);
100             if (i != size-1)
101                 res.append(", ");
102         }
103         res.append("]");
104         return res.toString();
105     }
106 
107     // 查找数组中是否存在元素e
108     public boolean contains(E e) {
109         for (int i= 0; i < size; i++) {
110             if (data[i] == e)
111                 return true;
112         }
113         return false;
114     }
115     // 查找数组中元素e所在的索引，如果不存在元素e,则返回-1
116     public int find(E e) {
117         for (int i = 0; i < size; i++) {
118             if (data[i] == e)
119                 return  i;
120         }
121         return -1;
122     }
123     // 从数组中删除元素,返回删除的元素
124     public E remove(int index) {
125         if (index < 0 || index >= size) {
126             throw new IllegalArgumentException("Remove failed!Index is illegal.");
127         }
128         E ret = data[index];
129         for (int i = index + 1; i < size; i++) {
130             data[i-1] = data[i];
131         }
132         size --;
133         data[size] = null; // loitering objects != memory leak
134         if (size == data.length/4 && data.length/2 != 0) {
135             resize(data.length/2);
136         }
137         return ret;
138     }
139     // 从数组中删除第一个元素
140     public E removeFirst() {
141         return remove(0);
142     }
143     // 从元素中删除最后一个元素
144     public E removeLast() {
145         return remove(size-1);
146     }
147     // 从数组中删除元素e
148     public void removeElement(E e) {
149         int index = find(e);
150         if (index != -1) {
151             remove(index);
152         }
153     }
154 }

Array

/**
 * @author 阿遠
 * Date: 2019/1/14
 * Time: 21:24
 */

/**
 * 队列的数组实现
 * @param <E>
 */
public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array;

    public ArrayQueue(int capacity){
        array = new Array<E>(capacity);
    }

    public ArrayQueue() {
        array = new Array<E>();
    }

    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    // 先进先出，从队尾添加元素
    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

    // 先进先出，从队头删除元素
    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    // 查看队头的元素
    @Override
    public E getFront() {
        return array.getFirst();
    }

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();
        res.append("Queue：");
        res.append("front [");
        for (int i = 0; i < array.getSize(); i++){
            res.append(array.get(i));
            if (i != array.getSize()-1) {
                res.append(", ");
            }
        }
        // 数组的右侧是队尾
        res.append("] tail");
        return res.toString();
    }
}

ArrayQueue

　　测试：

 1 public class Main {
 2 
 3     public static void main(String[] args) {
 4 
 5        ArrayQueue<Integer> queue = new ArrayQueue<Integer>();
 6        for (int i = 0; i < 10; i++) {
 7            queue.enqueue(i);
 8            System.out.println(queue);
 9            if (i % 3 == 2) {  // 每入队3个元素出队1个
10                queue.dequeue();
11                System.out.println(queue);
12            }
13        }
14     }
15 }

　　测试结果：

Queue：front [0] tail
Queue：front [0, 1] tail
Queue：front [0, 1, 2] tail
从队头删除1个元素：
Queue：front [1, 2] tail
Queue：front [1, 2, 3] tail
Queue：front [1, 2, 3, 4] tail
Queue：front [1, 2, 3, 4, 5] tail
从队头删除1个元素：
Queue：front [2, 3, 4, 5] tail
Queue：front [2, 3, 4, 5, 6] tail
Queue：front [2, 3, 4, 5, 6, 7] tail
Queue：front [2, 3, 4, 5, 6, 7, 8] tail
从队头删除1个元素：
Queue：front [3, 4, 5, 6, 7, 8] tail
Queue：front [3, 4, 5, 6, 7, 8, 9] tail

3.循环队列的实现

 1 /**
 2  * @author 阿遠
 3  * Date: 2019/1/14
 4  * Time: 22:05
 5  */
 6 public class LoopQueue<E> implements Queue<E> {
 7 
 8     private E[] data;
 9     private int front, tail;
10     private int size;
11 
12     public LoopQueue(int capacity) {
13         data = (E[])new Object[capacity + 1];
14         front = 0;
15         tail = 0;
16         size = 0;
17     }
18 
19     public LoopQueue() {
20         this(10);
21     }
22 
23     public int getCapacity() {
24         return data.length - 1;
25     }
26 
27 
28     @Override
29     public int getSize() {
30         return size;
31     }
32 
33     @Override
34     public boolean isEmpty() {
35         return front == tail;
36     }
37 
38     @Override
39     public void enqueue(E e) {
40         if( (tail + 1) % data.length == front )
41             resize(getCapacity() * 2);
42         data[tail] = e;
43         tail = (tail + 1) % data.length;
44         size ++;
45     }
46 
47     private void resize(int newCapacity) {
48         E[] newData = (E[]) new  Object[newCapacity + 1];
49         for (int i = 0; i < size; i ++) {
50             newData[i] = data[(i + front) % data.length];
51         }
52         data = newData;
53         front = 0;
54         tail = size;
55     }
56 
57     @Override
58     public E dequeue() {
59 
60         if (isEmpty())
61             throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
62         E ret = data[front];
63         data[front] = null;
64         front = (front + 1) % data.length;
65         size --;
66         if (size == getCapacity()/4 && getCapacity()/2 != 0)
67             resize(getCapacity()/2);
68         return ret;
69     }
70 
71     @Override
72     public E getFront() {
73         if (isEmpty())
74             throw new IllegalArgumentException("Queue is empty.");
75         return data[front];
76     }
77 
78     @Override
79     public String toString() {
80         StringBuilder res = new StringBuilder();
81         res.append(String.format("Queue: size = %d, capacity = %d
", size,getCapacity()));
82         res.append("front [");
83         for (int i = front; i != tail; i = (i+1) % data.length){
84             res.append(data[i]);
85             if ((i + 1) % data.length != tail) {
86                 res.append(", ");
87             }
88         }
89         res.append("] tail");
90         return res.toString();
91     }
92 }

LoopQueue

　　测试：

 1 public class Main {
 2 
 3     public static void main(String[] args) {
 4 
 5        LoopQueue<Integer> queue = new LoopQueue<Integer>();
 6        for (int i = 0; i < 10; i++) {
 7            queue.enqueue(i);
 8            System.out.println(queue);
 9            if (i % 3 == 2) {  // 每入队3个元素出队1个
10                queue.dequeue();
11                System.out.println("从队头删除1个元素：");
12                System.out.println(queue);
13            }
14        }
15     }
16 }

　　测试结果：

Queue: size = 1, capacity = 10
front [0] tail
Queue: size = 2, capacity = 10
front [0, 1] tail
Queue: size = 3, capacity = 10
front [0, 1, 2] tail
从队头删除1个元素：
Queue: size = 2, capacity = 5
front [1, 2] tail
Queue: size = 3, capacity = 5
front [1, 2, 3] tail
Queue: size = 4, capacity = 5
front [1, 2, 3, 4] tail
Queue: size = 5, capacity = 5
front [1, 2, 3, 4, 5] tail
从队头删除1个元素：
Queue: size = 4, capacity = 5
front [2, 3, 4, 5] tail
Queue: size = 5, capacity = 5
front [2, 3, 4, 5, 6] tail
Queue: size = 6, capacity = 10
front [2, 3, 4, 5, 6, 7] tail
Queue: size = 7, capacity = 10
front [2, 3, 4, 5, 6, 7, 8] tail
从队头删除1个元素：
Queue: size = 6, capacity = 10
front [3, 4, 5, 6, 7, 8] tail
Queue: size = 7, capacity = 10
front [3, 4, 5, 6, 7, 8, 9] tail

4.队列的链表实现

/**
 * @author 阿遠
 * Date: 2019/1/17
 * Time: 15:55
 */
public class LinkedListQueue<E> implements Queue<E> {

    private Node head, tail;
    private int size;
    private class Node{
        public E e;  // 元素
        public Node next;   // 结点

        private Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }
    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }
    @Override
    public int getSize() {
        return size;
    }

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

    @Override
    public void enqueue(E e) {
        if (tail == null) { // 入队操作，从链表的尾结点增加元素
            tail = new Node(e);
            head = tail;
        } else {
            tail.next = new Node(e);
            tail = tail.next;
        }
        size ++;
    }

    @Override
    public E dequeue() {
        if (isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        Node retNode = head;
        head = head.next;
        retNode.next = null;
        if (head == null)
            tail = null;
        size ++;
        return retNode.e;
    }

    @Override
    public E getFront() {
        if (isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return head.e;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue: front ");

        Node cur = head;
        while(cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("Null tail");
        return res.toString();
    }
}

　　测试：

public class Main {

    public static void main(String[] args) {

       LinkedListQueue<Integer> queue = new LinkedListQueue<Integer>();
       for (int i = 0; i < 10; i++) {
           queue.enqueue(i);
           System.out.println(queue);
           if (i % 3 == 2) {  // 每入队3个元素出队1个
               queue.dequeue();
               System.out.println("从队头删除1个元素：");
               System.out.println(queue);
           }
       }
    }
}

　　测试结果：

Queue: front 0->Null tail
Queue: front 0->1->Null tail
Queue: front 0->1->2->Null tail
从队头删除1个元素：
Queue: front 1->2->Null tail
Queue: front 1->2->3->Null tail
Queue: front 1->2->3->4->Null tail
Queue: front 1->2->3->4->5->Null tail
从队头删除1个元素：
Queue: front 2->3->4->5->Null tail
Queue: front 2->3->4->5->6->Null tail
Queue: front 2->3->4->5->6->7->Null tail
Queue: front 2->3->4->5->6->7->8->Null tail
从队头删除1个元素：
Queue: front 3->4->5->6->7->8->Null tail
Queue: front 3->4->5->6->7->8->9->Null tail