java 中的堆栈实现使用具有自动调整大小的默认整数数组

Question

所以我想在 java 中创建一个更省时的堆栈实现，但我不知道如何让它工作得更快。这是我的代码：

import java.util.Scanner;

public class A {

    public static void main(String[] args) {
        int[] n = new int[0];

        Scanner scan = new Scanner(System.in);
        loop: while(true){
            String stringy = scan.next();
            switch(stringy){
                case "push":
                    int x = scan.nextInt();
                    n = push(x, n);
                    System.out.println("ok");
                    break;
                case "pop":
                    n = pop(n);
                    break;
                case "exit":
                    System.out.println("bye");
                    break loop;
                case "size":
                    System.out.println(n.length);
                    break;
                case "back":
                    back(n);
                    break;
                case "clear":
                    n = clear();
                    System.out.println("ok");
                    break;

            }
        }

    }
    static int[] push(int n, int[] x) {
        int[] z = new int[x.length + 1];
        for (int i = 0; i < x.length; i++){
            z[i] = x[i];
        }
        z[x.length] = n;
        return z;
    }


    static int[] pop(int[] x){
        int z[] = new int[x.length-1];
        for(int i = 0; i < z.length; i++){
            z[i] = x[i];
        }
        System.out.println(x[x.length-1]);
        return z;
    }
    static void back(int[] x){
        System.out.println(x[x.length-1]);
    }
    static int[] clear(){
        int x[] = new int[0];
        return x;
    }
}

简要说明：程序从扫描仪中获取值。并且根据输入的单词，程序继续执行相应的指令，如 push、pop、back... 并打印出预期值以使用 ok 进行控制台。到目前为止，除性能外，一切都按预期正常工作。如您所见，在 push 和 pop 方法中，我的程序创建新数组并复制获取的数组 x 的值，并添加 1 个具有推送值的索引或删除弹出的值。这种方法似乎相当缓慢且效率低下。如果不从 java 库中选择 arraylist 或其他类，我找不到更有效的方法。但我必须使用默认的整数数组。还有其他问题会恶化程序的性能吗？我怎样才能让我的程序运行得更快？

Answer 1

您可以在方法之外创建成员变量来跟踪数组及其大小（类似于数组列表的实现方式），无需每次需要时都重新复制整个数组 pop/push.

您将需要 2 个变量，数组本身和大小（这将 expand/shrink 根据您的操作而定）

你最好创建一个新的 class，我将其命名为 CustomStack

public class CustomStack
{
    private int[] elements = new int[10];  // instantiated with a size of 10
    private int size;  // To track how many ints we currently have
....
}

您现在可以在方法中访问数组和大小。

所以首先你需要 push 方法，但是这里有一个技巧，如果我已经达到数组的最大大小怎么办？（即：数组中已经有 10 个数字），您需要解决这个问题，解决此问题的一种已知方法是创建一个新数组，其大小是当前数组的两倍，然后将所有值复制到新数组。

private void validateArraySize()
{
    if (size == elements.length)
    {
        int[] temp = new int[elements.length * 2]; //double the size
        System.arraycopy(elements, 0, temp, 0, elements.length);  // copy the array
        elements = temp; //set our member variable array to the new array
    }
}

以及推送方法：

public void push(int n)
{
     validateArraySize(); // The previos method to check if we can safely insert the value
     elements[size] = n;
     size++;
}

关于pop方法，很简单，只需要检查数组里面有没有整数即可：

 public int pop()
 {
     int valueRemoved = 0;
     if (size == 0)
        System.out.println("No elements found to pop");
     else
     {
         valueRemoved = elements[size - 1]; //Get the last value
         elements[size - 1] = 0;  // remove the last value
         size--;
      }
      return valueRemoved; // return removed value
 }

整个class看起来像这样：

public class CustomStack
{
    private int[] elements = new int[10];
    private int size;

    public void push(int n)
    {
        validateArraySize();
        elements[size] = n;
        size++;
    }

    private void validateArraySize()
    {
        if (size == elements.length)
        {
            int[] temp = new int[elements.length * 2];
            System.arraycopy(elements, 0, temp, 0, elements.length);
            elements = temp;
        }
    }

    public int pop()
    {
        int valueRemoved = 0;
        if (size == 0)
            System.out.println("No elements found to pop");
        else
        {
            valueRemoved = elements[size - 1];
            elements[size - 1] = 0;
            size--;
        }
        return valueRemoved;
    }

    public int getSize()
    {
        return size;
    }

    public void back()
    {
        if (size == 0)
            System.out.println("No elements found");
        else
            System.out.println(elements[size - 1]);
    }

    public void clear()
    {
        elements = new int[10];
    }
}

您的主要方法将变为：

 public static void main(String[] args) {
        CustomStack customStack = new CustomStack();

        Scanner scan = new Scanner(System.in);
        loop: while(true){
            String stringy = scan.next();
            switch(stringy){
                case "push":
                    int x = scan.nextInt();
                    customStack.push(x);
                    System.out.println("ok");
                    break;
                case "pop":
                    int val = customStack.pop();
                    System.out.println(val + " is popped");
                    break;
                case "exit":
                    System.out.println("bye");
                    break loop;
                case "size":
                    System.out.println(customStack.getSize());
                    break;
                case "back":
                    customStack.back();
                    break;
                case "clear":
                    customStack.clear();
                    System.out.println("ok");
                    break;

            }
        }

java 中的堆栈实现使用具有自动调整大小的默认整数数组

Stack implementation in java using default integer array with auto resize

java

arrays

data-structures

stack