我们结婚了20120714,九泉怪物分布,中国留学生罗马失联过程
工作之余，代码敲多了，停下来思考思考，会有异常不到的收获。。。只为更好的自己
提示下：用一个栈肯定是没办法实现队列，但如果我们有两个栈呢?
栈是先进后出，filo
出入元素都是在同一端（栈顶）
入栈
出栈
队列是先进先出，fifo
出入元素是在不同的两端（队头和队尾）
入栈
出栈
让一个栈作为队列的入口，负责插入新元素；另外一个栈作为队列的出口，负责移除老元素。
如图所示
让栈a中的所有元素按顺序出栈，再按照出栈顺序压入栈b。
这样一来，元素从栈a弹出并压入栈b的顺序是3，2，1和当初进入栈a的顺序123是相反的，如图
此时让元素1 “出队”，也就是让元素1从栈b弹出
代码实现：
我要评论/**
* @author sunyang
* @date 2018/10/25 10:18
*/
public class stackimplqueue {
/**
* 定义两个栈来实现队列
* 栈a 负责插入新元素
* 栈b 负责移除老元素
*/
private stack<integer> stacka = new stack<>();
private stack<integer> stackb = new stack<>();
/**
* 入队操作
* @param element
*/
public void enqueue(int element){
stacka.push(element);
}
/**
*
* 出队操作
*/
public integer dequeue(){
if (stackb.isempty()){
if (stacka.isempty()){
return null;
}
fetchformstacka();
}
return stackb.pop();
}
/**
* 从stacka栈中拿到出栈元素压入栈b
*/
private void fetchformstacka() {
while (!stacka.isempty()){
stackb.push(stacka.pop());
}
}
public static void main(string[] args) {
stackimplqueue stackqueue = new stackimplqueue();
stackqueue.enqueue(1);
stackqueue.enqueue(2);
stackqueue.enqueue(3);
system.out.println(stackqueue.dequeue());
system.out.println(stackqueue.dequeue());
system.out.println(stackqueue.dequeue());
stackqueue.enqueue(4);
system.out.println(stackqueue.dequeue());
}
}
入栈操作的时间复杂度显然是o(1)
出栈操作的时间复杂度如果发生转移的话就是o（n）
如果没有发生转移的话也是o（1）
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
浅析我对 String、StringBuilder、StringBuffer 的理解
使用IDEA搭建SSM框架的详细教程(spring + springMVC +MyBatis)
Springboot整合freemarker 404问题解决方案
引入mybatis-plus报 Invalid bound statement错误问题的解决方法
网友评论