LeetCode-剑指 Offer 09. 用两个栈实现队列
- 1. 问题描述
- 2. 解析
- 2.1 栈
- 2.2 队列
- 3. 参考答案
1. 问题描述
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1] 示例 2：
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2] 提示：
- 1 <= values <= 10000
- 最多会对 appendTail、deleteHead 进行 10000 次调用
2. 解析
是不是上来不懂题目的意思，
我也是一脸蒙蔽，还好评论区有大佬讲解：
读懂题目之后，思考的就是如何使用两个栈实现队列的功能。
上来我是这样思考：
2.1 栈
Stack插入一般称为进栈（PUSH），删除则称为退栈（POP）。
栈的特性是先进后出（First In Last Out）FILO
可以想象成垒砖头，一层一层的叠起来，
但是拿取的时候，必须从最上面拿。
2.2 队列
Queue插入一般称为入队（add），删除称为出队（poll）。
队列的特性是先进先出（First In First Out）FIFO
就像排队一样，先来后到。
了解了特性之后，才能开始做题。
两个栈是没有问题的了，先创建出来。
private Stack<Integer> sta1;
private Stack<Integer> sta2; 然后在添加的时候需要处理一下，
就是sta1正常添加，而sta2需要将sta1倒序再添加一下。
public void appendTail(int value) {
sta1.push(value);
setHead();
}
// 每一次添加sta1的时候，sta2就要重新倒序再添加一遍。
private void setHead() {
sta2.clear();
int size = sta1.size();
for (int i = size - 1; i >= 0; i--) {
sta2.push(sta1.elementAt(i));
}
} 这样是不是就完成了队列的转变，
就像压进去1、2、3、4、5
然后我再倒着：5、4、3、2、1压进去，
再弹出来不就是1、2、3、4、5了。
public int deleteHead() {
if (sta2.isEmpty()) {
return -1;
}
// 不要忘了sta1 最开始弹出去。
sta1.remove(0);
return sta2.pop();
} public CQueue() {
this.sta1 = new Stack<>();
this.sta2 = new Stack<>();
}
// 添加的时候只添加sta1
public void appendTail(int value) {
sta1.push(value);
}
// 删除的时候注意了，先判断sta2，如果有继续弹出，否则就是倒序压入sta1的值然后在弹出，这一招妙啊。
public int deleteHead() {
if (!sta2.isEmpty()) {
return sta2.pop();
} else if (!sta1.isEmpty()) {
while (!sta1.isEmpty()) {
sta2.push(sta1.pop());
}
return sta2.pop();
} else {
return -1;
}
} 3. 参考答案
class CQueue {
// 定义两个栈
private Stack<Integer> sta1;
private Stack<Integer> sta2;
// 初始化
public CQueue() {
this.sta1 = new Stack<>();
this.sta2 = new Stack<>();
}
// 添加数据
public void appendTail(int value) {
// 用栈1 添加数据
sta1.push(value);
}
// 弹出数据
public int deleteHead() {
// 先判断栈2 是否为空，不为空就弹出。
if (!sta2.isEmpty()) {
return sta2.pop();
} else if (!sta1.isEmpty()) {
// 否则的话要依次弹出栈1的数据，并添加到栈2里面
// 这里是关键，就很神奇的用两个栈实现了队列功能。
while (!sta1.isEmpty()) {
sta2.push(sta1.pop());
}
return sta2.pop();
} else {
return -1;
}
}
public static void main(String[] args) {
// 输入指令那一行数据如：["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
Scanner scanner = new Scanner(System.in);
String inputStr = scanner.next();
// 去头去尾，替换“并处理成： CQueue,deleteHead,appendTail,appendTail,deleteHead,deleteHead
inputStr = inputStr.substring(1, inputStr.length() - 1).replaceAll("\"", "");
String[] commends = inputStr.split(",");
// 输入代码对应的值:[[],[],[5],[2],[],[]]
String valueStr = scanner.next();
// 去头去尾即可：[],[],[5],[2],[],[]
valueStr = valueStr.substring(1, valueStr.length() - 1);
String[] values = valueStr.split(",");
CQueue myQueue = null;
// 存放最终的结果
StringBuilder result = new StringBuilder();
result.append("[");
for (int i = 0; i < commends.length; i++) {
String commend = commends[i];
String value = values[i];
// 对应处理指令
switch (commend) {
case "CQueue":
myQueue = new CQueue();
result.append("null,");
break;
case "appendTail":
// 去头去尾，拿到中括号里面数字
String num = value.substring(1, value.length() - 1);
myQueue.appendTail(Integer.parseInt(num));
result.append("null,");
break;
case "deleteHead":
int head = myQueue.deleteHead();
result.append(head+",");
break;
default:
}
}
// 去除最后一个逗号，
String resultStr = result.substring(0, result.length() - 1);
System.out.println(resultStr+"]");
}
}