专栏首页别先生数据结构之队列

数据结构之队列

1、队列Queue,队列也是一种线性结构,相比数组,队列对应的操作是数组的子集,只能从一端(队尾)添加元素,只能从另一端(队首)取出元素。队列是一种先进先出的数据结构(或者称为先到先得),First In First Out(简称FIFO)。

2、封装的数组的代码,可以实现增加,修改,删除,查询,动态扩容,缩容,判断是否为空等等方法。

  1 package com.company;
  2 
  3 
  4 /**
  5  *
  6  */
  7 public class Array<E> {
  8 
  9     private E[] data;//定义数组
 10     private int size;//数组实际的长度
 11 
 12     /**
 13      * 构造函数,传入数组的容量capacity构造Array
 14      *
 15      * @param capacity 初始化数据的容量长度
 16      */
 17     public Array(int capacity) {
 18         // 使用泛型,可以创建任意类型的数组类型
 19         data = (E[]) new Object[capacity];
 20         // 初始化数组的实际内容的长度为0
 21         size = 0;
 22     }
 23 
 24     /**
 25      * 无参数的构造函数,默认数组的容量capacity=10
 26      */
 27     public Array() {
 28         // 无参构造函数,指定初始化数组容量长度为0
 29         this(10);
 30     }
 31 
 32     /**
 33      * 获取数组中的元素个数
 34      *
 35      * @return
 36      */
 37     public int getSize() {
 38         // 获取到数组中的元素个数
 39         return size;
 40     }
 41 
 42     /**
 43      * 获取数组的容量
 44      *
 45      * @return
 46      */
 47     public int getCapacity() {
 48         // 获取到数组的容量
 49         return data.length;
 50     }
 51 
 52     /**
 53      * 返回数组是否为空
 54      *
 55      * @return
 56      */
 57     public boolean isEmpty() {
 58         // 判断数组的长度是否为空
 59         return size == 0;
 60     }
 61 
 62 
 63     /**
 64      * 向所有元素后添加一个新元素
 65      *
 66      * @param e
 67      */
 68     public void addLast(E e) {
 69 //        if (size == data.length) {
 70 //            throw new IllegalArgumentException("AddLast failed,Array is full......");
 71 //        } else {
 72 //            在数组的末尾添加一个元素
 73 //            data[size] = e;
 74 //            添加元素以后数组长度加一
 75 //            size++;
 76 //        }
 77 
 78         // 调用公共的方法,其实就是在数组的实际长度后面添加指定的元素的。
 79 
 80         // 调用添加数组的方法,参数一,传入数组实际的长度,参数二,添加的元素
 81         add(size, e);
 82     }
 83 
 84     /**
 85      * 在第一个位置添加元素,在所有元素前添加一个新元素
 86      *
 87      * @param e
 88      */
 89     public void addFirst(E e) {
 90         // 在数组的第一个位置添加元素
 91         add(0, e);
 92     }
 93 
 94 
 95     /**
 96      * 在第index个位置插入一个新元素e
 97      *
 98      * @param index 在第index个位置
 99      * @param e     添加的元素内容
100      */
101     public void add(int index, E e) {
102         // 判断位置index是否小于0或者索引index是否大于数组的实际长度size
103         if (index < 0 || index > size) {
104             throw new IllegalArgumentException("add failed,Require index >= 0 and index <= size.......");
105         }
106 
107         // 判断实际长度size是否等于数组的长度
108         if (size == data.length) {
109             // 可以直接抛出异常
110             // throw new IllegalArgumentException("add failed,Array is full......");
111             // 调用数组扩容的方法,扩容的长度为元数组长度的2倍
112             resize(2 * data.length);
113         }
114 
115         // 添加元素,就是在最后一个位置,将元素添加进去,即size的位置
116         // 从后向前移动,从后面的元素向后移动
117         // 如果传入的index是size,则初始化的位置是size-1,那么i的值大于等于传入的index(即size的值),i递减
118 
119         // int i = size - 1是数组的实际长度的,即最后一个位置的元素
120         // i >= index,是在指定索引位置添加索引
121         // i--是为了将前面的元素向后面移动的。
122         for (int i = size - 1; i >= index; i--) {
123             // 后一个索引位置赋予前一个索引位置的值
124             data[i + 1] = data[i];
125         }
126         // 将元素的内容插入到数组的index索引位置
127         data[index] = e;
128         // 数组的size递增
129         size++;
130     }
131 
132     /**
133      * 私用扩容,扩容数组的长度
134      *
135      * @param newCapacity
136      */
137     private void resize(int newCapacity) {
138         // 使用泛型创建对象,使用new Object的方法创建泛型的对象
139         E[] newData = (E[]) new Object[newCapacity];
140         // 循环,将原数组里面的内容放入到新数组里面,新数组的长度为元素组的2倍
141         for (int i = 0; i < size; i++) {
142             // 将原数组的值赋值给新数组的值
143             newData[i] = data[i];
144         }
145         // 将原数组的值指向新数组,此操作,不影响原数组的正常使用
146         data = newData;
147     }
148 
149     /**
150      * 获取Index索引位置的元素
151      *
152      * @param index
153      * @return
154      */
155     public E get(int index) {
156         // 如果索引index小于0或者索引的长度大于等于实际长度size,则抛出异常
157         if (index < 0 || index >= size) {
158             throw new IllegalArgumentException("add failed,Index is illegal......");
159         }
160         // 返回指定索引位置的数组元素
161         return data[index];
162     }
163 
164     /**
165      * 获取到动态数组的第一个元素
166      *
167      * @return
168      */
169     public E getFirst() {
170         return get(0);
171     }
172 
173     /**
174      * 获取到数组的最后一个元素
175      *
176      * @return
177      */
178     public E getLast() {
179         // 调用获取元素的方法
180         // 避免使用return data[size - 1],可能会出现size=0的情况
181         return get(size - 1);
182     }
183 
184     /**
185      * 修改index索引位置的元素e
186      *
187      * @param index
188      */
189     public void set(int index, E e) {
190         // 如果索引index小于0或者索引的长度大于等于实际长度size,则抛出异常
191         if (index < 0 || index >= size) {
192             throw new IllegalArgumentException("add failed,Index is illegal......");
193         }
194         // 则将元素放入到数组的索引index位置
195         data[index] = e;
196     }
197 
198 
199     /**
200      * @return
201      */
202     @Override
203     public String toString() {
204         // 封装数组遍历的内容
205         StringBuilder sb = new StringBuilder();
206         sb.append(String.format("Array : size = %d,capacity = %d\n", size, data.length));
207         sb.append('[');
208         for (int i = 0; i < size; i++) {
209             sb.append(data[i]);
210             if (i != size - 1) {
211                 sb.append(", ");
212             }
213         }
214         sb.append(']');
215         return sb.toString();
216     }
217 
218     /**
219      * 查找数据中是否包含元素e
220      *
221      * @param e
222      * @return
223      */
224     public boolean contains(E e) {
225         // 查看是否包含元素,进行遍历
226         for (int i = 0; i < size; i++) {
227             // 如果数组元素等于传入的元素e
228             if (data[i].equals(e)) {
229                 // 返回true
230                 return true;
231             }
232         }
233         return false;
234     }
235 
236     /**
237      * 查找数组中元素e所在的索引,如果不存在元素e,则返回-1
238      *
239      * @param e
240      * @return
241      */
242     public int find(E e) {
243         // 查看是否包含元素,进行遍历
244         for (int i = 0; i < size; i++) {
245             // 如果数组元素等于传入的元素e
246             if (data[i].equals(e)) {
247                 // 返回该索引位置的索引
248                 return i;
249             }
250         }
251         return -1;
252     }
253 
254     /**
255      * 从数组中删除index位置的元素,返回删除的元素
256      *
257      * @param index 此参数是索引参数
258      * @return
259      */
260     public E remove(int index) {
261         // 如果索引位置小于等于0或者索引位置大于等于数组的实际长度size
262         if (index < 0 || index >= size) {
263             throw new IllegalArgumentException("remove failed,Index is illegal......");
264         }
265 
266         // 返回删除的元素,先获取到要删除的元素
267         E result = data[index];
268         // System.out.println(result);
269 
270         // 初始化值是要删除索引的位置加1,且i的值小于实际size的大小,i递减
271 
272         // int i = index + 1,传入进去的删除索引位置的元素
273         // i < size,i小于数组的实际长度
274         // i++,i递增
275         for (int i = index + 1; i < size; i++) {
276             // 将数组元素的值赋值被删除元素的位置上面
277             // 即将数组元素向前移动,即第i位置的索引的数据移动到第i-1位置索引的数据
278             data[i - 1] = data[i];
279         }
280         // 删除元素以后,数组长度size递减1
281         size--;
282         // 将不可访问的位置置空
283         data[size] = null;
284 
285         // 避免出现复杂度震荡
286         // 删除数组长度,缩小容量
287         // data.length / 2 != 0,避免出现创建数组长度为0的数组
288         if (size == data.length / 4 && data.length / 2 != 0) {
289             // 缩容数组的长度
290             resize(data.length / 2);
291         }
292         return result;
293     }
294 
295     /**
296      * 删除数组的第一个元素的值
297      * <p>
298      * 从删除中删除第一个元素,返回删除的元素
299      *
300      * @return
301      */
302     public E removeFirst() {
303         // 删除数组的第一个位置的元素
304         return remove(0);
305     }
306 
307     /**
308      * 从数组中删除最后一个元素,返回删除的元素。
309      *
310      * @return
311      */
312     public E removeLast() {
313         // 删除数组最后一个位置的元素
314         return remove(size - 1);
315     }
316 
317     /**
318      * 从数组中删除元素e
319      *
320      * @param e
321      */
322     public void removeElement(E e) {
323         // 查看数组里面是否有该元素
324         int index = find(e);
325         // 如果查找到存在该元素
326         if (index != -1) {
327             // 调用删除数组元素的方法
328             remove(index);
329         }
330     }
331 
332     public static void main(String[] args) {
333         // 数组添加元素
334         Array<Integer> array = new Array<>(20);
335         for (int i = 0; i < 10; i++) {
336             array.addLast(i);
337         }
338 
339         System.out.println(array.toString());
340 
341         // 在指定位置添加元素
342         array.add(1, 110);
343         System.out.println(array.toString());
344 
345         // 在第一个位置添加元素
346         array.addFirst(-1);
347         System.out.println(array.toString());
348 
349         // 修改index索引位置的元素e
350         array.set(1, 120);
351         System.out.println(array.toString());
352 
353         // 是否包含某个元素
354         boolean contains = array.contains(9);
355         System.out.println(contains);
356 
357         // 删除指定索引位置的元素
358         array.remove(2);
359         System.out.println(array);
360 
361         // 删除第一个索引位置的元素
362         array.removeFirst();
363         System.out.println(array);
364 
365         // 删除最后一个位置的元素
366         array.removeLast();
367         System.out.println(array);
368 
369         // 从数组中删除元素e
370         array.removeElement(110);
371         System.out.println(array);
372     }
373 
374 }

3、使用泛型,可以接受任何数据类型的。声明队列的接口。

 1 package com.queue;
 2 
 3 /**
 4  *
 5  */
 6 public interface Queue<E> {
 7 
 8     /**
 9      * 向队列中添加一个元素,入队。对应栈的入栈。
10      *
11      * @param e
12      */
13     public void enqueue(E e);
14 
15     /**
16      * 从队列中取出一个元素,出队。对应栈的出栈。
17      *
18      * @return
19      */
20     public E dequeue();
21 
22     /**
23      * 获取到队列中队首的元素。对应栈的查看栈顶的元素。
24      *
25      * @return
26      */
27     public E getFront();
28 
29     /**
30      * 获取到队列的大小
31      *
32      * @return
33      */
34     public int getSize();
35 
36     /**
37      * 判断队列是否为空
38      *
39      * @return
40      */
41     public boolean isEmpty();
42 
43 }

创建实现Queue自定义接口队列的类,QueueStack队列,结合创建的Array<E>动态数组来实现栈的入队,出队,查看队首元素,判断队列是否为空等等操作。

  1 package com.queue;
  2 
  3 import com.company.Array;
  4 
  5 /**
  6  * 队列是一种先进先出的数据结构(或者称为先到先得),First In First Out(简称FIFO)。
  7  * <p>
  8  * <p>
  9  * 1、public void enqueue(E e)入队方法,时间复杂度0(1),均摊时间复杂度。
 10  * 2、public E dequeue()出队方法,时间复杂度0(n)。因为队首元素拿出去以后,后面所有元素前移一位。
 11  * 如果数据量很大,这回造成执行很慢,使用循环队列可以使时间复杂度变成O(1)。
 12  * 3、public E getFront()获取队首方法,时间复杂度0(1)。
 13  * 4、public int getSize()获取队列大小,时间复杂度0(1)。
 14  * 5、public boolean isEmpty()获取队列是否为空,时间复杂度0(1)。
 15  *
 16  * @param <E>
 17  */
 18 public class ArrayQueue<E> implements Queue<E> {
 19 
 20     // 声明一个Array对象
 21     private Array<E> array;
 22 
 23 
 24     // Fn + Alt + Insert快捷键弹出构造函数
 25 
 26     /**
 27      * @param capacity 动态数组的容量大小
 28      */
 29     public ArrayQueue(int capacity) {
 30         //
 31         array = new Array<>(capacity);
 32     }
 33 
 34     /**
 35      * 无参的栈构造函数,创建一个默认容量大小的动态数组
 36      */
 37     public ArrayQueue() {
 38         array = new Array<>();
 39     }
 40 
 41     /**
 42      * 入队
 43      *
 44      * @param e
 45      */
 46     @Override
 47     public void enqueue(E e) {
 48         // 即向数组的末尾添加元素,如果动态数组容量不够,会触发动态数组的扩容机制
 49         array.addLast(e);
 50     }
 51 
 52     /**
 53      * 出队
 54      *
 55      * @return
 56      */
 57     @Override
 58     public E dequeue() {
 59         // 队列,是先进先出的,所以出队,是将开始的元素进行删除即可
 60         E first = array.removeFirst();
 61         return first;
 62     }
 63 
 64     /**
 65      * 获取队首元素
 66      *
 67      * @return
 68      */
 69     @Override
 70     public E getFront() {
 71         // 获取到队首元素
 72         E first = array.getFirst();
 73         return first;
 74     }
 75 
 76     /**
 77      * 查看队列大小
 78      *
 79      * @return
 80      */
 81     @Override
 82     public int getSize() {
 83         // 返回队列的大小
 84         return array.getSize();
 85     }
 86 
 87     /**
 88      * 判断队列是否为空
 89      *
 90      * @return
 91      */
 92     @Override
 93     public boolean isEmpty() {
 94         // 返回队列是否为空
 95         return array.isEmpty();
 96     }
 97 
 98     /**
 99      * 获取到队列的容量大小
100      *
101      * @return
102      */
103     public int getCapacity() {
104         return array.getCapacity();
105     }
106 
107     @Override
108     public String toString() {
109         StringBuilder sb = new StringBuilder();
110         sb.append("Queue: ");
111         sb.append("front [");
112         for (int i = 0; i < array.getSize(); i++) {
113             sb.append(array.get(i));
114             if (i != array.getSize() - 1) {
115                 sb.append(", ");
116             }
117         }
118         sb.append("] tail");
119         return sb.toString();
120     }
121 
122     public static void main(String[] args) {
123         ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
124         // 入队操作
125         for (int i = 0; i < 10; i++) {
126             arrayQueue.enqueue(i);
127             System.out.println(arrayQueue);
128         }
129 
130         // 出队操作
131         arrayQueue.dequeue();
132         System.out.println("出队操作: " + arrayQueue);
133 
134         // 获取到队列的大小
135         int size = arrayQueue.getSize();
136         System.out.println("获取到队列的大小: " + size);
137 
138         // 获取到队首的元素
139         Integer front = arrayQueue.getFront();
140         System.out.println("获取到队首的元素: " + front);
141 
142         // 判断队列是否为空
143         System.out.println("判断队列是否为空: " + arrayQueue.isEmpty());
144     }
145 
146 }

4、循环队列,初始的情况下,队列中无任何元素,front指向0位置,tail也指向0的位置。

  1)、注意,front应该指向队列的第一个元素,tail指向的位置是指队列中最后一个元素的后一个位置。但是,当队列整体为空的时候,即队列中连第一个元素都没有的时候,此时,front和tail指向同一个位置,都是指向0的位置,即front和tail相等的时候,队列为空。   2)、如果队列不为空的时候,front和tail是不会相等的,如果此时,有一个元素入队了,此时,只要维护tail队尾就行了,tail指向下一次一个元素再入队时候的位置。如果是出队,只需要维护front即可,将front向下一个位置移动一个就行了。   3)、循环队列,如果出现出队操作,不再要求所有的元素都进行移动了,只需要front的指向改变即可,时间复杂度就变成了O(1)的操作。   4)、循环队列,如果队列的队尾tail移动到最后一个位置的时候,如果队列的队首front前面还有空闲的位置,那么队列的队尾tail可以指向队列的队首front的前面的位置。此时,队列可以看成是一个环形。   5)、front和tail相等的时候,队列为空。所以队列的队首front和队列的队尾tail之间会存在一个空闲的位置,是无法被填写元素的。队列的队满是tail + 1 == front,表示队列的队满,准确的说,是(tail + 1) % c == front表示队列队满了。   6)、tail指向的位置是指下一次有元素入队应该放入的位置,一旦有一个新的元素放入了,tail就应该加一。   7)、循环队列中,在capacity容量中,浪费一个空间。如果只剩下一个空间的时候,循环队列就已经满了,就可以进行扩容了。

4.1、循环队列的入队操作。

a、b、c、d、e元素入队,维护tail的位置,tail进行自增操作就行了。

4.2、循环队列的出队操作,此时,如果要进行循环队列出队操作,那么如何进行的呢。如果元素a出队,那么需要对front进行维护即可。

如果此时,b元素进行出队操作,如下所示:

4.3、循环队列的循环操作。

循环队列是如何进行循环操作的。准确的说是(tail + 1) % c == front表示循环队列满了。由于到了数组的末端,还可以返回到数组的前端,跑到数组前端的过程就是靠的求余操作。front == tail表示循环队列为空了。

  1 package com.queue;
  2 
  3 /**
  4  * 循环队列
  5  *
  6  * @param <E>
  7  */
  8 public class LoopQueue<E> implements Queue<E> {
  9 
 10     private E[] data;//创建一个E类型的数组。
 11     private int front;//定义一个变量,表示队首指向的索引位置,指向队首所在的索引。
 12     private int tail;//定义一个变量,队列最后一个元素下一个位置,新元素入队存放的位置对应的索引。
 13     private int size;//队列里面有多少个元素。
 14 
 15     /**
 16      * 创建一个含参构造函数
 17      *
 18      * @param capacity 数据的容量大小,用户期望的循环队列的容量大小
 19      */
 20     public LoopQueue(int capacity) {
 21         // 创建一个E类型的数组data
 22         // 由于循环队列,需要浪费一个空间,所以容量大小是用户期望的容量大小加一。
 23         data = (E[]) new Object[capacity + 1];
 24         // 成员变量初始化大小
 25         front = 0;//指向队首所在的索引为0
 26         tail = 0;//队列最后一个元素下一个位置的索引为0
 27         size = 0;//循环队列的大小为0
 28     }
 29 
 30     /**
 31      * 创建一个无参的构造函数,初始化循环队列的容量为10
 32      */
 33     public LoopQueue() {
 34         // 初始化容量为10的循环队列
 35         this(10);
 36     }
 37 
 38     /**
 39      * 入队操作
 40      *
 41      * @param e
 42      */
 43     @Override
 44     public void enqueue(E e) {
 45         // 首先判断队列是否是满的。
 46         // 判断的标准就是队尾tail加一取余循环队列的长度即下一个tail的值等于队首front,就表示队列满了。
 47         // 取余操作,是让循环队列的整个索引循环起来,类比钟表循环。
 48         // 假如front是一点钟,tail是十二点钟,那么十二加一,取余十二就等于一,那么就表示该循环队列满了。
 49         // 因为循环队列要空出一个位置。
 50         if ((tail + 1) % data.length == front) {
 51             // 如果循环队列满了,进行循环队列扩容。扩容的大小是,此时循环队列的最多可以存放元素的个数乘以2
 52             // 此处,不使用data.length乘以二,因为data.length和循环队列最多可以盛放的元素个数之间有一个一的差距。
 53             resize(this.getCapacity() * 2);
 54         }
 55 
 56         // 此时,将要存放的元素存放到tail的位置上面。
 57         data[tail] = e;
 58         // 此时,因为是在循环队列里面,维护一下tail的位置。
 59         tail = (tail + 1) % data.length;
 60         // 维护size的大小
 61         size++;
 62     }
 63 
 64     /**
 65      * 循环队列进行扩容操作
 66      *
 67      * @param newCapacity
 68      * @return
 69      */
 70     private void resize(int newCapacity) {
 71         // 创建一个新的数组,将之前的元素放入到新的数组里面
 72         // 由于循环队列,需要浪费一个空间,所以容量大小是用户期望的容量大小加一。
 73         E[] newData = (E[]) new Object[newCapacity + 1];
 74 
 75         // 将之前的数组的所有元素,放入到新的数组里面
 76         for (int i = 0; i < size; i++) {
 77             // 将之前的数组的所有元素放入到新的数组的从零到size减一索引的位置上面。
 78             // 在之前的data数组里面,front队首元素有可能不是在零索引位置上面的,比如出队操作。
 79             // 此时,将data数组里面front队首元素放到新的数组里面的零索引的位置上面。
 80             // 此时newData[i]的位置不是对应data[i]的位置。
 81             // 因为newData[0]对应的就是data[front],那么newData[1]对应的就是data[front + 1],以此类推。
 82             // 所以说,newData[i]对应的是data[(i + front) % data.length]
 83             // data中的所有元素相对于newData中的所有元素索引值有一个(i + front)偏移的。
 84             // 由于整个队列是循环队列,所以队列要循环起来,(i + front)的值有可能会超过data的length长度,产生越界。
 85             // 所以可以进行取余数据长度操作。
 86             newData[i] = data[(i + front) % data.length];
 87         }
 88 
 89         // 将原来的数组data指向扩容以后的新数组newData
 90         data = newData;
 91         // 此时队首front变成了0
 92         front = 0;
 93         // 队尾tail变成了size,循环队列里面的元素个数不需要改变
 94         tail = size;
 95     }
 96 
 97     /**
 98      * 出队操作
 99      *
100      * @return
101      */
102     @Override
103     public E dequeue() {
104         // 首先,判断队列是否为空,如果为空,直接抛出异常
105         if (this.isEmpty()) {
106             throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
107         }
108 
109         // 否则,如果此时队列不为空,就进行出队操作
110         // 首先,对要出队的元素进行保存
111         E result = data[front];
112         // 将出队的元素的位置指向null。
113         data[front] = null;
114 
115         // 维护front,因为是循环队列
116         front = (front + 1) % data.length;
117 
118         // 维护size的大小,由于是出队,所以size的大小减一
119         size--;
120 
121         // 出队,可以进行扩容操作,节约资源。如果size大小等于容量的四分之一的时候,就缩容到之前的二分之一
122         // 并且缩容的值不等于0
123         if (size == this.getCapacity() / 4 && this.getCapacity() / 2 != 0) {
124             this.resize(this.getCapacity() / 2);
125         }
126 
127         // 返回出队的元素内容
128         return result;
129     }
130 
131     /**
132      * 查看循环队列的队首元素
133      *
134      * @return
135      */
136     @Override
137     public E getFront() {
138         // 首先,判断队列是否为空,如果为空,直接抛出异常
139         if (this.isEmpty()) {
140             throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
141         }
142         return data[front];
143     }
144 
145     /**
146      * 获取到循环队列的大小
147      *
148      * @return
149      */
150     @Override
151     public int getSize() {
152         // 由于size就是维护的循环队列的大小
153         return size;
154     }
155 
156     /**
157      * 判断循环队列是否为空
158      *
159      * @return
160      */
161     @Override
162     public boolean isEmpty() {
163         // 循环队列的队首front等于循环队列的队尾指向的下一个位置的tail相等的时候,即循环队列为空
164         return front == tail;
165     }
166 
167     /**
168      * 返回循环队列的容量大小,初始化的时候容量加一,此时获取到循环队列容量的时候,记得减一。
169      *
170      * @return
171      */
172     public int getCapacity() {
173         // 扩容的时候,data发生变化,那么扩容以后的data.length的长度就发生了变化
174         return data.length - 1;
175     }
176 
177     @Override
178     public String toString() {
179         // 封装数组遍历的内容
180         StringBuilder sb = new StringBuilder();
181         sb.append(String.format("LoopQueue : size = %d,capacity = %d\n", size, this.getCapacity()));
182         sb.append("front [");
183         // 切记,i的初始化值是front。
184         // i的最大值是不可以取到tail的值的。
185         // i递增是(i + 1) % data.length。因为是循环队列。
186         for (int i = front; i != tail; i = (i + 1) % data.length) {
187             sb.append(data[i]);
188             // 如果当前的索引不是最后一个元素的时候
189             if ((i + 1) % data.length != tail) {
190                 sb.append(", ");
191             }
192         }
193         sb.append(" ] tail ");
194         return sb.toString();
195     }
196 
197     public static void main(String[] args) {
198         LoopQueue<Integer> loopQueue = new LoopQueue<>();
199         // 入队操作
200         for (int i = 0; i < 20; i++) {
201             loopQueue.enqueue(i);
202             System.out.println(loopQueue.toString());
203         }
204 
205         System.out.println();
206         // 出队操作
207         loopQueue.dequeue();
208         System.out.println("循环队列出队操作: " + loopQueue);
209 
210         // 获取到队列的大小
211         int size = loopQueue.getSize();
212         System.out.println("获取到循环队列的大小: " + size);
213 
214         // 获取到队首的元素
215         Integer front = loopQueue.getFront();
216         System.out.println("获取到循环队列队首的元素: " + front);
217 
218         // 判断队列是否为空
219         System.out.println("判断循环队列是否为空: " + loopQueue.isEmpty());
220     }
221 
222 }

执行效果,如下所示:

5、数组队列和循环队列的比较,性能测试。

 1 package com.queue;
 2 
 3 import java.util.Random;
 4 
 5 /**
 6  *
 7  */
 8 public class Main {
 9 
10     /**
11      * 测试使用queue运行opCount个enqueue和dequeue操作所需要的时间,单位:秒
12      *
13      * @param queue
14      * @param opCount
15      * @return
16      */
17     public static double queuePerforms(Queue<Integer> queue, int opCount) {
18         // 开始时间
19         long startTime = System.nanoTime();
20 
21         Random random = new Random();
22         // 入队操作
23         for (int i = 0; i < opCount; i++) {
24             queue.enqueue(random.nextInt(Integer.MAX_VALUE));
25         }
26 
27         // 出队操作
28         for (int i = 0; i < opCount; i++) {
29             queue.dequeue();
30         }
31 
32         // 结束时间
33         long endTime = System.nanoTime();
34 
35         // 秒与纳秒之前差九位数
36         return (endTime - startTime) / 1000000000.0;
37     }
38 
39     public static void main(String[] args) {
40         int opCount = 1000000;// 一百万次
41 
42         // 数组队列的性能
43         // 影响数组队列性能的是出队操作,因为每一个元素都要进行前移操作
44         ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
45         double time1 = queuePerforms(arrayQueue, opCount);
46         System.out.println("ArrayQueue, time:  " + time1 + " s");
47 
48 
49         // 循环队列的性能
50         LoopQueue<Integer> loopQueue = new LoopQueue<>();
51         double time2 = queuePerforms(loopQueue, opCount);
52         System.out.println("LoopQueue, time: " + time2 + " s");
53     }
54 
55 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构之栈

    1、栈Stack,栈也是一种线性结构,相比数组,栈对应的操作是数组的子集。栈只能从一端添加元素,也只能从同一端取出元素,这一端称为栈顶。栈是一种先进后出的或者后...

    别先生
  • 数据结构之数组

    1、数据结构研究的是数据如何在计算机中进行组织和存储,使得我们可以高效的获取数据或者修改数据。

    别先生
  • BootstrapTable的列排序怎么搞

    先搞一个table,使用ajax将数据查询出来,然后可以在所有列都加上排序。满足自己的需求。

    别先生
  • 大数据分析行业吸引指数:金融业最吸引人,电信行业惨遭排尾

    职业社交平台领英针对2014年全年中国市场的互联网行业人才及传统行业人才迁移情况进行了大数据分析推出行业人才吸引力指数。报告指出,目前行业趋势中,金融业对于人才...

    华章科技
  • [编程经验] Pandas中比较好用的几个方法

    话说我现在好久不做深度学习的东西了,做了一段时间是的NLP,以为可以去尝试各种高大上的算法,然而现在还并没有,反而觉得更像是做数据挖掘的。。平时遇到的比较多的问...

    用户1622570
  • 2.5.4、Google Analytics高级应用——API的使用

    GA非常强大,但是免费版的有诸多的限制,如:GA里面最多能导出的记录是5000,如果要做细致,个性化的分析,无疑是需要用到API,免费版GA通过API最多可以拿...

    GA小站
  • py-ops面向编程的关键字测试框架

    这是一款基于pytest封装,同时支持关键字和BDD,测试数据分离,面向编程,轻量级的,对上层自动化应用友好的基础测试框架。

    上帝De助手
  • vue 随记(2):轮子是如何造成的

    为了预测恒纪元和乱纪元,故事里的冯诺依曼设计了人列计算机,不需要三千万个数学家。只需要三千万忠实的士兵,每个个体订阅相关单元的变化,忠实地反映状态即可。

    一粒小麦
  • GCC编译过程记 原

          对于编程工作者来说,GCC是一个熟悉的名字,它的全称是“GNU Compiler Collection”。GCC是一组编译器集合,目前其支持C、C+...

    珲少
  • 一次排查线上接口偶发异常耗时引起的思考!

    这要从线上的一个接口偶发异常耗时说起,事情往往不是你想象的样子,尤其是在排查问题的时候,切忌有先入为主的的某些判断。

    WindWant

扫码关注云+社区

领取腾讯云代金券