✨hello，进来的小伙伴们，你们好耶！✨
🍅🍅系列专栏:【数据结构与算法】
✈️✈️本篇内容: 循环队列，双端队列以及面试OJ题！
⛵⛵作者简介：一名双非本科大三在读的科班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();
}
}
🍻好了，那么关于队列的知识点就先讲到这里啦，我们下期见，拜拜！🥞
