本文共 1792 字,大约阅读时间需要 5 分钟。
【题目】
编写一个类, 用两个栈实现队列, 支持队列的基本操作(add, poll, peek).
【难度】
二星
【分析】
如图1-3, 我们往stackPush里面压入数字1~5, 弹出数据的时候, 只需要把stackPush里面的数据倒入stackPop里面, 然后弹出stackPop的栈顶元素1, 就实现了队列先进先出的特性。
说起来容易, 但是要注意以下两点:
1. 往stackPop里面倒入数据时必须一次性倒入
2. stackPop里面有数据时不能再往里倒入数据
1. 往stackPop里面倒入数据时必须一次性倒入
如果stackPush如图1-3, 如果我们先往stackPop里面倒入4和5, 此时弹出的数据就是4, 不符合队列的特性——先进先出
2. stackPop里面有数据时不能再往里倒入数据
如果stackPush里的1~5全部倒入了stackPop里面, 这时又往stackPush里面压入了6~10; 此时stackPop里面有数据1~5, 如果再把stackPush里面的6~10倒入stackPop的话, stackPop里面的数据从上到下就是6~10 1~5, 此时如果弹出的数据就是6, 不符合队列的特性。
【代码实现】
package 栈和队列;import java.util.Stack;public class TwoStackQueue { private Stack【代码分析】stackPush; private Stack stackPop; public TwoStackQueue() { this.stackPush = new Stack (); this.stackPop = new Stack (); } public void add(int newNum) { this.stackPush.push(newNum); } public int poll() { if(this.stackPop.isEmpty()&&this.stackPush.isEmpty()) { throw new RuntimeException("Your queue is empty."); }else if(this.stackPop.isEmpty()) { while(!this.stackPush.isEmpty()) { this.stackPop.push(this.stackPush.pop()); } } return this.stackPop.pop(); } public int peek() { if(this.stackPop.isEmpty()&&this.stackPush.isEmpty()) { throw new RuntimeException("Your queue is empty."); }else if(this.stackPop.isEmpty()) { while(!this.stackPush.isEmpty()) { this.stackPop.push(this.stackPush.pop()); } } return this.stackPop.peek(); }}
poll函数:
类实例调用pop函数, 如果stackPush和stackPop都为空的话, 说明我们的队列没有数据, 抛出异常;
如果stackPop为空, stackPush不为空的话, 把stackPush的数据一次性倒入stackPop, 然后弹出stackPop的栈顶元素;
之后再调用poll, 只要stackPop不为空, 就依次弹出栈顶元素, 直到stackPop为空, 跳转到步骤1继续执行