---

前言

队列和栈是相反的，栈是先进后出，队列是先进先出，相当于排队打饭，排第一的是最先打到饭出去的。

队列

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

队列方法

队列模拟实现

public class MyLinkQueue {//内部类static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;public int usedSize;//入队列public boolean offer(int val){ListNode node = new ListNode(val);if (head == null){head = node;last = node;}else {//尾插法last.next = node;node.prev = last;last = last.next;}usedSize++;return true;}//出队列public int poll(){if (head == null){return -1;}int retVal = head.val;if (head.next == null){head = null;last = null;return  retVal;}head = head.next;head.prev = null;return retVal;}//查看对头元素public int peek(){if (head == null){return -1;}return head.val;}//队列是否为空public boolean empty(){return  head == null;}//队列元素数量public int size(){return usedSize;}
}

循环队列

这个循环队列有点点抽象，用视频来说明一下

还可以用这种方式表示循环队列，并附带两个问题

1. 第一个问题：

解决方法1：用usedZize进行记录；
解决方法2：浪费一个空间表示满：

解决方法3：使用标记

3. 第二个问题：

怎么循环放rear呢?

公式 : rear = (rear+1) % len
% 求的是余数
(0+1)%8=1
(7+1)%8=0

练习1 队列实现栈

1.哪个队列不为空就放哪个队列里
2.出栈的时候哪个队列不为空就出哪个队列的元素（size-1）
3.当两个队列都空了，那么说明模拟的栈是空的了

class MyStack {private Queue<Integer> que1;private Queue<Integer> que2;public MyStack() {que1 = new LinkedList<>();que2 = new LinkedList<>();}public void push(int x) {if (que1.isEmpty()){que1.offer(x);} else if (que2.isEmpty()) {que2.offer(x);}else{//两个队列都为空，指定存放到que1que1.offer(x);}}public int pop() {if (empty()){return -1;}if (!que1.isEmpty()){int size = que1.size();for (int i = 0; i < size-1; i++) {int x = que1.poll();//把que1中size-1的值都出到que2中que2.offer(x);}return que1.poll();//，剩下最后一个值就是要出的数}else{int size = que2.size();for (int i = 0; i < size-1; i++) {int x = que2.poll();que1.offer(x);}return que2.poll();}}public int top() {if (empty()){return -1;}if(!que1.isEmpty()){int size = que1.size();int x = -1;for (int i = 0; i < size; i++) {x = que1.poll();que2.offer(x);}return x;}else{int size = que2.size();int x = -1;for (int i = 0; i < size; i++) {x = que2.poll();que1.offer(x);}return x;}}public boolean empty() {return que1.isEmpty() && que2.isEmpty();}
}