广告网站留电话整人,view主题WordPress,网站专题页优化,建设银行交罚款网站文章目录 #x1f340;队列(Queue)的概念#x1f38b;队列的使用#x1f38d;队列的模拟实现#x1f6a9;创建队列#x1f6a9;入队列#x1f6a9;出队列#x1f6a9;获取队头元素#x1f6a9;获取队列长度#x1f6a9;判断是否为空#x1f6a9;完整代码 #x1f33… 文章目录 队列(Queue)的概念队列的使用队列的模拟实现创建队列入队列出队列获取队头元素获取队列长度判断是否为空完整代码 双端队列 (Deque)⭕总结 队列(Queue)的概念
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(FirstIn First Out) 入队列
进行插入操作的一端称为队尾Tail/Rear 出队列
进行删除操作的一端称为队头Head/Front
队列的使用
在Java中Queue是个接口底层是通过链表实现的。 队列在使用时有以下方法 注意Queue是个接口在实例化时必须实例化LinkedList的对象因为LinkedList实现了Queue接口。
使用如下
import java.util.LinkedList;
import java.util.Queue;public class TestMain {public static void main(String[] args) {QueueInteger q new LinkedList();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); // 从队尾入队列System.out.println(q.size());System.out.println(q.peek()); // 获取队头元素q.poll();System.out.println(q.poll()); // 从队头出队列并将删除的元素返回if(q.isEmpty()){System.out.println(队列空);}else{System.out.println(q.size());}}
}
运行结果如下
队列的模拟实现
队列中既然可以存储元素那底层肯定要有能够保存元素的空间通过前面线性表的学习了解到常见的空间类型有两种顺序结构 和 链式结构。
这里博主为大家演示一个双链表模拟实现队列
创建队列
其实就是创建一个双链表这里就不做过多赘述了实现如下 public static class ListNode {ListNode next;ListNode prev;int value;ListNode(int value) {this.value value;}}ListNode first; // 队头ListNode last; // 队尾int size 0;入队列
向双向链表位置插入新节点做法如下
创建一个节点newNode接收传进来的元素判断该队列是否为null若为null则该元素就是队头若不为null则将该元素的前驱节点设置为lastlast的后继节点变为newNodenewNode变为新的尾节点size
实现如下 // 入队列public void offer(int e) {ListNode newNode new ListNode(e);if (first null) {first newNode;
// last newNode;} else {last.next newNode;newNode.prev last;
// last newNode;}last newNode;size;}
出队列
将双向链表第一个节点删除掉做法如下
分为几种情况当队列为空时则直接返回队列为空的异常自定义异常如下
public class EmptyException extends RuntimeException{public EmptyException() {}public EmptyException(String message) {super(message);}
}当队列中只有一个元素----链表中只有一个节点时—直接删除当队列中有多个元素—链表中有多个节点----将第一个节点删除
实现如下 // 出队列---将双向链表第一个节点删除掉public int poll() {
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除int value 0;if (first null) {throw new EmptyException(队列为空);} else if (first last) {last null;first null;} else {value first.value;first first.next;first.prev.next null;first.prev null;}--size;return value;}
获取队头元素
获取链表中第一个节点的值域
若队列为null抛出异常若不为null返回队头的元素
实现如下 // 获取队头元素---获取链表中第一个节点的值域public int peek() {if (first null) {throw new EmptyException(队列为空);}return first.value;}
获取队列长度
直接返回size就好
实现如下 public int size() {return size;}判断是否为空
直接判断对头是否为null然后返回就好
实现如下 public boolean isEmpty(){return first null;}
完整代码
MyQueue实现如下
public class MyQueue {// 双向链表节点public static class ListNode {ListNode next;ListNode prev;int value;ListNode(int value) {this.value value;}}ListNode first; // 队头ListNode last; // 队尾int size 0;// 入队列---向双向链表位置插入新节点public void offer(int e) {ListNode newNode new ListNode(e);if (first null) {first newNode;
// last newNode;} else {last.next newNode;newNode.prev last;
// last newNode;}last newNode;size;}// 出队列---将双向链表第一个节点删除掉public int poll() {
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除int value 0;if (first null) {throw new EmptyException(队列为空);} else if (first last) {last null;first null;} else {value first.value;first first.next;first.prev.next null;first.prev null;}--size;return value;}// 获取队头元素---获取链表中第一个节点的值域public int peek() {if (first null) {throw new EmptyException(队列为空);}return first.value;}public int size() {return size;}public boolean isEmpty(){return first null;}
}双端队列 (Deque)
双端队列deque是指允许两端都可以进行入队和出队操作的队列
deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队也可以从队尾出队和入队 Deque是一个接口使用时必须创建LinkedList的对象。 在实际工程中使用Deque接口是比较多的栈和队列均可以使用该接口
DequeInteger stack new ArrayDeque();//双端队列的线性实现
DequeInteger queue new LinkedList();//双端队列的链式实现⭕总结
关于《 【数据结构】 栈Stack与栈的模拟实现》就讲解到这儿感谢大家的支持欢迎各位留言交流以及批评指正如果文章对您有帮助或者觉得作者写的还不错可以点一下关注点赞收藏支持一下
