【数据结构】_6.队列
目录
1.概念
2.队列的使用
3.队列模拟实现
4.循环队列
5.双端队列
6.OJ题
6.1 用队列实现栈
6.2 用栈实现队列
1.概念
（1）队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表；
（2）队列具有先进先出，后进后出的特点；
（3）入队列：进行插入操作的一端称为队尾；
出队列：进行删除操作的一端称为队头；
2.队列的使用
在java中，Queue是个接口，底层是通过链表实现的，其常用方法如下：
| 方法 | 功能 |
| boolean offer(E e) | 入队列 |
| E poll() | 出队列 |
| peek() | 获取队头元素 |
| int size() | 获取队列中有效元素的个数 |
| boolean isEmpty() | 检测队列是否为空 |
3.队列模拟实现
（1）包类关系：
（2）TestMyQueue：
package TestMyQueue;import TestMyStack.EmptyException;public class MyQueue {// 使用单链表实现队列static class Node{public int val;public Node next;public Node(int val){this.val = val;}}public Node head;public Node last;public int usedSize;public void offer(int val){Node newNode = new Node(val);if(head == null){head = newNode;last = newNode;}else{last.next = newNode;last = newNode;usedSize++;}}public int poll(){if(isEmpty()){throw new EmptyException();}int ret = head.val;head = head.next;return ret;}public boolean isEmpty(){return usedSize == 0;}public int peek(){if(isEmpty()){throw new EmptyException();}int ret = head.val;return ret;}public int getUseSize(){return usedSize;}
}（3）EmptyException：
package TestMyQueue;public class EmptyException extends RuntimeException{public EmptyException(){}
}4.循环队列
题目链接：622. 设计循环队列 - 力扣（LeetCode）
代码：
class MyCircularQueue {private int[] elem;private int front; // 表示队列的头private int rear; // 表示队列的尾public MyCircularQueue(int k) {this.elem = new int[k+1];}public boolean enQueue(int value) {// 入队列判满if(isFull()){return false;}elem[rear] = value;rear = (rear+1)% elem.length;return true;}public boolean deQueue() {// 判空if(isEmpty()){return false;}front = (front+1)% elem.length;return true;}public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int index = (rear==0)?elem.length-1:rear-1;return elem[index];}public boolean isEmpty() {return front == rear;}public boolean isFull() {// 写法1：
// if( (rear+1) % elem.length == front){
// return true;
// }
// return false;// 写法2：return (rear+1)% elem.length == front;}
}5.双端队列
双端队列是指允许两端都可以进行入队和出队操作的队列；
Deque是一个接口，使用时必须创建其实现类类的对象：
常用的实现类为ArrayDeque（由数组实现的双端队列）和LinkedList（由双向链表实现的双端队列），故而实例化Deque的方式有以下两种：
// 链式双端队列Deque<Integer> deque = new LinkedList<>();// 数组双端队列Deque<Integer> deque2 = new ArrayDeque<>();注：也可以使用Deque实现顺序栈：
实际上，以下写法：
Stack<Integer> stack = new Stack<>(); 即：直接使用Stack类实例化栈对象是很少用的，可以使用ArrayDeque创建顺序栈对象：
Deque<Integer> stack2 = new ArrayDeque<>();6.OJ题
6.1 用队列实现栈
题目链接：225. 用队列实现栈 - 力扣（LeetCode）
解题思路：使用两个队列实现栈，元素入栈至不为空的队列，元素出栈在不为空的队列出栈size-1个元素，最后余下的元素就是要出栈的元素；如果两个队列均为空，则入第一个队列；
代码：
public class MyStack {private Queue<Integer> queue1;private Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {if(!queue1.isEmpty()){queue1.offer(x);}else if(!queue2.isEmpty()){queue2.offer(x);}else{queue1.offer(x);}}public int pop() {if(empty()){// 当前栈为空return -1;}if(!queue1.isEmpty()){int size = queue1.size();for(int i=0;i<size-1;i++){//for(int i=0;i<queue1.size()-1;i++){ //写法错误,poll会导致size变化int ret = queue1.poll();queue2.offer(ret);}return queue1.poll();}else{int size = queue2.size();for(int i=0;i<size-1;i++){int ret = queue2.poll();queue1.offer(ret);}return queue2.poll();}}public int top() {if(empty()){return -1;}if(!queue1.isEmpty()){int size = queue1.size();int ret = -1;for(int i=0;i<size;i++){ret = queue1.poll();queue2.offer(ret);}return ret;}else{int size = queue2.size();int ret = -1;for(int i=0;i<size;i++){ret = queue2.poll();queue1.offer(ret);}return ret;}}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}
}6.2 用栈实现队列
题目链接：232. 用栈实现队列 - 力扣（LeetCode）
解题思路：使用两个栈实现队列，stack1用于入栈元素，当需要出栈元素时，若stack2不为空，直接出栈stack2栈顶元素，如果stack2为空，就将stack1的所有元素入栈到stack2中，再出栈stack2顶元素即可；
代码：
class MyQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()){return -1;}if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()){return -1;}if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.empty() && stack2.empty();}
}