数据结构学习笔记 - 03 栈

介绍

栈对应的操作是数组的子集。

对于栈的理解，其实它就是一个数组，只不过只能从一端添加元素，也只能从这一端删除元素。

栈是一种后进先出的数据结构（LIFO）。

栈的应用

1. 编辑器中的 Undo 操作，通常就是使用一个栈来维护的。
2. 程序调用的系统栈。比如我们执行 A 函数，执行到第 2 行后其调用了 B 函数，那么 A 函数执行就暂停，开始调用 B 函数，此时就有一个栈来维护这个调用过程，类似 A2 就被 push 到栈里，记录 A 函数当前执行到第 2 行。类似的 B3 也可能被 push 到栈中去执行 C 函数，C 函数执行完了继续执行 B，那么栈就会执行一个 pop 操作。通过栈顶的记录，计算机就找到了继续执行哪个函数以及执行到哪里了。
3. 编辑器中的括号匹配。

栈的实现

使用 Java 进行实现。我们将栈定义为一个接口。

public interface Stack<E> {

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

数组栈（使用之前实现的动态数组结构）：

/**
 * ArrayStack
 * 
 * 这个类基于我们自己实现的动态数组来实现「栈」这个接口。
 * 
 * 这个栈中的五个方法复杂度：
 * void push(E)        O(1) 均摊
 * E pop()             O(1) 均摊
 * E peek()            O(1)
 * int getSize()       O(1)
 * boolean isEmpty()   O(1)
 * 
 */
public class ArrayStack<E> implements Stack<E> {

    private 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();
    }

    /**
     * 查看实现这个栈的这个动态数组当前的容积。
     * 这个方法不是栈特有的，因此栈接口没有定义这个方法，但是我们是使用数组实现的这个栈，可以有这个方法供用户查看。
     */
    public int getCapacity() {
        return array.getCapacity();
    }

    /**
     * 入栈。
     */
    @Override
    public void push(E e) {
        array.addLast(e);
    }

    /**
     * 出栈。
     */
    @Override
    public E pop() {
        return array.removeLast();
    }

    /**
     * 查看栈顶元素。
     */
    @Override
    public E peek() {
        return array.getLast();
    }

    @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();
    }
}

链表栈（会使用之后实现的链表结构）：

/**
 * LinkedListStack
 * 使用链表来实现一个栈的数据结构。
 * 
 * 这个栈中的五个方法复杂度：
 * void push(E)        O(1)
 * E pop()             O(1)
 * E peek()            O(1)
 * int getSize()       O(1)
 * boolean isEmpty()   O(1)
 * 
 */
public class LinkedListStack<E> implements Stack<E> {
    private LinkedList<E> list;

    public LinkedListStack() {
        list = new LinkedList<>();
    }

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

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

    @Override
    public void push(E e) {
        list.addFirst(e);
    }

    @Override
    public E pop() {
        return list.removeFirst();
    }

    @Override
    public E peek() {
        return list.getFirst();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

        res.append("Stack: top ");
        res.append(list);
        return res.toString();
    }
}