【数据结构】队列

1.啥是队列

2.队列实现

3.Queue接口的介绍以及队列的使用

4.相关队列的例子

（1）啥是队列

我们之前讲解了栈，栈和队列是有点区别的

我们说过栈是一种先进后出的数据结构，你可以把它想象成羽毛球筒；然而队列属于一种先进先出的数据结构，队列嘛，就跟你排队做核酸排队打饭一样咯，你先排，你就先桶嗓子眼，你先排你就先打到饭（当然是不能有插队的情况啦~队列中也没有插队的概念，不会说在中间位置插入元素）

 上图就是你每次去食堂打饭的样子，元素从队尾进，从队首出~~~

---

（2）队列的实现

队列的底层是一个链表，用节点来连接，LinkedLIst实现了Queue接口，因此可以使用Linkedlist来实现一个队列

队列分为：普通队列，双端队列（Deque），优先级队列（堆）

由于堆是之后会介绍的一种数据结构，这里我们就来说说普通队列和双端队列

普通队列就是排队咯，它只有一个方向，遵循先进先出的特点，而双端队列是有两个方向的，你可以同不同的方向进，但你然需要遵循先进先出的特点，简单来说：普通队列是单行道，双端队列是双行道~

 上图展示了双链表的强大之处，使用双链表我们可以实现普通队列，实现双端队列，还可以实现栈~

当然，双链表这么牛逼，使用来实现一个队列岂不是小菜一碟~所以我们提升一下难度，我们不用双链表实现队列，我们改用单链表来实现队列！！！！！

---

我们知道单链表的形式，可以头插尾插，然后还有一个头节点head(这不是虚拟头节点，而是代表第一个元素~)

接下来我们看看怎么使用一个单链表来实现队列，这里我们理想的方式是使队列的入队和出队操作的时间复杂度都分别达到O(1)（遵循先进先出的规则）

1.头插法入队，删除尾巴节点出队（先进先出）——头插的时间复杂度是O(1)，我们有一个头节点head，因此不需要遍历，可以直接头插插入，因此我们使用头插入队；然后我们删除尾巴节点来出队，我们想要删除尾巴节点来实现出队，