05-图解数据结构之队列--Queue

mac2022-06-30 136

零、前言

栈是一种线性的数据结构特性：尾部添加，头部取出即先进先出FIFO 操作：enqueue入队 dequeue出队 getFront查看队首元素

队列.png

一、队列接口

/** * 作者：张风捷特烈 * 时间：2018/8/17 0017:15:57 * 邮箱：1981462002@qq.com * 说明：队列接口 */ public interface IQueue<T> { /** * 入队 * @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 ArrayGroupQueue<E> implements IQueue<E> { /** * 成员变量 */ private ArrayGroup<E> array; public ArrayGroupQueue(int capacity) { this.array = new ArrayGroup<>(capacity); } public ArrayGroupQueue() { this.array = new ArrayGroup<>(); } @Override public void enqueue(E el) { array.addLast(el); } @Override public E dequeue() { return array.removeFirst(); } @Override public E getFront() { return array.get(0); } @Override public int getSize() { return array.size(); } @Override public boolean isEmpty() { return array.isEmpty(); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("IQueue ："); res.append("front [ "); for (int i = 0; i < array.size(); i++) { res.append(array.get(i)); if (i != array.size() - 1) { res.append(", "); } } res.append("] tail"); return res.toString(); } }

数组普通队列测试

/** * 数组队列测试 */ private static void arrayQueueTest() { ArrayGroupQueue<Integer> queue = new ArrayGroupQueue<>(); for (int i = 0; i < 5; i++) { queue.enqueue(i); System.out.println(queue); } queue.dequeue(); System.out.println(queue); //IQueue ：front [ 0] tail //IQueue ：front [ 0, 1] tail //IQueue ：front [ 0, 1, 2] tail //IQueue ：front [ 0, 1, 2, 3] tail //IQueue ：front [ 0, 1, 2, 3, 4] tail //IQueue ：front [ 1, 2, 3, 4] tail }

三、循环队列

基于数组实现的队列在队首取出是会使得整队移动，而使时间复杂度为O(n) 可以使用循环队，基于队首队尾两个标示来固定队列，从而使得时间复杂度为O(1) 循环队列特点：为空时，队尾标示==队首标示,新加元素时，队尾表识后移，队列满：(队尾标示+1)%数组长度==队首标示循环队列会使队首前一个位置不可用。

循环队列.png 循环队列循环机制.png /** * 作者：张风捷特烈 * 时间：2018/8/17 0017:16:03 * 邮箱：1981462002@qq.com * 说明：数组实现循环队列 */ public class ArrayLoopQueue<T> implements IQueue<T> { /** * 队列数据 */ private T[] data; /** * 队首标示 */ private int front; /** * 队尾标示 */ private int tail; /** * 元素个数 */ private int size; /** * 无参构造：默认10个容量 */ public ArrayLoopQueue() { this(11); } /** * 一参构造 * * @param capacity 队列容量 */ public ArrayLoopQueue(int capacity) { // 因为会有一个浪费，所以+1 data = (T[]) new Object[capacity + 1]; front = 0; tail = 0; size = 0; } @Override public void enqueue(T el) { if (isFull()) { grow(getCapacity() * 2); } data[tail] = el; //插入数据时对尾标示进行操作 tail = (tail + 1) % data.length; size++; } @Override public T dequeue() { if (isEmpty()) { throw new IllegalArgumentException("Cannot dequeue from an empty queue"); } T ret = data[front]; data[front] = null; //插入数据时对首标示进行操作 front = (front + 1) % data.length; size--; if (size == getCapacity() / 4 && getCapacity() / 2 != 0) { grow(getCapacity() / 2); } return ret; } @Override public T getFront() { if (isEmpty()) { throw new IllegalArgumentException("Cannot dequeue from an empty queue"); } return data[front]; } /** * 重新确定容量 * @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 + front) % data.length]; } data = newData; front = 0; tail = size; } /** * 获取容量 * @return 容量 */ public int getCapacity() { return data.length - 1; } /** * 队列元素个数 * @return 元素个数 */ @Override public int getSize() { return size; } /** * 是否为空 * @return 是否为空 */ @Override public boolean isEmpty() { return front == tail; } /** * 队列是否满了 * @return 队列是否满了 */ public boolean isFull() { // tail的下一个位置等于front时 return (tail + 1) % data.length == front; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("ArrayLoopQueue: size = %d, capacity = %d\n", size, getCapacity())); res.append("front ["); for (int i = front; i != tail; i = (i + 1) % data.length) { res.append(data[i]); if ((i + 1) % data.length != tail) // 最后一个元素不要加， res.append(", "); } res.append("] tail"); return res.toString(); } }

测试：

/** * 循环队列测试 */ private static void LoopQueueTest() { ArrayLoopQueue<Integer> queue = new ArrayLoopQueue<>(8); for (int i = 0; i < 8; i++) { queue.enqueue(i); } System.out.println(queue); //ArrayLoopQueue: size = 8, capacity = 8 //front [0, 1, 2, 3, 4, 5, 6, 7] tail queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.enqueue(10); System.out.println(queue.getFront());//4 System.out.println(queue); //ArrayLoopQueue: size = 5, capacity = 8 //front [4, 5, 6, 7, 10] tail }

四、链表式集合实现队列

链表和队列可谓天然配，链表的头删除，头获取都是O(1),但尾添加是O(n),但可以维护首位标识，使尾加也为O(1)

/** * 作者：张风捷特烈 * 时间：2018/8/17 0017:22:50 * 邮箱：1981462002@qq.com * 说明：单链表实现队列 */ public class SingleLinkedQueue<T> implements IQueue<T> { /** * 头节点 */ 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把新Node挂载上来。 tail.next = new Node(null, el); // tail后挪 tail = tail.next; } size++; } @Override public T dequeue() { if (isEmpty()) throw new IllegalArgumentException("Cannot dequeue from an empty queue."); Node targetNode = head; head = head.next; // head后移 targetNode.next = null; // 元素置空 if (head == null) {// 如果头结点为空 tail = null; } size--; return targetNode.el; } @Override public T getFront() { if (isEmpty()) throw new IllegalArgumentException("IQueue is empty."); return head.el; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("IQueue: front "); Node cur = head; while (cur != null) { res.append(cur + "->"); cur = cur.next; } res.append("NULL tail"); return res.toString(); } private class Node { public T el;//改节点上的元素 public Node next; //下一节点 /** * 两参构造 * * @param next //下一节点 * @param el 生成节点的元素值 */ public Node(Node next, T el) { this.el = el; this.next = next; } @Override public String toString() { return el.toString(); } } }

四、时间测试

数组普通队列：ArrayGroupQueue测试

方法\数量复杂度1000次10000次10W次100W次1000次enqueueO(1)0.0006秒0.0022秒0.01571秒0.06668秒1.1375秒dequeueO(n)0.0111秒0.2707秒18.7684秒------getFrontO(1)----------

数组环形队列：ArrayLoopQueue测试

方法\数量复杂度1000次10000次10W次100W次1000次enqueueO(1)0.0004秒0.0019秒0.01775秒0.05414秒0.6896秒dequeueO(1)0.0005秒0.0021秒0.0091秒0.0360秒0.3327秒getFrontO(1)----------

链表队列：SingleLinkedStack测试

方法\数量复杂度1000次10000次10W次100W次1000次enqueueO(1)0.0011秒0.0031秒0.0099秒0.4881秒3.1186秒dequeueO(1)0.0002秒0.0013秒0.0046秒0.0221秒0.1388秒getFrontO(1)----------

后记、

1.声明：

[1]本文由张风捷特烈原创,各图均由本人亲自所画，转载请注明 [2]欢迎广大编程爱好者共同交流 [3]个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正 [4]你的喜欢与支持将是我最大的动力

2.连接传送门：

更多数据结构知识欢迎访问:图解数据结构项目源码均在我的https://github.com/toly1994328/DS：欢迎star 张风捷特烈个人网站，编程笔记请访问：http://www.toly1994.com

3.联系我

QQ:1981462002 邮箱：1981462002@qq.com 微信：zdl1994328

4.欢迎关注我的微信公众号，最新精彩文章，及时送达：

公众号.jpg

转载于:https://www.cnblogs.com/toly-top/p/9781866.html

相关资源：图解数据结构（使用Python）——队列

最新回复(0)