数据结构的队列

一.队列

1.队列（Queue）的概念就是先进先出。

2.队列的用法，红色框和绿色框为两组，offer为插入元素，poll为删除元素，peek为查看元素红色的也是一样的。

3.LinkedList实现了Deque的接口，Deque又继承于Queue所以，LinkedList可以实现Queue接口

4.这里先删除的1，因为队列是先进先出。然后再不断的取第一个元素。（offer是尾插poll是头删）

二.链表实现队列

通过双向链表的尾插和头删就可以进行队列的模拟比较简单不赘述：

三.数组实现队列

1.这里需要用到循环的数组来进行实现队列。

2.这里我们有三种方法可以来判断数组是否放满或者为空：（下面是我用第3个方法来实现这个队列）

3.这里计算last的位置的时候不能直接++或者用first（头）++，因为一直++可能会越界，所以这里用(last + 1) % len(数组的长度)，这样就不会越界。

4.代码展示：

循环数组作为队列，需要头和尾，头来进行删除数据，尾部进行插入数据，在扩建数组的长度的时候需要注意我要把数组的大小增大一倍，因为我是通过判断下一个位置是否为头来判断数组是否满了。这里还需要注意的是，删除数据的时候我们要知道，first也要和last一样通过公式(last + 1) % len(数组的长度)来计算。还需要注意的是获取队尾元素的时候，last可能会在0位置，那么就没办法last-1来找到这个数据了，这个时候我们要通过判断last是否为0，如果为0就直接返回数组长度-1作为下标来获取队尾元素，不能直接返回0的下标，因为你要获取的是队尾元素相当于是0的上一个数据是队尾-1元素的下标的数据，而不是0位置这个数据.

7.双端队列（Deque）：两边都可以入队和出队。并且这里还可以通过双端队列来实现队列和栈。需要注意的是Deque是接口，需要创建一个LinkedList的对象才能实现：

8.用法一看便知：

9.队列实现栈:(这里我们是通过两个队列来实现栈的，我们规定两个队列都为空的时候第一个队列存放数据，pop是通过将部位空的队列的n-1个数据移动到空队列中，再将最后一个数据pull出去就是栈pop的元素，获取栈顶元素也是同样的思路，但是栈顶元素需要将n个数据传入到空队列中，并且保存下最后一个数据)

10.栈实现队列：（思路就还是两个栈来实现这个队列，不管什么情况都是把数据放在第一个栈中，当需要队列poll数据的时候我自己实现的两个栈就需要把第一个栈的数据全部pop到第二个栈中来push然后再通过第二个栈来push，因为这样到第二个栈的时候数据就是倒过来的就可以直接push。代码中再pop的时候没有进行判断两个栈是否为空，如果两个栈都为空要返回--1，来判断）