栈（先进后出表）

一、什么是栈

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

二、定义栈接口

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

 1public interface IStack<T> extends MyList<T> {
 2    /**
 3     * 元素入栈
 4     */
 5    void push(T e);
 6
 7    /**
 8     * 弹出栈顶
 9     */
10    T pop();
11
12    /**
13     * 是否空栈
14     */
15    boolean empty();
16
17    /**
18     * 栈内元素个数
19     */
20    @Override
21    int getSize();
22
23    /**
24     * 查看栈顶元素，不弹出
25     */
26    T peek();
27}

三、栈的实现

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

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

1、入栈

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

1    @Override
2    public void push(T e) {
3        super.add(e);
4    }

2、出栈

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

 1    @Override
 2    public T pop() {
 3        if (size <= 0) {
 4            // 如果没有元素直接抛异常
 5            throw new EmptyStackException();
 6        }
 7        // 获取链表尾部结点即栈顶元素
 8        ListNode<T> the = last.pre;
 9        T res = the.data;
10        // 将链表尾部结点的前面结点作为尾部结点
11        the.pre.next = last;
12        // 重新设置尾部哑元的指针
13        last.pre = the.pre;
14        the.next = null;
15        the.pre = null;
16        size--;
17        return res;
18    }

3、其他方法

  MyStack 类完整的代码如下：

 1public class MyStack<T> extends DoubleLinkedList<T> implements IStack<T> {
 2    @Override
 3    public void push(T e) {
 4        super.add(e);
 5    }
 6
 7    @Override
 8    public T pop() {
 9        if (size <= 0) {
10            // 如果没有元素直接抛异常
11            throw new EmptyStackException();
12        }
13        // 获取链表尾部结点即栈顶元素
14        ListNode<T> the = last.pre;
15        T res = the.data;
16        // 将链表尾部结点的前面结点作为尾部结点
17        the.pre.next = last;
18        // 重新设置尾部哑元的指针
19        last.pre = the.pre;
20        the.next = null;
21        the.pre = null;
22        size--;
23        return res;
24    }
25
26    @Override
27    public boolean empty() {
28        return getSize() == 0;
29    }
30
31    @Override
32    public T peek() {
33        if (size <= 0) {
34            throw new EmptyStackException();
35        }
36        return last.pre.data;
37    }
38}

四、关于栈的练习题

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

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

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

 1public static boolean isPalindrome(ListNode<Integer> head) {
 2        if (head == null) {
 3            return false;
 4        }
 5        // 如果只有一个元素直接返回 true
 6        if (head.next == null) {
 7            return true;
 8        }
 9        // 定义两个指针，慢指针一次移动一个节点，快指针一次移动两个节点
10        // 当快指针指向结尾时，慢指针指向链表的中间
11        ListNode<Integer> slower = head;
12        ListNode<Integer> faster = head;
13        // 创建一个栈用于存储链表的前半部分
14        Stack<Integer> stack = new Stack<>();
15        // 判断链表的长度的奇偶数 true 为奇数
16        boolean isOdd = true;
17        while (faster != null && faster.next != null) {
18            // 每次将慢指针的元素压入栈底
19            stack.push(slower.data);
20            slower = slower.next;
21            faster = faster.next.next;
22            if (faster == null) {
23                isOdd = false;
24            }
25        }
26        // 奇数个节点，slower 还要 next 一下
27        if (isOdd) {
28            slower = slower.next;
29        }
30        while (!stack.empty() && slower!=null) {
31            // 每次将栈顶元素弹出与慢指针指向的后半链表的节点比较，不相等则不是回文
32            if (!stack.pop().equals(slower.data)) {
33                return false;
34            } else {
35                slower = slower.next;
36            }
37        }
38        return true;
39    }

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

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

 1/**
 2     * 这个栈用于存储最小值
 3     */
 4    private MyQueue<T> min=new MyQueue<T>();
 5
 6    public T min(){
 7        // 每次获得栈顶元素
 8        return min.peek();
 9        // 每次添加元素时，和这个栈顶元素做比较，小于等于则存储
10        // 每次弹出元素时，和这个栈顶元素做比较，等于则也将该栈中的元素弹出
11    }

3、栈排序

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

例子：

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

 1    public static ArrayList<Integer> twoStackSort(int[] numbers) {
 2        Stack<Integer> source = new Stack<>();
 3        // 第一个元素作为栈顶进行初始化栈
 4        for (int i = numbers.length - 1; i >= 0; i--) {
 5            source.push(numbers[i]);
 6        }
 7        // 对栈进行排序
 8        Stack<Integer> target = sortToTarget(source);
 9        ArrayList<Integer> list = new ArrayList<>();
10        // 第一个元素作为栈顶
11        while (!target.empty()) {
12            list.add(target.pop());
13        }
14        return list;
15    }
16
17
18    private static Stack<Integer> sortToTarget(Stack<Integer> source) {
19        // 创建一个临时栈
20        Stack<Integer> target = new Stack<>();
21        // 遍历原栈进行排序
22        while (!source.empty()) {
23            // 揭开盖子 即弹出栈顶元素
24            int v1 = source.pop();
25            // 如果临时栈为空则直接压入
26            if (!target.empty()) {
27                // 取出临时栈的栈顶元素
28                int v2 = target.peek();
29                if (v1 < v2) {
30                    // 如果盖子小，把大的先回收
31                    source.push(target.pop());
32                    // 直到有盖子的容身之所
33                    while (!target.empty() && v1 < target.peek()) {
34                        source.push(target.pop());
35                    }
36                }
37            }
38            // 把盖子放入临时栈中
39            target.push(v1);
40        }
41        return target;
42    }