一、队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

其实就是对一种结构里面的数据进行，头删和尾插的操作

二、队列的使用

2.1 Queue

在Java中，Queue是个接口，底层是通过链表实现的。

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

队列的方法，出了offer和栈中的push方法名有所不同，其他方法名都是一样的，意思也大概一样。只是插入删除位置不同。

大概给大家介绍一下，Queue基本使用方法：

java">public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);//删除队头元素System.out.println(queue.poll());//1System.out.println(queue.poll());//2//查看对他元素System.out.println(queue.peek());//3System.out.println(queue.peek());//3//队列中元素个数System.out.println(queue.size());//3//队列是否为空System.out.println(queue.isEmpty());//false
}

2.2 双向链表实现Queue

实现之前我们需要考虑一下，用哪一种数据结构好？

可惜的是入队操作需要时间复杂度需要O(n)，我们尽量用一种插入删除都是O(1)的结构。

通过思考发现，双向链表可以很好的解决这个问题：

 那我们就可以来实现

2.2.1 实现成员

java">public class MyQueue<E> {static class ListNode {public Object val;//存放数据public ListNode prev;//记录前驱结点public ListNode next;//记录下一个结点public ListNode(Object val) {this.val = val;//引用类型不需要初始化,默认为null}}public ListNode head;//记录头结点public ListNode last;//记录尾结点
}

2.2.2 实现offer

java">//相当于尾插public void offer(E val) {ListNode node = new ListNode(val);//队列是空的情况,头尾都是一个节点if(head == null) {head = last = node;}else {//结点指向前后的引用连接起来，last指向新的尾结点last.next = node;node.prev = last;last = last.next;}}

2.2.3 实现isEmpty

java">public boolean isEmpty() {
//head等于空返回true，不为空返回falsereturn head == null;
}

2.2.4 实现poll

java">//相当于头删public E pop() {//判断链表是否为空，是最好用一个异常try {if (isEmpty()) {throw new MyQueueNullException("堆栈为空pop");}}catch (MyQueueNullException e) {e.printStackTrace();}因为类型是Object，在获取元素的时候一定要强转换！！！E ret = (E)head.val;if(head.next == null) {//只有一个结点的情况head = last = null;}else {//将head前移，并把现在结点的前驱结点置为nullhead = head.next;head.prev = null;}return ret;}

2.2.5 实现peek

只要poll实现了，peek就很简单了

java">public E peek() {try {if (isEmpty()) {throw new MyQueueNullException("堆栈为空peek");}}catch (MyQueueNullException e) {e.printStackTrace();}//因为类型是Object，在获取元素的时候一定要强转换return (E)head.val;
}

2.2.6 实现size

java">public int size() {int count = 0;ListNode cur = head;while (cur != null) {count++;cur = cur.next;}return count;
}

这个是用双链表实现的，但是如果我们用数组可以做到吗？

可以但是比链表麻烦

2.3 顺序表实现Queue

 那肯定我们最好就是要往0位置放，不然数值一多会浪费很多空间

不过还是有问题，我们应该怎么分辨出元素满，和元素为空的情况：

既然last 是否等于 first无法判断，那么就需要借助其他东西来判断：

1. 用usedSize记录元素个数，空usedSize == 0， 满 usedSize == length
2. 用boolean flg = false；以标记的方法记录满和空
3. 浪费末尾一个空间，last == first就是空，last下一个是first就是满

 前面两个比较简单可以自己完成，我们做第3种相对于来说比较简单：

还有个非常核心的问题，我们如何让这个数组变成这种圆可以循环呢？

补充：大家可能对计算机中用   较小数取余较大数不太熟悉 ：

java">public static void main(String[] args) {System.out.println(0%3);//0System.out.println(1%3);//1System.out.println(2%3);//2System.out.println(3%3);//0System.out.println(4%3);//1
}

根据观察发现，较小数 % 较大数 = 较小数

622. 设计循环队列 - 力扣（LeetCode） 这里刚好有个题就是做循环队列的，那我们就来做这个题

要求：

 

实现，在代码中我写了非常详细的注释:

java">class MyCircularQueue {public int[] elem;public int first;public int last;//构造器，设置队列长度为 kpublic MyCircularQueue(int k) {this.elem = new int[k];}//向循环队列插入一个元素。如果成功插入则返回真public boolean enQueue(int value) {if(isFull()) {//队列满,没叫我们扩容就不用扩容return false;}elem[last] = value;last = (last + 1) % elem.length;return true;}//从循环队列中删除一个元素。如果成功删除则返回真public boolean deQueue() {if(isEmpty()){//队列为空return false;}//first前移一位，就删除了元素,后面要用会自己覆盖掉first = (first + 1) % elem.length;return true;}//队首获取元素。如果队列为空，返回 -1public int Front() {if (isEmpty()) {return -1;}return elem[first];}// 获取队尾元素。如果队列为空，返回 -1public int Rear() {if (isEmpty()) {return -1;}//这样写有个问题，如果last=0的情况，// 就不能用这个
//        return elem[last - 1];int index = (last == 0) ? elem.length - 1 : last - 1;return elem[index];}//检查循环队列是否为空。public boolean isEmpty() {return first == last;}//检查循环队列是否已满。public boolean isFull() {//      假设为满   %   空间       == firstreturn (last + 1) % elem.length == first;}
}

唯一注意的是，获取尾部元素的这种情况：  

2.4 如何在LeetCode上看报错 

但是因为我们方法的原因，有一个错误，也借助这个错误。我记录也教一下大家如何在LeetCode上看报错：

java">public MyCircularQueue(int k) {this.elem = new int[k + 1];
}

 

三、双端队列

3.1 Deque

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

Deque是一个接口，使用时必须创建LinkedList的对象。或者ArrayDeque

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

(在命名的时候区分一下)

java">Deque<Integer> queue1 = new LinkedList<>();//底层是双向链表Deque<Integer> queue2 = new ArrayDeque<>();//底层是动态顺序表

使用：

java">public static void main(String[] args) {Deque<Integer> queue1 = new LinkedList<>();queue1.offer(1);//1queue1.offer(2);//1 2queue1.offerFirst(3);//3 1 2queue1.offerLast(4);//3 1 2 4System.out.println(queue1.poll());//3System.out.println(queue1.pollFirst());//1System.out.println(queue1.pollLast());//4Deque<Integer> queue2 = new ArrayDeque<>();queue2.offer(1);//1queue2.offer(2);//2queue2.offerFirst(3);//3 1 2queue2.offerLast(4);//3 1 2 4System.out.println(queue2.poll());//3System.out.println(queue2.pollFirst());//1System.out.println(queue2.pollLast());//4
}