零、前言
1.现实世界里我们更多讲究的是
2.使用队列结构能很好的模拟和解决类似生活中的事，比如消息的发送用队列维护就是非常恰当的 3.队列就像去动物园买票，先处理队列的头部，有新的人来了就后面排着去，慢慢等 4.还有一种很有意思的队列是循环队列，它是由于数组对头部操作的困难性，从而转变一种思路，让数组也能很好的实现队列结构，后面会仔细分析一下 5.本例操作演示源码：先来后到,先排队先买票，这样才有秩序，毕竟我们没有计算机那么有耐心
1.留图镇楼：队列的最终实现的操作效果:
数组实现普通队列：
蓝色区域是数组看见：初始化四个空间，不够再扩容，空闲太多再缩容
链表实现普通队列：
2.队列结构的简介：
队列是一种线性的数据结构 特性：尾部添加，头部取出 即先进先出FIFO 操作：enqueue入队 dequeue出队 getFront查看队首元素复制代码
一、队列接口
兵马未动，粮草先行，有接口好办事。
/** * 作者：张风捷特烈 * 时间：2018/8/17 0017:15:57 * 邮箱：1981462002@qq.com * 说明：队列接口 */public interface IQueue{ /** * 入队 * @param el 元素 */ void enqueue(T el); /** * 出队 * @return 元素 */ T dequeue(); /** * 获取队首元素 * @return 队首元素 */ T getFront(); /** * 获取队列元素个数 * @return 元素个数 */ int getSize(); /** * 是否为空 * @return 是否为空 */ boolean isEmpty();}复制代码
二、普通队列的数组实现
普通队列的数组实现----性能非常差,后面用数组实现循环队列来优化
为什么会很差，因为尾添加和头删除，总有一个会让所有的人挪一挪，后面会用数组实现循环队列来优化
/** * 作者：张风捷特烈 * 时间：2018/8/17 0017:15:57 * 邮箱：1981462002@qq.com * 说明：普通队列的数组实现----性能非常差,后面用数组实现循环队列来优化 */public class ArrayChartQueueimplements IQueue { private ArrayChart array;//成员变量 public ArrayChartQueue(int capacity) { this.array = new ArrayChart<>(capacity); } public ArrayChartQueue() { this.array = new ArrayChart<>(); } @Override public void enqueue(E el) { array.add(el); } @Override public E dequeue() { return array.remove(0); } @Override public E front() { return array.get(0); } @Override public int size() { return array.size(); } @Override public boolean isEmpty() { return array.isEmpty(); }}复制代码
2.数组普通队列的插入演示：
由于是基于数组来实现，所以一切的操作也是基于数组
初始四个大小的数组，就像招待处预留四把椅子，然后等椅子坐满了，再来加椅子
3.数组普通队列的查看首元演示：
4.数组普通队列的移除演示：
数组表结构移除头部...万恶之源，千万不要用，此处仅演示! 此处仅演示!此处仅演示!!数组表结构移除头部...万恶之源，千万不要用，此处仅演示! 此处仅演示!此处仅演示!!
三、循环队列
基于数组实现的队列在队首取出时会使得整队移动，效率会很低
但是壮哉我大数组,岂会连个小小的队列都搞不定，以后还哪还有脸立足王座...于是循环队列出现了 说起循环大家脑子里都是一个圈来回转,循环小数表示不服... 只要有周期性就是循环，想成一个圈就狭隘了
1.循环队列实现的思路：
不就是想要知道队尾和队首是那个嘛，我标出来，维护一下给你不就行了吗 注意：这里的优势在于维护了队尾和队首的标示，插入尾和删除头都是定点，而且数组整体不移动,而是标示在动新加元素时，队尾表识后移，不够就扩容。删除头时队首标示 循环队列特点：为空时，`队尾标示==队首标示`,队列满：`(队尾标示+1)%数组长度==队首标示` 循环队列会使队首前一个位置不可用。复制代码
/** * 作者：张风捷特烈 * 时间：2018/8/17 0017:16:03 * 邮箱：1981462002@qq.com * 说明：数组实现循环队列 */public class ArrayLoopQueueimplements IQueue { private T[] data;// 队列数据 private int head;//队首标示 private int tail;//队尾标示 private int size;//元素个数 public ArrayLoopQueue() {//无参构造：默认8个容量 this(8); } public ArrayLoopQueue(int capacity) { // 因为会有一个浪费,所以+1 data = (T[]) new Object[capacity + 1]; head = 0; tail = 0; size = 0; } @Override public void enqueue(T el) { if (isFull()) {//加入时满了---扩容 grow(capacity() * 2); } data[tail] = el;//在队尾插入 //插入数据时对尾标示进行维护----- tail = (tail + 1) % data.length; size++; } @Override public T dequeue() { if (isEmpty()) { throw new IllegalArgumentException("MakeSure it's not an empty } T ret = data[head]; data[head] = null;//让队首移除 //队首移除时对首标示进行维护----- head = (head + 1) % data.length; size--; //闲置太多---缩容 if (size == capacity() / 4 && capacity() / 2 != 0 && size > 4) { grow(capacity() / 2); } return ret; } @Override public T front() { if (isEmpty()) { throw new IllegalArgumentException("MakeSure it's not an empty } return data[head]; } /** * 扩容/缩容 * * @param newCapacity 新的容量 */ private void grow(int newCapacity) { T[] newData = (T[]) new Object[newCapacity + 1]; for (int i = 0; i < size; i++) { // 此时在newData中队首对齐回来，data中就得有一个front的偏移量 newData[i] = data[(i + head) % data.length]; } data = newData; head = 0; tail = size; } /** * 获取容量 * * @return 容量 */ public int capacity() { return data.length - 1; } /** * 队列元素个数 * * @return 元素个数 */ @Override public int size() { return size; } /** * 是否为空 * * @return 是否为空 */ @Override public boolean isEmpty() { return head == tail; } /** * 队列是否满了 * * @return 队列是否满了 */ private boolean isFull() { // tail的下一个位置等于head时 return (tail + 1) % data.length == head; }}复制代码
四、单链表式实现队列结构
链表和队列可谓天然配，链表的头删除，头获取很快,但尾添加要获取尾部，需要遍历一次，不好
但可以维护首位标识，使队尾也容易获取。(当然你也可以用双链表...直接批件衣服，改都不用改) 注释的很清楚了，看着代码顺一下，或debug走一波，我就不赘述了
/** * 作者：张风捷特烈 * 时间：2018/8/17 0017:22:50 * 邮箱：1981462002@qq.com * 说明：单链表实现队列 */public class SingleLinkedQueueimplements IQueue { private Node head;//头节点 private Node tail;//尾节点 private int size;//元素个数 public SingleLinkedQueue() { head = null; tail = null; size = 0; } @Override public void enqueue(T el) {//入队 // 如果队尾为空，说明队列是空的。因为tail一直指向最后一个非空节点。 if (tail == null) { tail = new Node(null, el);//初始化 head = tail; } else { tail.next = new Node(null, el); // 新来的排到后面去 tail = tail.next; //更新队尾 } size++; } @Override public T dequeue() {//出队 if (isEmpty()) throw new IllegalArgumentException("MakeSure it's not an empty queue"); Node targetNode = head;//我是老大 head = head.next; // 我是老二，但我要篡位了...以后哥就是老大 targetNode.next = null; //前任老大走了.... if (head == null) {// 如果头结点为空 tail = null; } size--; return targetNode.el; } @Override public T front() { if (isEmpty()) throw new IllegalArgumentException("MakeSure it's not an empty queue"); return head.el; } @Override public int size() { return size; } @Override public boolean isEmpty() { return size == 0; } private class Node { private T el;//改节点上的元素 private Node next; //下一节点 /** * 两参构造 * * @param next //下一节点 * @param el 生成节点的元素值 */ private Node(Node next, T el) { this.el = el; this.next = next; } }}复制代码
五、小结
1.数组普通队列：ArrayChartQueue测试
| 方法\数量 | 1000 | 次10000次 | 10W次 | 100W次 | 1000次 |
|---|---|---|---|---|---|
| enqueue | 0.0006秒 | 0.0022秒 | 0.01571秒 | 0.06668秒 | 1.1375秒 |
| dequeue | 0.0111秒 | 0.2707秒 | 18.7684秒 | ---- | -- |
2.数组环形队列：ArrayLoopQueue测试
| 方法\数量 | 1000 | 次10000次 | 10W次 | 100W次 | 1000次 |
|---|---|---|---|---|---|
| enqueue | 0.0004秒 | 0.0019秒 | 0.01775秒 | 0.05414秒 | 0.6896秒 |
| dequeu | 0.0005秒 | 0.0021秒 | 0.0091秒 | 0.0360秒 | 0.3327秒 |
3.链表队列：SingleLinkedStack测试
| 方法\数量 | 1000 | 次10000次 | 10W次 | 100W次 | 1000次 |
|---|---|---|---|---|---|
| enqueue | 0.0011秒 | 0.0031秒 | 0.0099秒 | 0.4881秒 | 3.1186秒 |
| dequeue | 0.0002秒 | 0.0013秒 | 0.0046秒 | 0.0221秒 | 0.1388秒 |
可见循环队列还是蛮好的，壮哉，我大数组!
数组普通队列,就认识一下吧...不要用它。 数组环形队列和链表队列的比较也就相当于数组和链表的比较
本系列后续更新链接合集：(动态更新)
- 更多数据结构---以后再说吧
后记：捷文规范
2.本文成长记录及勘误表
| 日期 | 备注 | |
|---|---|---|
| 2018-11-24 |
3.更多关于我
| 笔名 | 微信 | 爱好 | |
|---|---|---|---|
| 张风捷特烈 | 1981462002 | zdl1994328 | 语言 |
4.声明
1----本文由张风捷特烈原创,转载请注明
2----欢迎广大编程爱好者共同交流 3----个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正 4----看到这里，我在此感谢你的喜欢与支持