1 import java.util.*;
 2 
 3 /**
 4  * @author 不乏理想的三师弟
 5  * 
 6     曾想过通过红黑树去实现 π_π ，下面代码也可以将ArrayList换成Stack对象作为存储对象。
 7     
 8     考虑到的问题：
 9     1、当最小元素出栈时，次小元素是什么？
10     手段：
11     在每次压栈操作时，都找出此时栈中的最小元素，若该最小元素不在B栈顶则额外压入B栈。
12     (即需执行压栈的元素与B栈顶作比较，若比B栈顶元素小则额外压入B栈)
13     在每次弹栈时，若该弹栈元素==B栈顶元素，则B栈同时进行一次弹栈。
14 
15  */
16 public class MinStack {
17     private ArrayList<Integer> stackA;
18     private ArrayList<Integer> stackB;
19     
20     private int indexA;
21     private int indexB;
22     
23     public MinStack() {
24         stackA = new ArrayList<>();
25         stackB = new ArrayList<>();
26         indexA = -1;
27         indexB = -1;
28     }
29     
30     // 压栈 （A栈）
31     public void push(int x) {
32         // 如果x元素是当前栈中最小元素，则额外压入B栈
33         //注意 是<=，因为在弹栈时是通过判断弹栈元素与B栈顶元素是否相等的而决定B是否弹栈（存在多个相同的当前最小元素的可能）
34         if(x <= min()) {
35             pushB(x);
36         }
37         stackA.add(x);
38         indexA++;
39     }
40     
41     // 弹栈（A栈）
42     public void pop() {
43         if(indexA == -1) return;
44         // 若该弹栈元素==B栈顶元素，则B栈同时进行一次弹栈。
45         if(stackA.remove(indexA--) == min()) {
46             popB();
47         }
48     }
49     
50     //获取栈顶元素（A栈）
51     public int top() {
52         if(indexA == -1) return 0;
53         return stackA.get(indexA);
54     }
55     
56     //获取当前栈中最小元素（获取B栈顶元素）
57     public int min() {
58         // 目的是为了将入栈的第一个元素也压入B栈
59         if(indexB == -1) return Integer.MAX_VALUE;
60         return stackB.get(indexB);
61     }
62     
63     //B栈辅助方法
64     public void popB() {
65         if(indexB == -1) return;
66         stackB.remove(indexB--);
67     }
68     public void pushB(int x) {
69         stackB.add(x);
70         indexB++;
71     }
72 }