《剑指offer》面试题7 用两个栈实现队列 Java版
2024-10-07 11:56:38
书中方法：队列是先进先出的，栈是先进后出的，试想把一串数压入A栈，接着一个个出栈并压入B栈，便会完成“头在下”到“头在上”的转变。B栈内还有元素时，直接出栈表示出列，如果没有元素则将A栈内元素压入B栈内。这个没有测试，省略了异常抛出。
public class QueueImplementionByTwoStack<Integer> {
private Stack<Integer> in = new Stack<>();
private Stack<Integer> sup = new Stack<>();
public void offer(Integer a){
in.push(a);
}
public Integer poll(){
if(sup.isEmpty()){
while(!in.isEmpty()){
sup.push(in.pop());
}
}
return sup.pop();
}
}
题目7扩展：用两个队列实现实现栈
书中方法：由于用两个队列并不能改变元素的出列顺序（而用两个栈可以），在表示出栈的时候，我们只能把前面的元素移入另一个队列，然后在原队列获得这个元素。也就是说有一个队列始终作为辅助，临时存放需要pop出的元素的前面的元素。
public class StackImplementionByTwoQueue<Item> {
private LinkedList<Item> q1;
private LinkedList<Item> q2;
public void push(Item item){
if(q1.isEmpty()){
q2.offer(item);
}else q1.offer(item);
}
public Item pop(){
if (q2.isEmpty()) {
while(q1.size()>1){
q2.offer(q1.poll());
}
return q1.poll();
}else{
while(q2.size()>1){
q1.offer(q2.poll());
}
return q2.poll();
}
}
}
最新文章
- Mono 3.2.7发布，JIT和GC进一步改进
- .net中 页面包含子页面 类似include的功能--（记录九）
- myeclipse maven 安装
- iOS重一些常用的代理模式
- 捉襟见肘之UIViewAnimationOptions
- 【转】字符集和字符编码（Charset & Encoding）
- 字符串连接，数字tostring，写入文件
- Windows性能计数器2
- updatepanel刷新后重新加载js脚本问题
- Spring初识(通过小实例清晰认识Spring)
- php后台模板html拼接写法
- 一个基于JRTPLIB的轻量级RTSP客户端(myRTSPClient)——收流篇：（四）example代码解析
- 如何将vue/html在Hbuilder里进行apk打包封装生成直接可用程序
- 【AtCoder】ARC075
- Dijskstra算法
- 八、K3 WISE 开发插件《工业单据老单插件中获取登陆用户名》
- 如何查看thinkphp版本号？
- xdoj 1330---异或（找规律）
- 二分搜素——（lower_bound and upper_bound)
- Axiom3D:数据绑定基本流程