数组扩容问题

Author Avatar
cuteximi 9月 19, 2017
  • 在其它设备中阅读本文章

用数组模拟栈

数组是固定大小的,不能改变长度,要想达到数组扩容的目的,就只能把当前数组复制到一个更长长度的数组中;

使用Arrays.copyOf()方法
源码如下:

public static short[] copyOf(short[] original, int newLength) {
        short[] copy = new short[newLength];
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

可以看出,内部调用了System.arraycopy()方法。

下面是用数组实现一个栈的代码:

class MinStack {
    /** initialize your data structure here. */
    int[] stack ;//数组
    int defaultSize = 2;//默认大小
    int realNumber;//存在的数量
    public MinStack() {
        this.stack = new int[defaultSize];
    }

    public void push(int x) {
        if(realNumber == stack.length){
            stack = Arrays.copyOf(stack,stack.length+defaultSize);  
        }
          stack[realNumber++] = x;    
    }

    public void pop() {
        if(realNumber > 0){
           realNumber--; 
        }
    }

    public int top() {
        return stack[realNumber-1];
    }

    public int getMin() {

        int min = stack[0];
        for(int i = 0;i < realNumber;i++){
            if(min > stack[i]){
                min = stack[i];
            }
        } 
        return min;

    }
}

This blog is under a CC BY-NC-SA 3.0 Unported License
本文链接:http://blog.cuteximi.com/数组扩容问题/