设计一个操作时间复杂度为O(1)的栈

发表于

通过Java设计一个栈，实现入栈、出栈和查找最小值的功能，要求时间复杂度为O(1)。

设计思路

由于要求时间复杂度，每次求最小值时，直接查找无疑会增大操作的复杂性，可考虑使用两个栈，一个栈像平时那样存放数据，再加入一个辅助栈来缓存当前栈的最小值。

自定义一个普通栈

此处选择新建一个内部类InnerStack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class InnerStack {
        private int top = 0;
        private int[] arr = new int[Test.MAX_STACK_SIZE];//Test.MAX_STACK_SIZE 为一个常量
        void push(int value) {
            if (top >= Test.MAX_STACK_SIZE) {
                System.out.println("The stack is full!");
            }
            arr[top++] = value;
        }
        int pop() {
            if (top <= 0) {
                System.out.println("The stack is null!");
                return Integer.MAX_VALUE; //出错时返回一个极大的值
            }
            return arr[--top];
        }
        int getTop() {
            return arr[top-1];
        }
        int getSize() {
            return top;
        }
    }

定义操作时间复杂度为O(1)的栈

添加两个InnerStack成员，data用来存放Stack的数据，min用来存放当前栈的最小值

1
2
3
4
5
6
7
8
9
class Stack {
  InnerStack data = null;
  InnerStack min = null;
  public Stack() {
        data = new InnerStack();
        min = new InnerStack();
    }
}

入栈。当Stack栈为空时，入栈第一个数据，放进data栈里。此时，第一个数据即当前栈的最小值，同时加入min栈。以后，每当有入栈操作时，把入栈的数据与min栈的顶端数据作比较，若小于min顶端的数据，则把此数据压入min栈，此数据即为当前Stack栈的最小值；如果入栈的数据没有min的数据大，则只压入data栈。

1
2
3
4
5
6
7
8
9
10
public void push(int value) {
        data.push(value);
        if (data.getSize() == 1) {
            min.push(value);
        }
        if(value < min.getTop()) {
            min.push(value);
        }
    }

出栈。 直接弹出data的栈顶数据，如果其值等于当前Stack栈的最小值即min的栈顶数据，则弹出min的栈顶数据。

1
2
3
4
5
6
7
8
9
public int pop() {
       int temp = data.pop();
       if (temp == min.getTop()) {
           min.pop();
       }
       return temp;
   }

返回最小值。直接返回min的栈顶数据。

1
2
3
public int getMin() {
        return min.getTop();
    }

测试

把{13, 12, -1, 16, 3, 7, 10, -22}压入栈，测试。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Test {
    public static final int MAX_STACK_SIZE = 10;
    public static void main(String []args) {
        Stack s  = new Stack();
        s.push(13);
        s.push(12);
        s.push(-1);
        s.push(16);
        s.push(3);
        s.push(7);
        s.push(10);
        s.push(-22);
        System.out.println("The min value is: " + s.getMin());
    }
}
//output: The min value is: -22