献县建设局网站,移投界seo,利搜网站排名软件,wordpress密码邮箱1.队列(Queue)
1.1 关于队列 队列 #xff1a;只允许在一端进行插入数据操作#xff0c;在另一端进行删除数据操作的特殊线性表#xff0c; 队列具有先进先出 FIFO(First In First Out)的操作特性#xff08;队列是个接口#xff09;#xff1b; 入队列#x…1.队列(Queue)
1.1 关于队列 队列 只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表 队列具有先进先出 FIFO(First In First Out)的操作特性队列是个接口 入队列进行插入操作的一端称为队尾 Tail/Rear 出队列进行删除操作的一端称为队头 Head/Front 下图通过图解来了解关于队列入队和出队的操作 1.2队列与链表 在Java中Queue是个接口底层是通过链表实现的 具体情况如下图所示
1.3 队列的基本使用方法 下图是使用队列时具体的基本方法 注意Queue是个接口在实例化时该接口时必须实例化LinkedList的对象因为LinkedList实现了Queue接口。
2.用链表实现队列 我们本次使用的是双向链表
2.1创建队列
public class MyLLQueue {//创建静态内部类,实例对象作为队列中的节点public static class Node {int value;Node next;Node prev;public Node(int value) {this.value value;}}public Node front;//双向链表的头结点public Node rear;//双向链表的尾结点public int usedSize 0;//记录队列中节点个数
}
2.2入队列 思路 1、创建一个要添加的值为value的节点node。 2.1判断当前队列是否为空即链表头结点front是否为null,若为null则该node既是front队头和也是rear队尾。 2.2若队头不为null则将该节点的引用给当前队列的队尾的next至此队尾就是我们新添加的节点 4、队列里面的数据容量加一。 代码如下
public boolean offer(int vale) {Node node new Node(vale);if (isEmpty()) {front node;rear node;} else {rear.next node;node.prev rear;}rear node;usedSize;return true;}
2.3 判断队列是否为空
private boolean isEmpty() {return usedSize 0;} 2.4出队列 1、队列为空则直接返回队列为空的自定义异常。
public class EmptyException extends RuntimeException{public EmptyException(String msg) {super(msg);}
} 2、队列此时不为空。 2.1 此时队列中只有一个元素即队头的next域里存放的是空指针null出队操作之后队列就为空故此让队头和队尾都指向空指针 2.2 此时队列中有多个元素让队头的后域指向下一个节点队头的前域指向空指针 3、队列里面的数据容量减一
//出队列---将双向链表第一个节点删除掉,并返回第一个删除节点的值public int poll() {// 1. 队列为空// 2. 队列中只有一个元素----链表中只有一个节点---直接删除// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除if (isEmpty()) {//队列为空,抛异常,提示不能对空队列进行出队操作throw new EmptyException(队列为空,操作错误!!);}//用ret记录返回的队头元素的数据int ret front.value;if (front.next null) {//当前链表只有一个节点front null;rear null;usedSize--;return ret;}front front.next;front.prev null;usedSize--;return ret;}
2.5获取队头元素 思路类似于2,4部分
//获取队头元素的值,不出队列int peek(){if (isEmpty()) {//队列为空,抛异常,提示不能对空队列进行出队操作throw new EmptyException(队列为空,操作错误!!);}return front.value;}
2.6 双向链表linkedlist实现队列的完整代码
public class MyLLQueue {//创建静态内部类,实例对象作为队列中的节点public static class Node {int value;Node next;Node prev;public Node(int value) {this.value value;}}public Node front;//双向链表的头结点public Node rear;//双向链表的尾结点public int usedSize 0;//记录队列中节点个数//为了体现队列的先进先出特点,规定从尾入,从头出(也可以头进尾出)//插入操作,原理为双链表的尾插法public boolean offer(int vale) {Node node new Node(vale);if (isEmpty()) {front node;rear node;} else {rear.next node;node.prev rear;}rear node;usedSize;return true;}private boolean isEmpty() {return usedSize 0;}//出队列---将双向链表第一个节点删除掉,并返回第一个删除节点的值public int poll() {// 1. 队列为空// 2. 队列中只有一个元素----链表中只有一个节点---直接删除// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除if (isEmpty()) {//队列为空,抛异常,提示不能对空队列进行出队操作throw new EmptyException(队列为空,操作错误!!);}//用ret记录返回的队头元素的数据int ret front.value;if (front.next null) {//当前链表只有一个节点front null;rear null;usedSize--;return ret;}front front.next;front.prev null;usedSize--;return ret;}//获取队头元素的值,不出队列int peek(){if (isEmpty()) {//队列为空,抛异常,提示不能对空队列进行出队操作throw new EmptyException(队列为空,操作错误!!);}return front.value;}//获取队列的长度public int size(){return usedSize;}public static void main(String[] args) {MyLLQueue myLLQueue new MyLLQueue();System.out.println(myLLQueue.isEmpty());myLLQueue.offer(1);myLLQueue.offer(2);myLLQueue.offer(3);System.out.println(myLLQueue.size());System.out.println(myLLQueue.peek());System.out.println(myLLQueue.poll());System.out.println(myLLQueue.peek());System.out.println(myLLQueue.size());}
}测试结果如下 3. 双端队列 (Deque) 双端队列deque是指允许两端都可以进行入队和出队操作的队列deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队也可以从队尾出队和入队。 Deque是一个接口与queue类似在使用时必须创建LinkedList的对象以下是详细图解 在实际工程中使用Deque接口是比较多的栈和队列均可以使用该接口代码如下
DequeInteger stack new ArrayDeque();//双端队列的线性实现
DequeInteger queue new LinkedList();//双端队列的链式实现
ps本次内容就到这里如果喜欢的话就请一键三连哦
