终极版
- 入栈push:push到stack1中,如果满了,报错。
- 出栈pop: 若stack1,stack2都空,报错;
若stack2不为空,从stack2中pop一个;
若stack2空,将stack1倒入stack2,将最后一个pop出来。
图示
Java代码实现
class StackQueue {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public void push(int item) {
stack1.push(item);
}
public Integer pop() throws Exception{
if (stack1.empty() && stack2.empty()) {
System.out.println("empty");
throw new Exception();
}
if (stack2.empty()) {
while (stack1.size() > 1) {
stack2.push(stack1.pop());
}
return stack1.pop();
} else {
return stack2.pop();
}
}
}
+ push 1, 2, 3
stack1=[1, 2, 3], stack2=[]
- pop: 1
stack1=[1], stack2=[3, 2] //stack1倒入stack1, 把stack1最后一个pop
stack1=[], stack2=[3, 2]
+ push 4, 5
stack1=[4, 5], stack2=[3, 2]
- pop: 2
stack1=[4, 5], stack2=[3]
- pop: 3
stack1=[4, 5], stack2=[]
- pop: 4
stack1=[4], stack2=[5] //stack1倒入stack1, 把stack1最后一个pop
stack1=[], stack2=[5]
- pop: 5
stack1=[], stack2=[]
- pop: empty
网友评论