剑指offer/LintCode494_用两个队列实现一个栈
文章目录
剑指offer/LintCode494_用两个队列实现一个栈
声明
文章均为本人技术笔记,转载请注明出处https://segmentfault.com/u/yzwall
解题思路
实现功能:
用两个队列实现一个栈,实现push(element),pop(),top()和isEmpty()方法;
解题思路
假设有队列queue1和queue2;
实现栈的push(element)操作
实现栈push(element)操作:始终用来queue1入队实现;
实现栈的pop()方法
模拟栈的过程中,保证两个队列中始终有一个队列为空,另一个队列不空,空栈时两队列全部为空;;
queue1和queue2运行过程中有时充当from,有时充当to;
非空队列from中所有元素依次出队并入队to队列中,直到from中只剩下一个元素,
实现
pop()操作:弹出from中最后一个元素;实现
top()操作:保存from中最后一个元素并返回,from弹出并入队to队列中(保证每次操作完成后,两个队列中始终有一个队列为空,另一个队列不空,空栈除外);
注意点
使用java.util.ArrayDeque实现队列时,切记用offer()方法入队而不用push()方法,用poll()方法出队而不用pop()方法;
题目链接
lintcode 494: http://www.lintcode.com/en/problem/implement-stack-by-two-queues/;
Java代码
/**
* 用两个队列实现一个栈
* http://www.lintcode.com/en/problem/implement-stack-by-two-queues/
* @author yzwall
*/
import java.util.ArrayDeque;
class Stack {
private ArrayDeque<Integer> queue1;
private ArrayDeque<Integer> queue2;
int top;
Stack() {
this.queue1 = new ArrayDeque<>();
this.queue2 = new ArrayDeque<>();
}
// queue1始终负责实现栈的push操作
public void push(int element) {
queue1.offer(element);
}
// 将from队列元素出队,并依次入队到to队列,直到from队列中只有一个元素
public void move(ArrayDeque<Integer> from,
ArrayDeque<Integer> to) {
while (from.size() > 1) {
to.offer(from.poll());
}
}
public void pop() {
if (!isEmpty()) {
if (!queue1.isEmpty()) {
move(queue1, queue2);
// queue1队列pop后为空
queue1.poll();
} else if (!queue2.isEmpty()) {
move(queue2, queue1);
// queue1队列pop后为空
queue2.poll();
}
}
}
public int top() {
if (!isEmpty()) {
if (!queue1.isEmpty()) {
move(queue1, queue2);
// 获取模拟栈顶元素,清空栈顶所在队列
top = queue1.peek();
queue2.offer(queue1.poll());
} else if (!queue2.isEmpty()) {
move(queue2, queue1);
// 获取模拟栈顶元素,清空栈顶所在队列
top = queue2.peek();
queue1.offer(queue2.poll());
}
return top;
}
return 0;
}
public boolean isEmpty() {
return queue1.isEmpty() && queue2.isEmpty();
}
}

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