✨hello，进来的小伙伴们，你们好耶！✨
🍅🍅系列专栏:【数据结构与算法】
✈️✈️本篇内容: 循环队列，双端队列以及面试OJ题！
⛵⛵作者简介：一名双非本科大三在读的科班Java编程小白，道阻且长，你我同行！
🍱🍱码云存放仓库gitee：Java数据结构代码托管！
一、循环队列
环形队列通常使用数组实现。
那么在使用我们的循环队列时，我们可以发现很明显的一个问题就是如何区分空与满，因为刚开始没有存元素的时候我们的head和tail都是在同一位置，随着我们相继向队列中存元素，那么我们的head不动，tail往后走，当tail再次和head相遇的时候，那么问题来了，这个时候队列是满还是空的呢？如何解决？
如何区分空与满
1. 通过添加 size 属性记录
2. 保留一个位置
3. 使用标记
那么今天博主给大家演示就是通过保留一个位置(计数器)来实现循环队列！
一、实现类
class MyCircularQueue {private int front;private int rear;private int capacity;private int[] elements;//通过计数器的方式实现public MyCircularQueue(int k) {capacity = k + 1;elements = new int[capacity];rear = front = 0;}}
2、插入一个元素
public boolean enQueue(int value) {//插入一个元素if (isFull()) {return false;}elements[rear] = value;rear = (rear + 1) % capacity;return true;}
3、删除一个元素
public boolean deQueue() {//删除一个元素if (isEmpty()) {return false;}front = (front + 1) % capacity;return true;}
4、获取队首元素
public int Front() {//获取队首元素if (isEmpty()) {return -1;}return elements[front];}
5、获取队尾元素
public int Rear() {//获取队尾元素if (isEmpty()) {return -1;}return elements[(rear - 1 + capacity) % capacity];}
6、判断是否为空
public boolean isEmpty() {return rear == front;}
7、判断是否满
public boolean isFull() {return ((rear + 1) % capacity) == front;}
二、双端队列
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口，使用时必须创建LinkedList的对象。由于在实际开发中Deque使用的并不是非常多，所以大家只需了解一下即可！
三、面试题
1. 用队列实现栈。
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
解题思路：
因为栈是后进先出结构，而我们的队列是先进先出结构，我们可以用两个队列来模拟实现栈的结构，qu1用来进栈，当我们需要出栈时，将qu1里面的元素出栈size-1个元素，就能得到我们的栈顶元素，注意，进栈的时候先判断两个队列谁不为空往哪个队列进，只有两个队列都为空的时候我们的栈也为空。
代码实现：
class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}//进栈public void push(int x) {if(!qu1.isEmpty()) {qu1.offer(x);}else if(!qu2.isEmpty()) {qu2.offer(x);}else {//两个队列都为空的时候qu1.offer(x);}}//出栈public int pop() {if(empty()) {return -1;//}if(!qu1.isEmpty()) {int size = qu1.size();for (int i = 0; i < size-1; i++) {qu2.offer(qu1.poll());}return qu1.poll();}else {int size = qu2.size();for (int i = 0; i < size-1; i++) {qu1.offer(qu2.poll());}return qu2.poll();}}//peek操作public int top() {if(empty()) {return -1;//}if(!qu1.isEmpty()) {int size = qu1.size();int ret = -1;for (int i = 0; i < size; i++) {ret = qu1.poll();qu2.offer(ret);}return ret;}else {int size = qu2.size();int ret = -1;for (int i = 0; i < size; i++) {ret = qu2.poll();qu1.offer(ret);}return ret;}}//两个队列都为空 那么就是栈为空public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}}
2. 用栈实现队列。
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有push to top,peek/pop from top,size, 和is empty操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解题思路：
1、用两个栈实现队列，先将元素全部入栈到第一个栈s1当中。
2、pop()操作，先判断s1是否为空，如果为空则返回-1，接着判断条件为s2为空,s1不为空，将s1中的元素全部进栈到s2当中，然后return s2.pop()便是出队操作。
3、跟操作2类似，最后返回s2.peek()便可！
代码实现：
import java.util.*;class MyQueue {private Stack<Integer> s1;private Stack<Integer> s2;public MyQueue() {s1 = new Stack<>();s2 = new Stack<>();}public void push(int x) {s1.push(x);}//public int pop() {if(empty()) {return -1;}if(s2.empty()) {while (!s1.empty()) {s2.push(s1.pop());}}//return s2.pop();}public int peek() {if(empty()) {return -1;}if(s2.empty()) {while (!s1.empty()) {s2.push(s1.pop());}}//return s2.peek();}//如果两个栈 都是空的 呢么队列就是空的public boolean empty() {return s1.empty() && s2.empty();}}
🍻好了，那么关于队列的知识点就先讲到这里啦，我们下期见，拜拜！🥞
如果觉得《【数据结构与算法】深入理解队列(下)》对你有帮助，请点赞、收藏，并留下你的观点哦！
