Java栈的实现相关笔记

1、集合的一些基础概念

Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection 接口又有 3 种子类型，List、Set 和 Queue，再下面是一些抽象类，最后是具体实现类，常用的有 、、、 等等。

集合框架是一个用来代表和操纵集合的统一架构。所有的集合框架都包含如下内容：

接口：是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口，是为了以不同的方式操作集合对象 实现（类）：是集合接口的具体实现。从本质上讲，它们是可重复使用的数据结构，例如：ArrayList、LinkedList、HashSet、HashMap。 算法：是实现集合接口的对象里的方法执行的一些有用的计算，例如：搜索和排序。这些算法被称为多态，那是因为相同的方法可以在相似的接口上有着不同的实现

2、Queue

public interface Queue<E>
extends <E>

设计用于在处理之前保留元素的集合。 除了基本的Collection之外，队列还提供额外的插入，提取和检查操作。 这些方法中的每一种都有两种形式：如果操作失败，则抛出一个异常，另一种返回一个特殊值（ null或false ，具体取决于操作）。 插入操作的后一种形式专门设计用于容量限制的Queue实现；在大多数实现中，插入操作不能失败。

Summary of Queue methods:

Throws exception Returns special value

Insert add() offer() Remove remove() poll() Examine element() peek()

3、Deque

public interface Deque<E>
extends <E>

支持两端元素插入和移除的线性集合。 名称deque是“双端队列”的缩写，通常发音为“deck”。 大多数Deque实现对它们可能包含的元素的数量没有固定的限制，但是该接口支持容量限制的deques以及没有固定大小限制的deques。

该界面定义了访问deque两端元素的方法。 提供了插入，移除和检查元素的方法。 这些方法中的每一种存在两种形式：如果操作失败，则会抛出异常，另一种方法返回一个特殊值（ null或false ，具体取决于操作）。 插入操作的后一种形式专门设计用于容量限制的Deque实现; 在大多数实现中，插入操作不能失败。

4、栈的实现

4.1、java不建议stack类实现栈，建议用deque类实现栈。

问题在于stack类继承于vector类：

（1）Vector作为动态数组，因为要保证线程安全，效率比较低，基本已经弃用；即使需要并发编程，自Java 5以后，也推荐使用java.util.concurrent包。

（2）Vector作为动态数组，有能力在数组中的任何位置添加或删除元素，Stack也有了这样的能力，破坏了栈这种数据结构的封装。因为兼容性的问题，使用老版本Java的程序将在新的Java环境下无法执行，所以Java并没有删去stack类，只是不建议使用。

注：虽然Java官方推荐使用Deque接口实现stack，但是这样的stack也破坏了封装性，并不安全。

4.2、LinkedList类和ArrayDeque类都可以实现栈

二者比较可以参考这篇文章：