用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 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 次调用
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
解题思路
挺有意思的一道题,说这个题有意思不是因为这个题的思路难,而是写了半天,发现忽略了好多小细节。因为队列是先进先出,而栈是先进后出,如果要用栈来实现队列,很容易就想到了用两个栈来回倒,入队就是向栈里压入元素,出队就是将整个栈压入另外一个栈,将栈底元素变成栈顶元素,再出栈。
实现如下:
class CQueue {
Stack stackA;
Stack stackB;
boolean deleteHead;
boolean appendTail;
public CQueue() {
stackA = new Stack();
stackB = new Stack();
appendTail = false;
deleteHead = false;
}
public void appendTail(int value) {
if(deleteHead){
switchStack(stackA,stackB);
}
if(!stackB.empty())
stackB.push(value);
else
stackA.push(value);
appendTail = true;
deleteHead = false;
}
public int deleteHead() {
if(appendTail){
switchStack(stackA,stackB);
}
appendTail = false;
deleteHead = true;
if(stackA.empty() && !stackB.empty())
return (Integer)stackB.pop();
if(stackB.empty() && !stackA.empty())
return (Integer)stackA.pop();
return -1;
}
private void switchStack(Stack a, Stack b){
if(!a.empty()){
while(!a.empty()){
Integer value = (Integer) a.pop();
b.push(value);
}
} else if(!b.empty()){
while(!b.empty()){
Integer value = (Integer) b.pop();
a.push(value);
}
}
}
}
提交没问题,但是感觉写的很繁琐,是因为没有想清楚几个问题就动手了。
- Stack A 和Stack B 可以为固定的栈,即A永远用于进队,B用于出队而不是两个栈来回颠倒,所以appendTail 和 deleteHead 完全用不上。
- Stack 直接使用了java 类包 java.util.Stack, 可以显式给定数据类型,不需要后面再casting
- 提交后发现执行时间较慢,原因是使用的Stack是基于Vector的,有些人直接利用了LinkedList,时间效率一下子就提高了。
- 最后理解了一下Stack.pop() 和 peek()的区别,一个是栈顶元素出栈,后者是保留。
改后的代码为
class CQueue {
Stack<Integer> in;
Stack<Integer> out;
public CQueue() {
in = new Stack<>();
out = new Stack<>();
}
public void appendTail(int value) {
if(!out.empty())
switchStack(out,in);
in.push(value);
}
public int deleteHead() {
if(!in.empty())
switchStack(in,out);
if(!out.empty())
return out.pop();
return -1;
}
private void switchStack(Stack a, Stack b){
while(!a.empty()){
Integer value = (Integer) a.pop();
b.push(value);
}
}
}
其中switchStack 可以继续化简为
b.push(a.pop());
网友评论