左神算法学习笔记 - 014【入门】队列和栈入门题目-栈和队列相互实现
用栈实现一个队列结构
这道题希望我们用栈来实现一个先进先出的队列结构。我们知道队列的特点是先进先出，和日常生活中排队一样，先到先得；而栈结构是后进先出，就像弹夹一样，后压入的子弹会被先射出去。这是一道数据结构的设计题目，我们如何用栈的特点来实现一个「逻辑上」的先进先出结构呢？
技巧是使用两个栈，简单来说，如果元素按照 a b c d e（尾 -> 头） 的顺序入栈，我们再准备一个栈，将元素转移进去，就会得到 e d c b a（尾 -> 头） 的入栈顺序，那么再出栈的话就是 a b c d e 的顺序弹出了，就实现了先入的元素先出。
在实现的细节上，最关键的就是这个栈之间「倒入」的过程，需要注意一下几点：
out 栈空了才能从 in 栈倒元素过来，否则顺序就不对了
in 栈每次倒的话，就必须把全部元素都转移到 out 里，否则顺序也不对了
总之，就是我们必须保证整体进出的顺序在逻辑上和队列是一样的。
下面是题解代码：
class MyQueue {
Stack<Integer> in;
Stack<Integer> out;
public MyQueue() {
in = new Stack<>();
out = new Stack<>();
}
// 直接从 in 栈 加入
public void push(int x) {
in.push(x);
inToOut(); // 能倒顺便倒一下
}
// 先倒一下，再给结果
public int pop() {
inToOut();
return out.pop();
}
// peek 操作也是先倒一下再给结果
public int peek() {
inToOut();
return out.peek();
}
// 关键的倒数据的过程
private void inToOut() {
if (out.isEmpty()) {
while (!in.isEmpty()) {
out.push(in.pop());
}
}
}
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
}关于复杂度，对于每个加入“队列的数”内部实际上也就是入栈出栈各两次，因此均摊下来，每个操作是 O(1) 的，因为 n 个数的所有操作总的时间复杂度是 O(n)。
这道题也能看出来，一个典型的队列结构对外提供的 API 有：push、pop、peek、empty，虽然方法名可能有所不同。
用队列实现一个栈结构
这道题和上面的相反，用队列结构实现一个栈。
我们可以用两个队列实现，但是最优解法是用一个队列实现的，而且它们的思路是相同的，只不过一个队列的解法是把相同的操作在原地进行了，因此我们只理解清楚最优解法即可。
用队列模拟栈的关键在于：每次插入新的元素时，我们都要操作一下队列里的所有元素，让这个最新的元素出队的最前方。因此需要做的就是把队列中已经存在的元素，逐个弹出再从队尾加入，这样就维护成了栈的样子。
直接看代码吧：
class MyStack {
public Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
// 关键的操作在于 push 数据之后的处理
public void push(int x) {
int n = queue.size(); // 先拿到目前的长度
queue.offer(x); // 再压入数据
for (int i = 0; i < n; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.pop();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}代码中关键的处理就是 push 元素时候进行的处理，需要注意的是，要在 offer 入数据前，用一个变量记录一下队列的长度，这就是加入数据之后，需要「出队再入队」的次数。
对于时间复杂度，push 操作是 O(n)，因为和元素的数量是线性相关的，其他操作都是一次常数操作。这里不存在像「用栈实现队列」那样存在均摊的逻辑，可以看一下上面的代码，push pop 和 peek 都有倒数据的操作。而这里我们可以想象一下，一个元素可能在这个队列里入队出队多次。
实现一个环形双端队列
首先了解一下，双端队列就是头部和尾部都可以进出元素的队列，题目中所谓的环形其实不那么重要，想表达的意思我理解就是这个结构没有起点的意思，只要 size 满足在给定的 limit 之下，都可以工作即可。
其实双端队列在 Java 中有线程的实现，就是 LinkedList，因此最简单的解法就是直接使用 LinkedList 的 API。
class MyCircularDeque {
Deque<Integer> deque;
int size, limit;
public MyCircularDeque(int k) {
deque = new LinkedList<>();
size = 0;
limit = k;
}
public boolean insertFront(int value) {
if (isFull()) {
return false;
} else {
deque.offerFirst(value);
size++;
return true;
}
}
public boolean insertLast(int value) {
if (isFull()) {
return false;
} else {
deque.offerLast(value);
size++;
return true;
}
}
public boolean deleteFront() {
if (isEmpty()) {
return false;
} else {
deque.pollFirst();
size--;
return true;
}
}
public boolean deleteLast() {
if (isEmpty()) {
return false;
} else {
deque.pollLast();
size--;
return true;
}
}
public int getFront() {
if (isEmpty()) {
return -1;
} else {
return deque.peekFirst();
}
}
public int getRear() {
if (isEmpty()) {
return -1;
} else {
return deque.peekLast();
}
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == limit;
}
}LinkedList 底层的双向链表不存在什么容量的问题，只要内存够用就可以添加元素，因此我们需要一个 size 来记录元素的大小，用 limit 来记录输入中指定的容量，以此来判断 full 和 empty。注意每次添加和删除元素的时候，不要忘记更新 size。
另外需要注意记忆一下 LinkedList 的 Deque API：offerFirst, offerLast, pollFirst, pollLast, peekFirst, peekLast。
LinkedList 虽然可以直接拿来用，但是它各个操作的常数时间是比较慢的。这道题我们还可以使用数组和两个头尾变量来模拟出双端队列。这里直接上一个笔记图片：
在这个数组中，我们通过 l 和 r 两个下标来记录头和尾的位置。需要处理的情况就是当下标来到数组下标 0 和 length - 1 的位置时，它们需要“环绕”过去。这可能就是题目中环形的含义。
双端队列的数组实现：
class MyCircularDeque {
public int[] deque;
public int size, l, r, limit;
public MyCircularDeque(int k) {
deque = new int[k];
size = l = r = 0;
limit = k;
}
public boolean insertFront(int value) {
if (isFull()) return false;
if (isEmpty()) {
l = r = 0;
deque[0] = value;
} else {
l = (l == 0) ? (limit - 1) : l - 1;
deque[l] = value;
}
size++;
return true;
}
public boolean insertLast(int value) {
if (isFull()) return false;
if (isEmpty()) {
l = r = 0;
deque[0] = value;
} else {
r = (r == limit - 1) ? 0 : r + 1;
deque[r] = value;
}
size++;
return true;
}
public boolean deleteFront() {
if (isEmpty()) return false;
l = (l == limit - 1) ? 0 : l + 1;
size--;
return true;
}
public boolean deleteLast() {
if (isEmpty()) return false;
r = (r == 0) ? limit - 1 : r - 1;
size--;
return true;
}
public int getFront() {
if (isEmpty()) {
return -1;
}
return deque[l];
}
public int getRear() {
if (isEmpty()) {
return -1;
}
return deque[r];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == limit;
}
}对于这类题目来说，需要实现的函数比较多，因此可以先从 isEmpty() 和 isFull() 两个函数入手，因为后续的每一个方法都会用到这两个方法。
这道题目是练习边界处理的一道不错的题目，注意插入和删除方法中关于数组下标是否到达边界的判断写法：我们先判断出 l 和 r 的位置，然后把数据插入就好。
另外，在插入的时候，如果整个数组为空，我们把 l 和 r 两个下标重置回 0 位置从头开始，否则结果就不如预期（经过验证）。