Java - 数据结构-栈

1. 定义

栈（stack），是一种线性存储结构，它有以下几个特点：

• 1. 栈中数据是按照"后进先出（LIFO, Last In First Out）"方式进出栈的。
• 2. 向栈中添加/删除数据时，只能从栈顶进行操作。

栈通常包括的三种操作：push、peek、pop。

• push -- 向栈中添加元素。
• peek -- 返回栈顶元素。
• pop -- 返回并删除栈顶元素的操作。

2. 简单实现

public class GeneralArrayStack<T> {

    private static final int DEFAULT_SIZE = 12;
    private T[] mArray;
    private int count;

    public GeneralArrayStack(Class<T> type) {
        this(type, DEFAULT_SIZE);
    }

    public GeneralArrayStack(Class<T> type, int size) {
        // 不能直接使用mArray = new T[DEFAULT_SIZE];
        mArray = (T[]) Array.newInstance(type, size);
        count = 0;
    }

    // 将val添加到栈中
    public void push(T val) {
        mArray[count++] = val;
    }

    // 返回“栈顶元素值”
    public T peek() {
        return mArray[count - 1];
    }

    // 返回“栈顶元素值”，并删除“栈顶元素”
    public T pop() {
        T ret = mArray[count - 1];
        mArray[count - 1] = null; /* to let gc do its work */
        count--;
        return ret;
    }

    // 返回“栈”的大小
    public int size() {
        return count;
    }

    // 返回“栈”是否为空
    public boolean isEmpty() {
        return size() == 0;
    }

    // 打印“栈”
    public void printArrayStack() {
        if (isEmpty()) {
            System.out.printf("stack is Empty\n");
        }

        System.out.printf("stack size()=%d\n", size());

        int i = size() - 1;
        while (i >= 0) {
            System.out.println(mArray[i]);
            i--;
        }
    }
}

测试:

public static void main(String[] args) {
    GeneralArrayStack<String> stack = new GeneralArrayStack<>(String.class, 5);

    for (int i = 0; i < 5; i++) {
        stack.push("this is " + i);
    }

    System.out.println("栈顶:" + stack.peek());

    String pop = stack.pop();
    System.out.println("取出的栈顶元素:" + pop);

    stack.printArrayStack();
}

结果:

栈顶:this is 4
取出的栈顶元素:this is 4
stack size()=4
this is 3
this is 2
this is 1
this is 0