「Java面试必会」两个栈如何实现一个队列
2019-01-03 本文已影响53人
花生无翼
面试中,算法题是无法回避的,问的太深似乎没必要,毕竟应聘的不是算法岗位,如果问到算法题了,那一般肯定会是常见的,你听过,但是又不是很熟悉的东西。我们要做的就是把不熟悉的东西搞熟悉了,不会的东西搞会了,做好充分的准备。
下面这个题就比较有意思了,考的是对数据结构的基本理解,看下怎么实现。两个栈如何实现一个队列?
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class QueueImplementByTwoStacks {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
QueueImplementByTwoStacks() {
stack1 = new Stack<Integer>();
stack2 = new Stack<Integer>();
}
public Integer poll() {
Integer it = null;
if (!stack2 .empty()) {
it = stack2.pop();
} else {
while (!stack1 .empty()) {
it = stack1.pop();
stack2.push( it);
}
if (!stack2 .empty()) {
it = stack2.pop();
}
}
return it ;
}
public Integer offer(int o ) {
stack1.push( o);
return o ;
}
public static void main(String[] args) {
QueueImplementByTwoStacks queue = new QueueImplementByTwoStacks();
List<Integer> list = new ArrayList<Integer>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
list.add( queue.poll());
System. out.println(list .toString());
queue.offer(4);
list.add( queue.poll());
System. out.println(list .toString());
queue.offer(5);
System. out.println(list .toString());
list.add( queue.poll());
/*list.add(queue.poll());
list.add(queue.poll());*/
System. out.println(list .toString());
}
}