湛江专业自助建站详情,资源优化排名网站,成都网络公司最新招聘,学校网站空间建设情况作者 | 王磊来源 | Java中文社群#xff08;ID#xff1a;javacn666#xff09;转载请联系授权#xff08;微信ID#xff1a;GG_Stone#xff09;本文已收录至我的 Github《算法图解》系列#xff1a;https://github.com/vipstone/algorithm前面我们介绍了栈#xff08… 作者 | 王磊来源 | Java中文社群IDjavacn666转载请联系授权微信IDGG_Stone本文已收录至我的 Github《算法图解》系列https://github.com/vipstone/algorithm前面我们介绍了栈Stack队列和栈是比较像的一种数据结构。我们可以想象有很多辆汽车正在通过单行道的隧道所有车辆不能插队、不能掉头先进来的车也先出去我们可以把这种特征的数据结构称之为队列。队列也属于逻辑结构所谓的物理结构是指可以将数据存储在物理空间中比如数组和链表都属于物理数据结构而逻辑结构则是用于描述数据间的逻辑关系的它可以由多种不同的物理结构来实现比如队列和栈都属于逻辑结构。队列特性队列中的元素必须是先进先出First In First OutFIFO的它有两个重要的方法入队enqueue和出队dequeue。队列的入口端叫队尾rear出口端叫队头front如下图所示手撸队列学习了队列的基本知识之后接下来我们将使用代码来实现一个队列。首先我们先使用数组来实现一个队列它的结构如下图所示1.自定义队列—数组public class MyQueueE {private Object[] queue; // 存储容器private int head; // 头部指针private int tail; // 尾部指针private int size; // 队列实际存储长度private int maxSize; // 最大容量public MyQueue() {// 无参构造函数设置默认参数this.maxSize 10;this.head 0;this.tail -1;this.size 0;this.queue new Object[this.maxSize];}public MyQueue(int initSize) {// 有参构造函数设置参数this.maxSize initSize;this.head 0;this.tail -1;this.size 0;this.queue new Object[this.maxSize];}/*** 查询队头元素*/public E peek() throws Exception {if (size 0) {throw new Exception(队列中暂无数据);}return (E) this.queue[this.head];}/*** 入列*/public boolean offer(E e) throws Exception {if (tail (maxSize - 1)) {throw new Exception(添加失败队列已满);}this.queue[tail] e;size;return true;}/*** 出列*/public E poll() throws Exception {if (size 0) {throw new Exception(删除失败队列为空);}size--;return (E) this.queue[head];}/*** 代码测试*/public static void main(String[] args) throws Exception {MyQueue queue new MyQueue();queue.offer(Hello);queue.offer(Java);System.out.println(queue.peek());queue.poll();System.out.println(queue.poll());}
}
以上代码的执行结果如下HelloJava2.自定义队列—链表用链表实现队列的数据结构如下图所示实现代码如下public class QueueByLinked {/*** 声明链表节点*/static class NodeE {E item; // 当前的值NodeE next; // 下一个节点Node(E e) {this.item e;}}private Node firstNode; // 队头元素private Node lastNode; // 队尾元素private int size; // 队列实际存储数量private int maxSize; // 队列最大容量public QueueByLinked(int maxSize) {if (maxSize 0) throw new RuntimeException(队列最大容量不能为空);// 默认初始化函数firstNode lastNode new Node(null);this.size 0;this.maxSize maxSize;}/*** 判断队列是否为空*/public boolean isEmpty() {return size 0;}/*** 入列*/public void offer(Object e) {// 最大值效验if (maxSize size) throw new RuntimeException(队列已满);Node node new Node(e);lastNode lastNode.next node; // 设置最后一个节点和倒数第二个节点的 nextsize; // 队列数量 1}/*** 出列*/public Node poll() {if (isEmpty()) throw new RuntimeException(队列为空);size--; // 队列数量 -1return firstNode firstNode.next; // 设置并返回队头元素第一个节点是 null当前元素则为 Node.next}/*** 查询队头元素*/public Node peek() {if (isEmpty()) throw new RuntimeException(队列为空);return firstNode.next; // 返回队头元素第一个节点是 null当前元素则为 Node.next}/*** 代码测试*/public static void main(String[] args) {QueueByLinked queue new QueueByLinked(10);queue.offer(Hello);queue.offer(JDK);queue.offer(Java);System.out.println(queue.poll().item);System.out.println(queue.poll().item);System.out.println(queue.poll().item);}
}
以上代码的执行结果如下HelloJDKJava3.扩展使用 List 实现自定义队列除了以上两种方式之外我们还可以使用 Java 自身的数据结构来实现队列比如 List我们这里提供一个实现的思路但并不建议在实际工作中使用实现代码如下import java.util.ArrayList;
import java.util.List;/*** 自定义队列List方式*/
public class QueueByListE {private List value; // 队列存储容器public QueueByList() {// 初始化value new ArrayList();}/*** 判断队列是否为空*/public boolean isEmpty() {return value.size() 0;}/*** 入列*/public void offer(Object e) {value.add(e);}/*** 出列*/public E poll() {if (isEmpty()) throw new RuntimeException(队列为空);E item (E) value.get(0);value.remove(0);return item;}/*** 查询队头元素*/public E peek() {if (isEmpty()) throw new RuntimeException(队列为空);return (E) value.get(0);}/*** 代码测试*/public static void main(String[] args) {QueueByList queue new QueueByList();queue.offer(Hello);queue.offer(JDK);queue.offer(Java);System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());}
}
以上代码的执行结果如下HelloJDKJava队列使用场景队列的常见使用场景有存储多线程中等待排队执行的任务存储多线程公平锁中等待执行任务的线程常见消息中间件的任务队列等。总结通过以上三种队列的实现方式我们可以看出任意容器都是可以用来实现队列Queue的只要保证队列的元素先进先出FIFO并且在实现类中需要包含队列的四个核心方法入列、出列、查询队列是否为空、返回队头元素等就可以称为实现了一个自定义的队列。最后给大家留一个问题队列的类型都有哪些欢迎评论区留言~
往期推荐
动图演示手撸堆栈的两种实现方法链表反转的两种实现方法后一种击败了100%的用户算法图解如何找出栈中的最小值算法图解如何判断括号是否有效关注我每天陪你进步一点点
