ArrayStack 数组栈

栈的实现

栈的实现有多种方式，一种是通过动态数组, 另一种是通过链表。

为了增强代码的复用性和解耦，我们不从头实现一个栈。而是定义一个栈的接口, 动态数组或者链表，去实现这个接口即可。而事实上，通过我们前面所学的Array来实现一个栈是非常简单的。

public interface Stack<E>{

    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();

}

push()方法 将一个元素入栈。peek() 方法返回栈顶的元素，但是不取出。pop()方法取出栈顶元素并返回。其他两个方法与Array相同, 这里就不做解释了。

随后我们定义一个ArrayStack 类去实现 Stack 接口即可。

public class ArrayStack<E> implements Stack<E> {
    Array<E> array;

    public ArrayStack(int capacity) {
        this.array = new Array<E>(capacity);
    }

    public ArrayStack() {
        this.array = new Array<E>();
    }

    @Override
    public int getSize() {
        return this.array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return this.array.isEmpty();
    }

    @Override
    public void push(E e) {
        this.array.addLast(e);
    }

    @Override
    public E pop() {
        return this.array.removeLast();
    }

    @Override
    public E peek() {
        return this.array.getLast();
    }

    public int getCapacity(){
        return this.array.getCapacity();
    }

    @Override
    public String toString() {
        StringBuilder res=new StringBuilder();
        res.append("Stack : ");
        res.append(" [ ");
        for (int i = 0; i < this.array.getSize(); i++) {
            res.append(this.array.get(i));
            if (i!=array.getSize()-1){
                res.append(", ");
            }
        }
        res.append(" ] top");
        return res.toString();
    }

    public static void main(String[] args) {
        ArrayStack<Integer> stack=new ArrayStack<>();
        for (int i = 0; i < 5; i++) {
            stack.push(i);
            System.out.println(stack);
        }

        stack.pop();
        stack.pop();
        System.out.println(stack);
    }
}

可以看出，所有栈的操作, 都可以直接调用Array 的方法进行实现。

测试一下

最后我们在 main 方法内进行测试。我们依次向栈内push 数字0到5， 随后打印输出，再pop两次，再次输出.

public static void main(String[] args) {
    ArrayStack<Integer> stack=new ArrayStack<>();
    for (int i = 0; i < 5; i++) {
        stack.push(i);
        System.out.println(stack);
    }

    stack.pop();
    stack.pop();
    System.out.println(stack);
}

输出结果:

Stack :  [ 0 ] top
Stack :  [ 0, 1 ] top
Stack :  [ 0, 1, 2 ] top
Stack :  [ 0, 1, 2, 3 ] top
Stack :  [ 0, 1, 2, 3, 4 ] top
Stack :  [ 0, 1, 2 ] top