剑指offer/LintCode40_用两个栈模拟队列
文章目录
剑指offer/LintCode40_用两个栈模拟队列
声明
文章均为本人技术笔记,转载请注明出处https://segmentfault.com/u/yzwall
解题思路
实现功能:
用两个栈模拟实现一个队列的push(element),pop()和top()操作;
解题思路
假设有两个栈stack1, stack2
队列
push(element)实现:始终用stack1入栈实现-
队列
pop()和top()实现:由于stack1依次出栈并压入stack2中,恰好保证stack2中顺序与模拟队列顺序一致,始终保证stack2栈顶元素为模拟队列队首当stack2为空时,stack1中全部元素依次出栈并入栈stack2,最后直接弹出栈顶或者只返回栈顶数据;
当stack2不空时,直接弹出栈顶或者只返回栈顶数据;
注意点
对空栈进行
pop()和top()操作时考虑异常情况;实现栈弃用
java.util.stack,选用java.util.ArrayDeque实现;
题目链接
lintcode 40: http://www.lintcode.com/en/problem/implement-queue-by-two-stacks/
剑指offer 面试题7
Java代码
import java.util.ArrayDeque;
/**
* 用两个栈实现一个队列
* http://www.lintcode.com/en/problem/implement-queue-by-two-stacks/
* @author yzwall
*/
class MyQueue {
private ArrayDeque<Integer> stack1;
private ArrayDeque<Integer> stack2;
MyQueue() {
this.stack1 = new ArrayDeque<>();
this.stack2 = new ArrayDeque<>();
}
public void push(int element) {
stack1.push(element);
}
public int pop() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int top() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论