栈简介 Stack

栈的本质

栈也是一种数据呈线性排列的数据结构，不过在这种结构中，我们只能访问最新添加的数据。

⨳ 栈就像是一摞书，拿到新书时我们会把它放在书堆的最上面，取书时也只能从最上面的新书开始取。

⨳ 栈也像一摞叠在一起的盘子，我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。

⨳ 栈也像子弹夹，子弹夹只有一个口，最新压入的子弹，也是最开始射出的子弹。

总之，后进者先出（Last In First Out，简称 LIFO），就是典型的“栈”结构。

前文讲了数组和链表这两种不同的线性存储结构，而栈既可以用数组实现（顺序栈），也可以用链表实现（链式栈）。

栈主要 API 如下：

⨳ void push(E)：入栈操作，向栈顶添加元素

⨳ E pop()：出栈操作，从栈顶弹出元素

⨳ E peek()：查看栈顶元素

相比数组和链表，栈就是个阉割版本，那我直接使用数组或者链表不就好了吗？为什么还要用这个“操作受限”的“栈”呢？

因为数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，比较容易出错（单一职责）。

下面就分别使用数组和链表实现一个栈。

顺序栈 ArrayStack

import com.cango.array.IntArray; // 数组篇讲的代码

public class IntArrayStack {

    IntArray array ;

    public IntArrayStack(int capacity){
        array = new IntArray(capacity);
    }

    public IntArrayStack(){
        array = new IntArray();
    }


    public void push(int e){
        array.add(array.getSize(),e);
    }


    public int pop(){
        return array.remove(array.getSize()-1);
    }


    public int peek(){
        return array.get(array.getSize()-1);
    }
    
}

看完代码你可能会说，就这？对，将数组操作阉割一下就是栈。

如果 IntArray 支持动态扩容，用 IntArray 实现的栈也会支持动态扩容，多方便。

从上代码可以看出，用数组实现栈最好让数组尾部作为栈顶，因为栈只能操作栈顶的元素，对应到数组，就是只处理数组尾部的元素，不涉及数组其他元素的搬移。

链式栈 LinkedStack

将数组操作阉割一下就是顺序栈，接着将链表阉割一下实现链式栈：

import com.cango.list.IntList;

public class IntLinkedStack {

    IntList list;

    public IntLinkedStack(){
        list = new IntList();
    }
    
    public void push(int e){
        list.add(0,e);
    }
    
    public int pop(){
        return list.remove(0);
    }
    
    public int peek(){
        return list.get(0);
    }

}

单向链表适合让链表头部作为栈顶，因为链表对头部节点的增删查最快。

Stack VS Deque

package java.util;

/**
 * The <code>Stack</code> class represents a last-in-first-out
 * (LIFO) stack of objects. It extends class <tt>Vector</tt> with five
 * operations that allow a vector to be treated as a stack. The usual
 * <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
 * method to <tt>peek</tt> at the top item on the stack, a method to test
 * for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt>
 * the stack for an item and discover how far it is from the top.
 * <p>
 * When a stack is first created, it contains no items.
 *
 * <p>A more complete and consistent set of LIFO stack operations is
 * provided by the {@link Deque} interface and its implementations, which
 * should be used in preference to this class.  For example:
 * <pre>   {@code
 *   Deque<Integer> stack = new ArrayDeque<Integer>();}</pre>
 *
 * @author  Jonathan Payne
 * @since   JDK1.0
 */
public
class Stack<E> extends Vector<E>

这是 Java 版本的 Stack，从描述上看，官方推荐使用 Deque 代替 Stack 。

为啥呢？

Stack 类对 push、pop 方法实现很好呀，原因就是它是继承 Vector ，而不是组合 Vector （Vector 是个线程安全的数组封装），这就导致 Stack 不仅仅有 push、pop 方法，数组相关操作方法都有，Stack 存在的意义就是屏蔽多余的操作，现在 Stack 操作这么多，怎能不让开发者迷惑。

Java 官方推荐的写法是使用 Deque 接口：

 Deque<Integer> stack = new ArrayDeque<Integer>();}

Deque 是双端队列的意思，也就是说可以在队列两头操作元素，那我只用一头进行插入和删除，这不就是栈了嘛。

Deque 还是暴露了多余的操作呀，是的，哪能这么办，重新构造 Stack 类吗？原来的项目怎么办？

妥协的方法就是，选择一个比较符合栈操作的类，也就是 Deque。