java 实现下压栈的操作(能动态调整数组大小)

实现下压栈的操作是实现栈数据结构的一种方式，下面是如何用Java实现这种操作，同时可以动态调整数组大小。

实现步骤

1. 定义一个类来存储栈的操作。
2. 在该类中创建一个数组来存储栈的元素。
3. 创建一个变量来存储栈中元素的数量。
4. 实现一个方法push()，将元素压入栈中。如果数组已满，则将数组的大小扩大一倍。将新元素添加到数组的结尾。
5. 实现一个方法pop()，将栈顶元素弹出并返回。如果数组数目小于数组大小的四分之一，则将数组大小缩小一半。
6. 实现一个方法isEmpty()，检查栈是否为空。
7. 实现一个方法size()，返回栈中元素的数量。

下面是示例代码：

public class Stack<Item>{
    private Item[] items;
    private int size;
    private int capacity;

    public Stack(int capacity){
        items = (Item[]) new Object[capacity];
        this.capacity = capacity;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public int size(){
        return size;
    }

    private void resize(int capacity){
        Item[] temp = (Item[]) new Object[capacity];
        for (int i = 0; i < size; i++){
            temp[i] = items[i];
        }
        items = temp;
        this.capacity = capacity;
    }

    public void push(Item item){
        if (size == capacity){
            resize(capacity * 2);
        }
        items[size++] = item;
    }

    public Item pop(){
        Item item = items[--size];
        items[size] = null;
        if (size > 0 && size == capacity / 4){
            resize(capacity / 2);
        }
        return item;
    }
}

这里我们定义了一个Stack类。其泛型类型为Item。它包含了一个数组items和size变量来表示栈中元素的数量。另外还有一个capacity变量表示数组的大小。

接着实现了isEmpty()和size()两个方法。

resize()方法用于重新分配数组大小。新建一个新的数组temp，将目前数组中的所有元素复制到新数组中。

push()方法将元素压入栈中。如果数组已满，将调用resize()方法将数组大小扩大一倍。将新元素添加到数组的末尾。

pop()方法从栈顶弹出元素并返回其值。如果数组中的元素数量小于数组大小的四分之一，则将数组大小缩小一半。

接下来，我们用实例来说明一下该类的使用方法。

示例1：使用Stack类实现栈的基本操作

Stack<String> stack = new Stack<String>(10);
stack.push("Hello");
stack.push("World!");
stack.push("How");
stack.push("are");
stack.push("you?");
while (!stack.isEmpty()){
    System.out.print(stack.pop() + " ");
}

输出结果：

you? are How World! Hello 

示例2：使用Stack类实现对表达式的求值

Stack<Double> vals = new Stack<Double>(10);
Stack<String> ops = new Stack<String>(10);

while (!StdIn.isEmpty()) {
    String s = StdIn.readString();
    if (s.equals("(")) ;
    else if (s.equals("+")) ops.push(s);
    else if (s.equals("-")) ops.push(s);
    else if (s.equals("*")) ops.push(s);
    else if (s.equals("/")) ops.push(s);
    else if (s.equals("sqrt")) ops.push(s);
    else if (s.equals(")")) {
        String op = ops.pop();
        double v = vals.pop();
        if (op.equals("+")) v = vals.pop() + v;
        else if (op.equals("-")) v = vals.pop() - v;
        else if (op.equals("*")) v = vals.pop() * v;
        else if (op.equals("/")) v = vals.pop() / v;
        else if (op.equals("sqrt")) v = Math.sqrt(v);
        vals.push(v);
    }
    else vals.push(Double.parseDouble(s));
}

System.out.println(vals.pop());

输入表达式：

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

输出结果：

101.0

以上就是实现下压栈操作并动态调整数组大小的步骤和示例说明。