- 主页/
- [名企面试知识点][Java]用两个栈实现队列
[名企面试知识点][Java]用两个栈实现队列
发布于 2017-03-07 13:12
2411 次浏览
0 赞
来自 笔试面试
题目描述
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
题目分析
用两个栈实现FIFO
情况一:如果出栈时stack2为空,则直接把stack1全部出栈到stack2之后,返回stack2.pop()就可以得出 出栈结果。
情况二:已经出栈过,stack2中有数据。stack1中也有数据,现在要出栈。就要先把stack1的全部数据出栈到stack2,然后再返回stack2.pop()的值就行。
实现代码:
> 运行时间:27ms 占用内存:503k
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
值得注意的是:
isEmpty()是 stack父类vector中的方法,stack中判空的函数是 empty(),虽然都是判断当前集合的元素个数是否为0。但是isEmpty()是同步的方法,empty()不是线程同步的。并且用isEmpty()的时间效率更高!
添加回复