玩转数据结构之栈

0. 序言

栈是一种线性结构，相比数组， 栈对应的操作是数组的子集：只能从一端添加元素，也只能从一端取出元素，这一端为栈顶。

这篇文章会用之前的数组类Array实现一个底层为数组的栈ArrayStack。建议在阅读本篇文章之前，先阅读关于动态数组类Array这篇文章：https://www.jianshu.com/p/02bbc13b5e5f 当然对数组了解比较深入的，可以直接阅读本篇。

1. 特点

• 后进先出（Last In First Out FIFO）

  
  栈

2. 应用

• 无处不在的Undo操作（撤销）

• 程序调用的系统栈

  
  系统栈
  

  ① A调用B，B进栈
  ② B调用C，C进栈
  ③ C执行完，C弹栈
  ④ 栈顶是B，接着执行B，B结束，B弹栈
  ⑤ 栈中无元素，接着执行A，直至结束。

3. 基本实现

Stack<E>

• void push(E)：入栈
• E pop()：出栈
• E peek()：查看栈顶元素
• int getSize()：获取栈中元素个数
• boolean isEmpty()：判断栈中是否有元素

① 从用户的角度来看，支持这些操作即可。
② 具体底层实现，用户不关心
③ 实际底层有多种实现方式。

4. 设计

基于数组的栈

定义一个ArrayStack<E>，实现接口Stack<E>。

5. 代码实现

• 定义接口Stack<E>

public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
}

• 定义实现类ArrayStack<E>

public class ArrayStack<E> implements Stack<E> {

    Array<E> array;

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

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

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

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

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

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

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

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

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

基于自定义的数组类Array，实现的栈的功能，以下是测试代码：

public class Test_ArrayStack {
    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();
        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, 3] top

模拟了出栈，结果证明代码正确。

6. 栈的复杂度分析

栈的复杂度分析
ArrayStack是基于动态数组实现的，所以会自动扩容和缩容。其中入栈和出栈操作，可能会导致扩容和缩容，通过均摊复杂度分析，其时间复杂度为O(1)。
对均摊复杂度分析不了解的，可以跳转阅读：https://www.jianshu.com/p/59f380c6ffcd

7. 后续

如果大家喜欢这篇文章，欢迎点赞！
如果想看更多 数据结构 方面的文章，欢迎关注!