Java使用原生int数组实现自动扩容栈的性能优化问题

其他影响性能的问题 #

• 输入输出效率低：Scanner的解析效率远低于原生IO类，大量指令输入场景下会成为主要瓶颈；同时每次操作直接调用System.out.println会触发频繁的IO刷盘，拖慢整体运行速度。
• 数组复制实现效率低：手动写for循环做数组全量复制，性能远低于JDK自带的native实现的数组复制方法。
• 操作逻辑存在无效开销：pop时没有必要每次都复制前n-1个元素，clear也没必要新建空数组，这些都是无意义的内存申请和复制开销。

完整优化方案 #

1. 核心存储逻辑重构（均摊操作复杂度降到O(1)） #

• 不再让数组长度等于实际元素数量，增加一个size变量记录当前栈内实际元素个数，数组预留冗余容量：
  • 初始数组容量可以设为16，push时如果size < 数组长度，直接将元素写入arr[size]后size加1即可，不需要复制数组。
  • 只有当size == 数组长度时才扩容，每次扩容为原容量的2倍，此时仅需要一次全量复制，均摊下来每次push的时间复杂度为O(1)。
  • pop操作直接返回arr[size-1]后size减1即可，不需要重建数组，只有当size小于数组容量的1/4时，才将数组缩容为原容量的1/2，避免频繁扩容缩容抖动。
  • clear操作直接把size设为0即可，不需要新建空数组。
• 数组扩容/缩容时使用System.arraycopy（原生native实现）替代手动for循环复制，复制效率更高。

2. 输入输出优化 #

• 输入替换为BufferedReader + StringTokenizer组合，读取速度比Scanner高5~10倍，适合大量指令输入的场景。
• 输出使用PrintWriter替代直接System.out.println，可以减少IO刷新次数，提升输出效率。

3. 代码结构优化 #

将栈的相关逻辑封装为独立类，避免每次操作都传递数组、返回数组，减少不必要的对象操作开销。

优化后完整代码示例 #

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class IntStack {
    private int[] arr;
    private int size;
    private static final int INIT_CAPACITY = 16;

    public IntStack() {
        arr = new int[INIT_CAPACITY];
        size = 0;
    }

    public void push(int x) {
        if (size == arr.length) {
            // 扩容为2倍
            int[] newArr = new int[arr.length * 2];
            System.arraycopy(arr, 0, newArr, 0, arr.length);
            arr = newArr;
        }
        arr[size++] = x;
    }

    public int pop() {
        int val = arr[--size];
        // 缩容判断，避免空间浪费
        if (size > 0 && size == arr.length / 4) {
            int[] newArr = new int[arr.length / 2];
            System.arraycopy(arr, 0, newArr, 0, size);
            arr = newArr;
        }
        return val;
    }

    public int back() {
        return arr[size - 1];
    }

    public int size() {
        return size;
    }

    public void clear() {
        size = 0;
        // 若需要主动释放内存可取消下方注释
        // arr = new int[INIT_CAPACITY];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        IntStack stack = new IntStack();
        StringTokenizer st;

        while (true) {
            String line = br.readLine();
            if (line == null) break;
            st = new StringTokenizer(line);
            String op = st.nextToken();
            switch (op) {
                case "push":
                    int x = Integer.parseInt(st.nextToken());
                    stack.push(x);
                    pw.println("ok");
                    break;
                case "pop":
                    pw.println(stack.pop());
                    break;
                case "exit":
                    pw.println("bye");
                    pw.flush();
                    return;
                case "size":
                    pw.println(stack.size());
                    break;
                case "back":
                    pw.println(stack.back());
                    break;
                case "clear":
                    stack.clear();
                    pw.println("ok");
                    break;
            }
            pw.flush();
        }
    }
}

内容的提问来源于stack exchange，提问作者Aitsuken