栈介绍

什么是栈

栈（Stack）是一种基础的数据结构，它按照后进先出（Last In First Out，LIFO）的原则存储和操作数据。栈可以看作是一种线性容器，只能在容器的一端进行插入和删除操作，这一端被称为栈顶，另一端被称为栈底。

栈的基本操作包括入栈（Push）和出栈（Pop）操作。入栈操作将一个元素放入栈顶，出栈操作将栈顶元素删除并返回。栈还可以进行查看栈顶元素（Top）和判断栈是否为空（IsEmpty）等操作。

栈的应用非常广泛，比如函数调用、表达式求值、括号匹配等。在函数调用中，每个函数的调用过程都可以看作是一个栈帧，函数调用结束后，栈帧被弹出，程序继续运行。在表达式求值中，中缀表达式首先被转换为后缀表达式，然后使用栈来进行求值。在括号匹配中，可以使用栈来判断左右括号是否匹配。

栈可以使用数组或链表来实现。如果使用数组来实现栈，需要预先分配一定的内存空间，当栈满时需要重新分配更大的空间。如果使用链表来实现栈，可以动态地添加或删除节点，不需要预先分配内存空间。

栈的操作的时间复杂度通常为O(1)，因为所有操作都是在栈顶进行的，不需要遍历整个栈。但是，如果使用数组实现栈时，当栈满时需要重新分配更大的空间，这会带来额外的开销。

代码实现

public class Stack<V> {
    private int maxSize;
    private int top;
    private V[] array;
    private int currentSize;

    @SuppressWarnings("unchecked")
    public Stack(int maxSize) {
        this.maxSize = maxSize;
        this.top = -1; 
        array = (V[]) new Object[maxSize];
        this.currentSize = 0;
    }

    public int getCurrentSize() {
        return currentSize;
    }

    public int getMaxSize() {
        return maxSize;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }

    public V top() {
        if (isEmpty())
            return null;
        return array[top];
    }

    public void push(V value) {
        if (isFull()) {
            System.err.println("Stack is Full!");
            return;
        }
        array[++top] = value; 
        currentSize++;
    }

    public V pop() {
        if (isEmpty())
            return null;
        currentSize--;
        return array[top--]; 
    }

}