🍀队列(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) { Queue<Integer> 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，则将该元素的前驱节点设置为last；
- last的后继节点变为newNode
- newNode变为新的尾节点
- 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接口是比较多的，栈和队列均可以使用该接口
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现 Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现
⭕总结
关于《 【数据结构】 栈（Stack）与栈的模拟实现》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！
