栈（先进后出表）

一、什么是栈

  栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
  栈是一个元素先进后出的数据结构，我们可以把栈结构理解成手枪的弹夹。入栈就是就是将子弹压入弹夹中，后压的子弹总是在先压的子弹上面；而出栈就是开枪，先打出的子弹总是弹夹最上放的子弹，即后压入的子弹；所以先压进的子弹总是最后打出。

二、定义栈接口

  栈是一种特殊的线性表，所以栈的接口也继承我们之前定义的 MyList 接口，IStack 接口包含一些栈的基本操作。

public interface IStack<T> extends MyList<T> {
    /**
     * 元素入栈
     */
    void push(T e);

    /**
     * 弹出栈顶
     */
    T pop();

    /**
     * 是否空栈
     */
    boolean empty();

    /**
     * 栈内元素个数
     */
    @Override
    int getSize();

    /**
     * 查看栈顶元素，不弹出
     */
    T peek();
}

三、栈的实现

  数据的存储结构有两种：顺序存储结构和链式存储结构。堆栈只能对栈首进行操作（入栈/出栈），所以底层的存储结构用链表比数组更好些。为了方便获取元素的前驱，我们使用双链表来实现栈。我们只需要将栈的实现类继承 DoubleLinkedList 类就可以使用双链表进行存储栈的数据了。（DoubleLinkedList 类是我们上一篇双链表的实现类）

public class MyStack<T> extends DoubleLinkedList<T> implements IStack<T> {
}

1、入栈

  入栈就是向栈的最上方添加元素，等同于向链表末尾添加元素，所以我们只需要调用双链表的 add 方法即可。

    @Override
    public void push(T e) {
        super.add(e);
    }

2、出栈

  出栈包含两个操作：获取栈顶元素并将其删除；也就是获取链尾结点并将其删除。

    @Override
    public T pop() {
        if (size <= 0) {
            // 如果没有元素直接抛异常
            throw new EmptyStackException();
        }
        // 获取链表尾部结点即栈顶元素
        ListNode<T> the = last.pre;
        T res = the.data;
        // 将链表尾部结点的前面结点作为尾部结点
        the.pre.next = last;
        // 重新设置尾部哑元的指针
        last.pre = the.pre;
        the.next = null;
        the.pre = null;
        size--;
        return res;
    }

3、其他方法

  MyStack 类完整的代码如下：

public class MyStack<T> extends DoubleLinkedList<T> implements IStack<T> {
    @Override
    public void push(T e) {
        super.add(e);
    }

    @Override
    public T pop() {
        if (size <= 0) {
            // 如果没有元素直接抛异常
            throw new EmptyStackException();
        }
        // 获取链表尾部结点即栈顶元素
        ListNode<T> the = last.pre;
        T res = the.data;
        // 将链表尾部结点的前面结点作为尾部结点
        the.pre.next = last;
        // 重新设置尾部哑元的指针
        last.pre = the.pre;
        the.next = null;
        the.pre = null;
        size--;
        return res;
    }

    @Override
    public boolean empty() {
        return getSize() == 0;
    }

    @Override
    public T peek() {
        if (size <= 0) {
            throw new EmptyStackException();
        }
        return last.pre.data;
    }
}

四、关于栈的练习题

1、判断链表是不是回文链表

  所谓回文链表就是顺序读和逆序读的结果一样，如果链表中的结点没有指向前驱，我们可以用栈结构来实现。

  定义两个指针，慢指针一次移动一个节点，快指针一次移动两个节点。当快指针指向结尾时，慢指针指向链表的中间，循环也就结束了。在移动的过程中，将慢指针指向的元素全部入栈，然后继续移动慢指针和栈中的元素进行比较即可。注意：对链表长度的奇偶性进行处理。

public static boolean isPalindrome(ListNode<Integer> head) {
        if (head == null) {
            return false;
        }
        // 如果只有一个元素直接返回 true
        if (head.next == null) {
            return true;
        }
        // 定义两个指针，慢指针一次移动一个节点，快指针一次移动两个节点
        // 当快指针指向结尾时，慢指针指向链表的中间
        ListNode<Integer> slower = head;
        ListNode<Integer> faster = head;
        // 创建一个栈用于存储链表的前半部分
        Stack<Integer> stack = new Stack<>();
        // 判断链表的长度的奇偶数 true 为奇数
        boolean isOdd = true;
        while (faster != null && faster.next != null) {
            // 每次将慢指针的元素压入栈底
            stack.push(slower.data);
            slower = slower.next;
            faster = faster.next.next;
            if (faster == null) {
                isOdd = false;
            }
        }
        // 奇数个节点，slower 还要 next 一下
        if (isOdd) {
            slower = slower.next;
        }
        while (!stack.empty() && slower!=null) {
            // 每次将栈顶元素弹出与慢指针指向的后半链表的节点比较，不相等则不是回文
            if (!stack.pop().equals(slower.data)) {
                return false;
            } else {
                slower = slower.next;
            }
        }
        return true;
    }

2、O(1)获取栈的最小值

  请设计一个栈，支持 min 方法，可返回栈元素中的最小值。时间复杂度必须为 O(1)。再用一个栈存储最小值。

/**
     * 这个栈用于存储最小值
     */
    private MyQueue<T> min=new MyQueue<T>();

    public T min(){
        // 每次获得栈顶元素
        return min.peek();
        // 每次添加元素时，和这个栈顶元素做比较，小于等于则存储
        // 每次弹出元素时，和这个栈顶元素做比较，等于则也将该栈中的元素弹出
    }

3、栈排序

  请编写一个程序，按升序多栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。给定一个 int[] numbers，其中第一个元素为栈顶，请返回排序后的栈，请注意这是一个栈，意味着排序过程你只能访问第一个元素。

例子：

• 输入：[1, 2, 3, 4, 5]
• 输出：[5, 4, 3, 2, 1]

    public static ArrayList<Integer> twoStackSort(int[] numbers) {
        Stack<Integer> source = new Stack<>();
        // 第一个元素作为栈顶进行初始化栈
        for (int i = numbers.length - 1; i >= 0; i--) {
            source.push(numbers[i]);
        }
        // 对栈进行排序
        Stack<Integer> target = sortToTarget(source);
        ArrayList<Integer> list = new ArrayList<>();
        // 第一个元素作为栈顶
        while (!target.empty()) {
            list.add(target.pop());
        }
        return list;
    }


    private static Stack<Integer> sortToTarget(Stack<Integer> source) {
        // 创建一个临时栈
        Stack<Integer> target = new Stack<>();
        // 遍历原栈进行排序
        while (!source.empty()) {
            // 揭开盖子 即弹出栈顶元素
            int v1 = source.pop();
            // 如果临时栈为空则直接压入
            if (!target.empty()) {
                // 取出临时栈的栈顶元素
                int v2 = target.peek();
                if (v1 < v2) {
                    // 如果盖子小，把大的先回收
                    source.push(target.pop());
                    // 直到有盖子的容身之所
                    while (!target.empty() && v1 < target.peek()) {
                        source.push(target.pop());
                    }
                }
            }
            // 把盖子放入临时栈中
            target.push(v1);
        }
        return target;
    }