栈

栈

栈的定义

栈是 后入先出（LIFO） 的数据结构，入栈通常使用 push 操作，往栈中插入数据到栈底，出栈使用 pop 操作，从栈顶删除数据。

栈的实现

栈常用的实现方式是通过动态数组来实现的，在 Java 和 Kotlin 中也内置了栈库 Stack，但是 Stack 已经不推荐使用了。

不推荐使用 Stack 实现栈

性能低

性能低是因为 Stack 继承自 Vector， 而 Vector 在每个方法中都加了锁，如下所示：

// ...
public synchronized void trimToSize() { }
public synchronized void ensureCapacity(int minCapacity) {  }
public synchronized void setSize(int newSize) {  }
public synchronized int capacity() {  }
public synchronized int size() {  }
public synchronized boolean isEmpty() {  }
// ...

由于需要兼容老的项目，很难在原有的基础上进行优化，因此 Vector 就被淘汰掉了，使用 ArrayList 和 CopyOnWriteArrayList 来代替，如果在非线程安全的情况下可以使用 ArrayList，线程安全的情况下可以使用 CopyOnWriteArrayList 。

破坏了原有的数据结构

栈的定义是在一端进行 push 和 pop 操作，除此之外不应该包含其他 入栈和出栈 的方法，但是 Stack 继承自 Vector，使得 Stack 可以使用父类 Vector 公有的方法

val stack = Stack<Int>()
stack.push(6)
stack.add(1,10)
stack.removeAt(1)
stack.pop()
stack.addAll(arrayListOf())

除了调用 push() 和 pop() 方法之外，还可以调用 addXXX() 、 removeXXX() 等等方法，但是这样会破坏栈原有的结构。所以对于栈的数据结构，不应该有可以在任何位置添加或者删除元素的能力。

JDK 推荐使用 Deque 接口替换栈

栈的相关操作应该由 Deque 接口来提供，推荐使用 Deque 这种数据结构，以及它的子类，例如 ArrayDeque。

使用 Deque 接口来实现栈的功能有什么好处：

• 速度比 Stack 快

作为栈使用时可能比 Stack 快，作为队列使用时可能比 LinkedList 快。因为原来的 Java 的 Stack 继承自 Vector，而 Vector 在每个方法中都加了锁，而 Deque 的子类 ArrayDeque 并没有锁的开销。

• 屏蔽掉无关的方法

原来的 Java 的 Stack，包含了在任何位置添加或者删除元素的方法，这些不是栈应该有的方法，所以需要屏蔽掉这些无关的方法。

大神不推荐使用 Stack（ArrayDeque 代替 Stack）

• Java Stack vs Deque

在大型的项目中不建议直接使用 Stack，也不推荐使用 ArrayDeque 代替 Stack。
我们可以基于 ArrayDeque 封装一个真正的栈，只允许在一端做插入和删除操作，如下所示。

interface Stack<E> {
    fun push(e: E)
    fun pop(): E?
    fun peek(): E?
    fun size(): Int
    fun empty(): Boolean
}

class ArrayStack<E> : Stack<E> {

    private val deque = ArrayDeque<E>()

    override fun push(e: E) = deque.push(e)

    override fun pop(): E? = deque.poll()

    override fun peek(): E? = deque.peek()

    override fun size() = deque.size

    override fun empty(): Boolean = deque.isEmpty()

}