站不住的栈：1.青铜挑战——理解手写栈

本关主要研究的是一个很重要的数据结构 —— 栈。

1. 栈基础知识

1.1. 栈的特征

栈和队列都是比较特殊的线性表，又称之为访问受限的线性表。栈是很多表达式，符号等运算的基础，也是递归的底层实现，理论上递归能做的题目，栈都可以，只是有限问题用栈会非常复杂。

栈底层实现仍然是链表或者顺序表，栈和线性表的最大区别是数据的存取的操作被限制了，其插入和删除只允许在线性表的一段进行。一般而言，把允许操作的一端称为栈顶（Top），不可操作的一端称为栈底（Bottom），同时把插入元素的操作称为入栈（Push），把删除元素的操作称为出栈（Pop）。如果栈中没有任何元素，则称为空栈，栈的数据结构如下图所示：

1.2. 栈的操作

栈的常用操作主要有：

• push （E）: 增加一个元素 E
• pop：弹出栈顶的元素 E
• peek（）：显示栈顶元素，但是不出栈
• empty（）：判断栈是否为空

我们在设计自己的栈的时候，不管用数组还是链表，都要实现以上几个方法。

如何向测试一下自己对于栈的理解，只需要做下这道题就可以了：入栈顺序为 1234，所有可能得出栈序列是什么？

这个题是什么意思呢？比如说，我先让 1 和 2 出栈，然后 2 和 1 出栈，然后再让 3 和 4 入栈后再依次出栈，这样就可以得到序列 2143。4 中元素的全排列一共有 24 种，栈要求符合先进后出，后进先出（FILO）， 按照此标准，可以衡量排除后得到以下序列：

1234 √ 1243 √ 1324 √ 1342 √ 1423 × 1432 √

2134 √ 2143 √ 2314 √ 2341 √ 2413 × 2431 √

3124 × 3142 × 3214 √ 3241 √ 3412 × 3421 √

4123 × 4132 × 4213 × 4231 × 4312 × 4321 √

14 种可能，10 种不可能，如上图所示。

1.3. Java 中的栈

Java 的 util 就提供了栈 Stack 类，所以使用并不复杂，看以下这一个例子就可以了:

public class MainTest {
    public static void main(String[] args) {
        // 栈的构建
        Stack stack = new Stack();

        // 压栈
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 查看栈顶元素
        System.out.println("栈顶元素为:" + stack.peek());
        System.out.println("--------------------------------");

        while (!stack.empty()) {
            // 对于栈顶元素进行显示,但是不出栈
            System.out.println("栈顶元素:" + stack.peek());
            // 出栈并且显示
            System.out.println("出栈元素:" + stack.pop());
        }

    }
}

2. 基于数组实现栈

2.1. 理论

再看具体内容之前，先补充一点， top 有的地方直接指向栈顶元素，有的地方直接指向栈顶往上的一个空单位，这个根据题目要求设计就好了，如果是面试的时候就直接问面试官，top 指向哪里，本文采用指向栈顶的空位置。

如果要自己实现，可以有数组，链表和 Java 提供的 LinkList 三种基本方式，我们都看一下。

采用顺序表实现的栈，内部以数组为基础，实现对元素的存取操作。在应用中还要注意每次入栈前先判断栈的容量是否够用，如果不够用，可以进行扩容。

入栈过程如下：

出栈过程如图所示：

2.2. 实操

top 先将栈顶元素取出，然后执行 top-- ,实现的完整代码如下：

public class MyStackByArray {
    /**
     * 实现栈的数组
     */
    private Object[] stack;

    /**
     * 栈顶元素
     */
    private int top;

    public MyStackByArray() {
        // 初始化栈的容量为 10
        stack = new Object[10];
    }

    /**
     * 判断栈是否为空
     */
    public boolean isEmpty() {
        return top == 0;
    }

    /**
     * 返回栈顶元素，但是不出栈
     */
    public T peek() {
        T t = null;
        if (top > 0) {
            t = (T) stack[top - 1];
        }
        return t;
    }

    /**
     * 入栈
     *
     * @param t
     */
    public void push(T t) {
        if (t == null) {
            System.out.println("插入元素不能为空");
            return;
        }
        extendCapacity(top + 1);
        stack[top] = t;
        top++;
        System.out.println("数据 " + t + " 插入数据成功");
    }

    /**
     * 出栈
     *
     * @return 出栈元素
     */
    public T pop() {
        T t = peek();
        if (top > 0) {
            stack[top - 1] = null;
            top--;
        }
        return t;
    }

    /**
     * 扩大容量
     */
    public void extendCapacity(int size) {
        int len = stack.length;
        if (size > len) {
            // 每次扩大 50 %
            size = size * 3 / 2 + 1;
            stack = Arrays.copyOf(stack, size);
        }
    }
}

2.3. 测试

public class MyStackByArrayTest {
    @Test
    public void testStack() {
        MyStackByArray stack = new MyStackByArray();

        System.out.println("栈顶元素:" + stack.peek());
        System.out.println(stack.isEmpty());
        stack.push("Java");
        stack.push(null);
        stack.push("Python");
        stack.push("C++");

        System.out.println("----------------");
        while (!stack.isEmpty()) {
            System.out.println("栈顶元素为:" + stack.peek());
            System.out.println("出栈元素为:" + stack.pop());
        }

    }
}

3. 基于链表实现栈

3.1. 原理

链表其实可以使用栈实现，然后插入和删除都在头结点进行，如下图所示

在链表那一章，我们介绍过没有虚拟节点时对链表头元素进行插入和删除操作的方法，而与这里基于链表实现栈完全一致。

3.2. 实操

代码实现也不复杂，完整实现如下：

public class ListStack {
    private class Node {
        public T data;
        public Node next;
    }

    public Node head;

    /**
     * 构造函数初始化指针
     */
    public ListStack() {
        head = null;
    }

    /**
     * 入栈
     *
     * @param t
     */
    public void push(T t) {
        if (t == null) {
            System.out.println("插入元素不能为空");
        }
        // 如果头结点为空
        if (head == null) {
            head = new Node();
            head.data = t;
            head.next = null;
        } else {
            // 创建一个临时节点，用于存放头结点
            Node temp = head;
            head = new Node();
            head.data = t;
            head.next = temp;
        }
    }

    /**
     * 出栈
     */
    public T pop() {
        if (head == null) {
            System.out.println("头结点为空，返回元素为 null .");
            return null;
        }
        T temp = head.data;
        head = head.next;
        return temp;
    }

    /**
     * 获取栈顶元素
     */
    public T peek() {
        if (head == null) {
            System.out.println("头结点元素为空");
            return null;
        }
        T temp = head.data;
        return temp;
    }

    /**
     * 栈空
     */
    public boolean isEmpty() {
        if (head == null) {
            return true;
        }
        return false;
    }
}

3.3. 测试

public class ListStackTest {

    @Test
    public void testListStack() {
        ListStack stack = new ListStack();
        System.out.println("链表是否为空:" + stack.isEmpty());
        stack.push("Java");
        stack.push(null);
        stack.push("Python");
        stack.push("C++");
        stack.push("C");
        System.out.println("栈顶元素:"+stack.peek());
        System.out.println("---------------------------");
        while (!stack.isEmpty()) {
            System.out.println("出栈元素:" + stack.pop());
        }
    }

}

4. 通关文牒

本关是栈的基本结构，基本原理，主要说的是 java 中栈的实现以及数组和链表两种创建栈的方式。