数据结构基础：使用数组和链表实现队列、循环队列

数据结构基础：使用数组和链表实现队列、循环队列

其他

如果大家想再次学习一下数据结构，推荐一个数据可视化的数据结构学习网站：​​​和链表（链式存储）。队列的实现也可以是数组或链表。

0、队列通用接口

出于通用性的考量，我们抽象一个Queue接口，其中包括入队、出队、获取队列size操作；并对入队数据进行泛型化处理。

package com.saint.base.datastructure.queue;/** * 队列接口 * * @author Saint * @version 1.0 * @createTime 2021-09-04 20:04 */public interface Queue { /** * 获取队列size */ int getSize(); /** * 入队操作 */ void enqueue(E e); /** * 出队操作 */ E dequeue();}

1、使用数组实现队列

数组结构特点：

随机访问时间复杂度O(1) – 快速查询，随机插入时间复杂度O(n/2)数据在内存中连续存储，空间预分配。

大家可以在如下网址进行入队和出队的演示，而我代码的版本在dequeue操作之后会对数据进行移动，使数据对齐到数据开头。网址中的版本减少了dequeue移动数据的操作，但带来了存储空间的浪费。

package com.saint.base.datastructure.queue;/** * 基于数组实现的队列，泛型数据需要可比较 * * @author Saint * @version 1.0 * @createTime 2021-09-04 14:20 */public class ArrayQueue> implements Queue { /** * 存放数据的数组 */ Object[] items; /** * 元素个数 */ int size; /** * 无参构造方法 -- 其中调用有参构造方法 */ public ArrayQueue() { this(10); } /** * 有参构造方法 * * @param capacity 初始容量 */ public ArrayQueue(int capacity) { items = new Object[capacity]; this.size = 0; } @Override public void enqueue(E e) { // 判断是否需要扩容 if (size == items.length) { resize(2 * items.length); } // 往数组尾部中添加数据 items[size] = e; size++; } /** * 数组扩容/缩容操作 * * @param newCapacity 新的数组容量 */ public void resize(int newCapacity) { Object[] newItems = new Object[newCapacity]; // 数据迁移 for (int i = 0; i < size; i++) { newItems[i] = items[i]; } items = newItems; } @Override public E dequeue() { if (getCapacity() < 1) { throw new RuntimeException("Queue is empty"); } E e = (E) items[0]; // 删除数组头部数据， 时间复杂度O(n) for (int i = 0; i < size - 1; i++) { items[i] = items[i + 1]; } items[size - 1] = null; size--; // 缩容操作 if (size == getCapacity() / 4 && getCapacity() > 1) { resize(getCapacity() / 2); } return e; } /** * 获取元素个数 * * @return */ @Override public int getSize() { return size; } /** * 获取数组当前容量 * * @return */ public int getCapacity() { return items.length; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("ArrayQueue: size =%d, capacity = %d.\n", size, getCapacity())); res.append("["); for (int i = 0; i < size; i++) { res.append(items[i]); if (i != size - 1) { res.append(","); } } res.append("] tail"); return res.toString(); }}

2、使用数组实现循环队列

特点：

使用数组实现的普通队列，每次出队之后都要调整数组中的数据位置。而循环队列减少了这个O(n)时间复杂的操作。所以循环队列出队的效率比一般的队列要高很多。

package com.saint.base.datastructure.queue;/** * 基于数组实现的循环队列 * * @author Saint * @version 1.0 * @createTime 2021-09-04 14:19 */public class ArrayLoopQueue> implements Queue { /** * 存放队列数据的地方 */ Object[] items; /** * 队列元素个数 */ int size; /** * 队首指针 */ int takeIndex; /** * 队尾指针 */ int putIndex; public ArrayLoopQueue() { this(10); } public ArrayLoopQueue(int capacity) { items = new Object[capacity]; size = 0; putIndex = 0; takeIndex = 0; } @Override public void enqueue(E e) { // 判断是否需要扩容 ，队尾指针 + 1 和 数组容量取模 if ((putIndex + 1) % items.length == takeIndex) { resize(2 * items.length); } items[putIndex] = e; putIndex++; size++; } @Override public E dequeue() { if (takeIndex == putIndex) { throw new RuntimeException("Queue is empty"); } E e = (E) items[takeIndex]; items[takeIndex] = null; takeIndex = (takeIndex + 1) % items.length; size--; if (size == getCapacity() / 4 && getCapacity() / 2 > 0) { resize(getCapacity() / 2); } return e; } /** * 数组扩容/缩容操作 * * @param newCapacity 新的数组容量 */ public void resize(int newCapacity) { Object[] newItems = new Object[newCapacity]; // 数据迁移 for (int i = 0; i < size; i++) { // 这里取数据的时候要从takeIndex开始取 newItems[i] = items[(i + takeIndex) % items.length]; } items = newItems; // 数据迁移完，要对takeIndex和putIndex进行重置 takeIndex = 0; putIndex = size; } @Override public int getSize() { return size; } /** * 获取数组当前容量 * * @return */ public int getCapacity() { return items.length; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("ArrayLoopQueue: size =%d, capacity = %d, takeIndex = %d, putIndex = %d.\n", size, getCapacity(), takeIndex, putIndex)); res.append("head ["); for (int i = takeIndex; i != putIndex; i = (i + 1) % items.length) { res.append(items[i]); if ((i + 1) % items.length != putIndex) { res.append(" ,"); } } res.append("] tail"); return res.toString(); }}

3、使用链表实现队列

链表特点：

随机访问时间复杂度O(n) – 丧失随机访问的能力、随机插入时间复杂度O(1)。不需要空间预分配，但会额外占用内存空间，用于存储next指针。

Node节点类：

package com.saint.base.datastructure;/** * 链表节点类 * * @author Saint * @version 1.0 * @createTime 2021-09-04 21:21 */public class Node { /** * 存放数据 */ public E value; /** * 指向下一个node节点 */ public Node next; /** * 构造器 * * @param e * @param next */ public Node(E e, Node next) { this.value = e; this.next = next; } /** * 带一个参数的构造器 * * @param e */ public Node(E e) { this(e, null); } /** * 默认构造器 */ public Node() { this(null, null); } @Override public String toString() { return value.toString(); }}

package com.saint.base.datastructure.queue;import com.saint.base.datastructure.Node;/** * @author Saint * @version 1.0 * @createTime 2021-09-04 14:19 */public class LinkedQueue> implements Queue { /** * 链表头部 */ Node head; /** * 链表尾部 */ Node tail; /** * 数据元素个数 */ int size; public LinkedQueue() { head = null; tail = null; size = 0; } @Override public void enqueue(E e) { // 如果链表为空，则创建一个新节点 if (tail == null) { tail = new Node(e); head = tail; } else { // 新建一个Node节点，并将链表尾节点的next指向新建的Node节点。 tail.next = new Node(e); // tail指针后移 tail = tail.next; } size++; } @Override public E dequeue() { if (head == null) { throw new RuntimeException("Queue is empty!"); } Node cur = head; head = head.next; cur.next = null; if (head == null) { tail = null; } size--; return cur.value; } @Override public int getSize() { return size; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("LinkedQueue: front "); Node cur = head; while (cur != null) { res.append(cur.value + "--> "); cur = cur.next; } res.append(" NULL tail"); return res.toString(); }}

4、测试类

package com.saint.base.datastructure.queue;/** * @author Saint * @version 1.0 * @createTime 2021-09-04 20:27 */public class QueueTest { public static void main(String[] args) { System.out.println("------------------ArrayQueue-----------------------"); ArrayQueue queue = new ArrayQueue<>(); for (int i = 0; i < 10; i++) { queue.enqueue(i); System.out.println(queue); if (i % 3 == 0) { queue.dequeue(); System.out.println("出队 ： " + queue); } } System.out.println("-----------------------------------------"); System.out.println("------------------ArrayLoopQueue-----------------------"); ArrayLoopQueue loopQueue = new ArrayLoopQueue<>(); for (int i = 0; i < 10; i++) { loopQueue.enqueue(i); System.out.println(loopQueue); if (i % 3 == 0) { loopQueue.dequeue(); System.out.println("出队 ： " + loopQueue); } } System.out.println("-----------------------------------------"); System.out.println("------------------ArrayLoopQueue-----------------------"); LinkedQueue linkedQueue = new LinkedQueue<>(); for (int i = 0; i < 10; i++) { linkedQueue.enqueue(i); System.out.println(linkedQueue); if (i % 3 == 0) { linkedQueue.dequeue(); System.out.println("出队 ： " + linkedQueue); } } }}

控制台输出：

------------------ArrayQueue-----------------------ArrayQueue: size =1, capacity = 10.[0] tail出队 ： ArrayQueue: size =0, capacity = 10.[] tailArrayQueue: size =1, capacity = 10.[1] tailArrayQueue: size =2, capacity = 10.[1,2] tailArrayQueue: size =3, capacity = 10.[1,2,3] tail出队 ： ArrayQueue: size =2, capacity = 5.[2,3] tailArrayQueue: size =3, capacity = 5.[2,3,4] tailArrayQueue: size =4, capacity = 5.[2,3,4,5] tailArrayQueue: size =5, capacity = 5.[2,3,4,5,6] tail出队 ： ArrayQueue: size =4, capacity = 5.[3,4,5,6] tailArrayQueue: size =5, capacity = 5.[3,4,5,6,7] tailArrayQueue: size =6, capacity = 10.[3,4,5,6,7,8] tailArrayQueue: size =7, capacity = 10.[3,4,5,6,7,8,9] tail出队 ： ArrayQueue: size =6, capacity = 10.[4,5,6,7,8,9] tail-----------------------------------------------------------ArrayLoopQueue-----------------------ArrayLoopQueue: size =1, capacity = 10, takeIndex = 0, putIndex = 1.head [0] tail出队 ： ArrayLoopQueue: size =0, capacity = 10, takeIndex = 1, putIndex = 1.head [] tailArrayLoopQueue: size =1, capacity = 10, takeIndex = 1, putIndex = 2.head [1] tailArrayLoopQueue: size =2, capacity = 10, takeIndex = 1, putIndex = 3.head [1 ,2] tailArrayLoopQueue: size =3, capacity = 10, takeIndex = 1, putIndex = 4.head [1 ,2 ,3] tail出队 ： ArrayLoopQueue: size =2, capacity = 5, takeIndex = 0, putIndex = 2.head [2 ,3] tailArrayLoopQueue: size =3, capacity = 5, takeIndex = 0, putIndex = 3.head [2 ,3 ,4] tailArrayLoopQueue: size =4, capacity = 5, takeIndex = 0, putIndex = 4.head [2 ,3 ,4 ,5] tailArrayLoopQueue: size =5, capacity = 10, takeIndex = 0, putIndex = 5.head [2 ,3 ,4 ,5 ,6] tail出队 ： ArrayLoopQueue: size =4, capacity = 10, takeIndex = 1, putIndex = 5.head [3 ,4 ,5 ,6] tailArrayLoopQueue: size =5, capacity = 10, takeIndex = 1, putIndex = 6.head [3 ,4 ,5 ,6 ,7] tailArrayLoopQueue: size =6, capacity = 10, takeIndex = 1, putIndex = 7.head [3 ,4 ,5 ,6 ,7 ,8] tailArrayLoopQueue: size =7, capacity = 10, takeIndex = 1, putIndex = 8.head [3 ,4 ,5 ,6 ,7 ,8 ,9] tail出队 ： ArrayLoopQueue: size =6, capacity = 10, takeIndex = 2, putIndex = 8.head [4 ,5 ,6 ,7 ,8 ,9] tail-----------------------------------------------------------ArrayLoopQueue-----------------------LinkedQueue: front 0--> NULL tail出队 ： LinkedQueue: front NULL tailLinkedQueue: front 1--> NULL tailLinkedQueue: front 1--> 2--> NULL tailLinkedQueue: front 1--> 2--> 3--> NULL tail出队 ： LinkedQueue: front 2--> 3--> NULL tailLinkedQueue: front 2--> 3--> 4--> NULL tailLinkedQueue: front 2--> 3--> 4--> 5--> NULL tailLinkedQueue: front 2--> 3--> 4--> 5--> 6--> NULL tail出队 ： LinkedQueue: front 3--> 4--> 5--> 6--> NULL tailLinkedQueue: front 3--> 4--> 5--> 6--> 7--> NULL tailLinkedQueue: front 3--> 4--> 5--> 6--> 7--> 8--> NULL tailLinkedQueue: front 3--> 4--> 5--> 6--> 7--> 8--> 9--> NULL tail出队 ： LinkedQueue: front 4--> 5--> 6--> 7--> 8--> 9-->

三、数组和链表的区别

数组最好用于索引有语意的情况。 最大的优点是支持快速查询。链表不适合用于索引有语意的情况。 最大的优点是动态。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。