前言
队列（queue）是一种线性数据结构，队列中的元素只能先入先出（First In First Out，简称 FIFO）。队列和实际生活中的排队相对应，是一种和生活息息相关的数据结构，在很多系统中都会有队列设计思想的体现。
1.概念
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
2. 存储原理
队列这种数据结构既可以用数组来实现，也可以用链表来实现
2.1 数组实现
用数组实现的队列叫作顺序队列
2.2 链表实现
用链表实现的队列叫作链式队列
3. 操作
3.1 数组实现
3.1.1 定义队列类
public class ArrayQueue {//私有化数组，禁止外部直接访问，限制对数组的操作只能通过，提供的入队，出对操作实现private Object[] nums; // 数组// head表示队头下标，tail表示队尾下标int head = 0;int tail = 0;// 申请一个大小为capacity的数组public ArrayQueue(int size) {nums = new Object[size];}
}
3.1.2 入队
/*** @Description: 入队操作* @Author: wanlong* @Date: 2023/5/22 19:45* @param element:* @return boolean**/
public boolean enQueue(Object element){if (tail==nums.length){//队列满了，这里直接报错，后期可以优化扩容数组，保存更多元素return false;}nums[tail]=element;tail++;return true;
}
3.1.3 出队
/*** @Description:出队操作* @Author: wanlong* @Date: 2023/5/22 19:52* @return java.lang.Object**/
public Object deQueue(){if (head==tail){return null;}Object element = nums[head];head++;return element;
}
3.1.4 测试类
package org.wanlong.queue;import org.junit.BeforeClass;
import org.junit.Test;/*** @author wanlong* @version 1.0* @description: 测试队列* @date 2023/5/22 19:55*/
public class Client {static ArrayQueue arrayQueue = new ArrayQueue(10);@BeforeClasspublic static void init() {//入队三个元素arrayQueue.enQueue(1);arrayQueue.enQueue(2);arrayQueue.enQueue("我是队尾");}@Testpublic void testEnQueue() {arrayQueue.enQueue(1);arrayQueue.enQueue(2);}@Testpublic void testDequeue() {Object o = arrayQueue.deQueue();System.out.println("第一个出队元素为:" + o);Object o2 = arrayQueue.deQueue();System.out.println("第二个出队元素为" + o2);}
}3.1.5 运行结果
第一个出队元素为:1
第二个出队元素为2
3.2 链表实现
3.2.1 定义节点
package org.wanlong.queue;/*** @author wanlong* @version 1.0* @description: 定义链表节点* @date 2023/5/22 20:05*/
public class Node {Object value;Node next;public Node(Object value) {this.value = value;}
}
3.2.2 定义链表实现队列类
package org.wanlong.queue;/*** @author wanlong* @version 1.0* @description:* @date 2023/5/22 20:05*/
public class LinkedQueue {Node head;Node tail;int size;/*** @param element:* @return void* @Description:入队操作* @Author: wanlong* @Date: 2023/5/22 20:08**/public void enQueue(Node element) {if (tail == null) {head = element;tail = element;} else {tail.next = element;//指针后移tail = element;}//元素个数加一size++;}/*** @return java.lang.Object* @Description:出队操作* @Author: wanlong* @Date: 2023/5/22 20:08**/public Object deQueue() {if (head == null) {return null;}Node h = head;//将拉取的节点的下一个节点变成新的表头head = head.next;//把旧的表头的下一个节点指向设置为null，让gc回收h.next = null;if (head == null)tail = null;//元素个数减一size--;return h.value;}
}3.2.3 定义测试类
@Test
public void testLinkedListEnqueue(){LinkedQueue linkedQueue = new LinkedQueue();linkedQueue.enQueue(new Node("我"));linkedQueue.enQueue(new Node("是"));linkedQueue.enQueue(new Node("呆"));linkedQueue.enQueue(new Node("子"));Object o1 = linkedQueue.deQueue();System.out.println("第一个出队元素："+o1);Object o2 = linkedQueue.deQueue();System.out.println("第二个出队元素："+o2);
}
3.2.4 运行结果
第一个出队元素：我
第二个出队元素：是
4. 时间复杂度
入队和出队都是O(1)
5. 应用
- 资源池
- 消息队列
- 命令队列
以上，本人菜鸟一枚，如有错误，请不吝指正
