java三篇博客转载 详解-vector,stack,queue,deque

时间：2022-10-22 14:24:44

博客一：转载自http://shmilyaw-hotmail-com.iteye.com/blog/1825171

java stack的详细实现分析

简介

我们最常用的数据结构之一大概就是stack了。在实际的程序执行，方法调用的过程中都离不开stack。那么，在一个成熟的类库里面，它的实现是怎么样的呢？也许平时我们实践的时候也会尝试着去写一个stack的实现玩玩。这里，我们就仔细的分析一下jdk里的详细实现。

Stack

如果我们去查jdk的文档，我们会发现stack是在java.util这个包里。它对应的一个大致的类关系图如下：

java三篇博客转载 详解-vector,stack,queue,deque

通过继承Vector类，Stack类可以很容易的实现他本身的功能。因为大部分的功能在Vector里面已经提供支持了。

Stack里面主要实现的有一下几个方法：

方法名 返回类型 说明
empty boolean 判断stack是否为空。
peek E 返回栈顶端的元素。
pop E 弹出栈顶的元素
push E 将元素压入栈
search int 返回最靠近顶端的目标元素到顶端的距离。

因为前面我们已经提到过，通过继承Vector，很大一部分功能的实现就由Vector涵盖了。Vector的详细实现我们会在后面分析。它实现了很多的辅助方法，给Stack的实现带来很大的便利。现在，我们按照自己的思路来分析每个方法的具体步骤，再和具体实现代码对比。

empty

从我们的思路来说，如果要判断stack是否为空，就需要有一个变量来计算当前栈的长度，如果该变量为0，则表示该栈为空。或者说我们有一个指向栈顶的变量，如果它开始的时候是设置为空的，我们可以认为栈为空。这部分的实现代码也很简单：

  1. public boolean empty() {
  2. return size() == 0;
  3. }

如果更进一步分析的话，是因为Vector已经实现了size()方法。在Vector里面有一个变量elementCount来表示容器里元素的个数。如果为0，则表示容器空。这部分在Vector里面的实现如下：

  1. public synchronized int size() {
  2. return elementCount;
  3. }

peek

peek是指的返回栈顶端的元素，我们对栈本身不做任何的改动。如果栈里有元素的话，我们就返回最顶端的那个。而该元素的索引为栈的长度。如果栈为空的话，则要抛出异常：

  1. public synchronized E peek() {
  2. int     len = size();
  3. if (len == 0)
  4. throw new EmptyStackException();
  5. return elementAt(len - 1);
  6. }

这个elementAt方法也是Vector里面的一个实现。在Vector里面，实际上是用一个elementData的Object数组来存储元素的。所以要找到顶端的元素无非就是访问栈最上面的那个索引。它的详细实现如下：

  1. public synchronized E elementAt(int index) {
  2. if (index >= elementCount) {
  3. throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
  4. }
  5. return elementData(index);
  6. }
  7. @SuppressWarnings("unchecked")
  8. E elementData(int index) {
  9. return (E) elementData[index];
  10. }

pop

pop方法就是将栈顶的元素弹出来，如果栈里有元素，就取最顶端的那个，否则就要抛出异常：

  1. public synchronized E pop() {
  2. E       obj;
  3. int     len = size();
  4. obj = peek();
  5. removeElementAt(len - 1);
  6. return obj;
  7. }

在这里，判断是否可以取栈顶元素在peek方法里实现了，也将如果栈为空则抛异常的部分包含在peek方法里面。这里有必要注意的一个细节就是，在通过peek()取到顶端的元素之后，我们需要用removeElementAt()方法将最顶端的元素移除。我们平时可能不太会留意到这一点。为什么要移除呢？我们反正有一个elementCount来记录栈的长度，不管它不是也可以吗？

实际上，这么做在程序运行的时候会有一个潜在的内存泄露的问题。因为在java里面，如果我们普通定义的类型属于强引用类型。比如这里vector就底层用的Object[]这个数组强类型来保存数据。强类型在jvm中做gc的时候，只要程序中有引用到它，它是不会被回收的。这就意味着在这里，只要我们一直在用着stack，那么stack里面所有关联的元素就都别想释放了。这样运行时间一长就会导致内存泄露的问题。那么，为了解决这个问题，这里就是用的removeElementAt()方法。

  1. public synchronized void removeElementAt(int index) {
  2. modCount++;
  3. if (index >= elementCount) {
  4. throw new ArrayIndexOutOfBoundsException(index + " >= " +
  5. elementCount);
  6. }
  7. else if (index < 0) {
  8. throw new ArrayIndexOutOfBoundsException(index);
  9. }
  10. int j = elementCount - index - 1;
  11. if (j > 0) {
  12. System.arraycopy(elementData, index + 1, elementData, index, j);
  13. }
  14. elementCount--;
  15. elementData[elementCount] = null; /* to let gc do its work */
  16. }

这个方法实现的思路也比较简单。就是用待删除元素的后面元素依次覆盖前面一个元素。这样，就相当于将数组的实际元素长度给缩短了。因为这里这个移除元素的方法是定义在vector中间，它所面对的是一个更加普遍的情况，我们移除的元素不一定就是数组尾部的，所以才需要从后面依次覆盖。如果只是单纯对于一个栈的实现来说，我们完全可以直接将要删除的元素置为null就可以了。

push

push的操作也比较直观。我们只要将要入栈的元素放到数组的末尾，再将数组长度加1就可以了。

  1. public E push(E item) {
  2. addElement(item);
  3. return item;
  4. }

这里，addElement方法将后面的细节都封装了起来。如果我们更加深入的去考虑这个问题的话，我们会发现几个需要考虑的点。1. 首先，数组不会是无穷大的 ，所以不可能无限制的让你添加元素下去。当我们数组长度到达一个最大值的时候，我们不能再添加了，就需要抛出异常来。2. 如果当前的数组已经满了，实际上需要扩展数组的长度。常见的手法就是新建一个当前数组长度两倍的数组，再将当前数组的元素给拷贝过去。前面讨论的这两点，都让vector把这份心给操了。我们就本着八卦到底的精神看看它到底是怎么干的吧：

  1. public synchronized void addElement(E obj) {
  2. modCount++;
  3. ensureCapacityHelper(elementCount + 1);
  4. elementData[elementCount++] = obj;
  5. }
  6. private void ensureCapacityHelper(int minCapacity) {
  7. // overflow-conscious code
  8. if (minCapacity - elementData.length > 0)
  9. grow(minCapacity);
  10. }
  11. private void grow(int minCapacity) {
  12. // overflow-conscious code
  13. int oldCapacity = elementData.length;
  14. int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
  15. capacityIncrement : oldCapacity);
  16. if (newCapacity - minCapacity < 0)
  17. newCapacity = minCapacity;
  18. if (newCapacity - MAX_ARRAY_SIZE > 0)
  19. newCapacity = hugeCapacity(minCapacity);
  20. elementData = Arrays.copyOf(elementData, newCapacity);
  21. }
  22. private static int hugeCapacity(int minCapacity) {
  23. if (minCapacity < 0) // overflow
  24. throw new OutOfMemoryError();
  25. return (minCapacity > MAX_ARRAY_SIZE) ?
  26. Integer.MAX_VALUE :
  27. MAX_ARRAY_SIZE;
  28. }

看到这部分代码的时候，我不由得暗暗叹了口气。真的是拔了萝卜带出泥。本来想看看stack的细节实现，结果这些细节把vector都深深的出卖了。在vector中间有几个计数的变量，elementCount表示里面元素的个数，elementData是保存元素的数组。所以一般情况下数组不一定是满的，会存在着elementCount <= elementData.length这样的情况。这也就是为什么ensureCapacityHelper方法里要判断一下当新增加一个元素导致元素的数量超过数组长度了，我们要做一番调整。这个大的调整就在grow方法里展现了。

grow方法和我们所描述的方法有点不一样。他不一样的一点在于我们可以用一个capacityIncrement来指示调整数组长度的时候到底增加多少。默认的情况下相当于数组长度翻倍，如果设置了这个变量就增加这个变量指定的这么多。

search

search这部分就相当于找到一个最靠近栈顶端的匹配元素，然后返回这个元素到栈顶的距离。

  1. public synchronized int search(Object o) {
  2. int i = lastIndexOf(o);
  3. if (i >= 0) {
  4. return size() - i;
  5. }
  6. return -1;
  7. }

对应在vector里面的实现也相对容易理解：

  1. public synchronized int lastIndexOf(Object o) {
  2. return lastIndexOf(o, elementCount-1);
  3. }
  4. public synchronized int lastIndexOf(Object o, int index) {
  5. if (index >= elementCount)
  6. throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
  7. if (o == null) {
  8. for (int i = index; i >= 0; i--)
  9. if (elementData[i]==null)
  10. return i;
  11. } else {
  12. for (int i = index; i >= 0; i--)
  13. if (o.equals(elementData[i]))
  14. return i;
  15. }
  16. return -1;
  17. }

这个lastIndexOf的实现无非是从数组的末端往前遍历，如果找到这个对象就返回。如果到头了，还找不到对象呢？...不好意思，谁让你找不到对象的？活该你光棍，那就返回个-1吧。

Vector

在前面对stack的讨论和分析中，我们几乎也把vector这部分主要的功能以及实现给涵盖了。vector和相关类以及接口的关系类图如下：

java三篇博客转载 详解-vector,stack,queue,deque

因为Java没有内置对List类型的支持，所以Vector内部的实现是采用一个object的array。其定义如下：

  1. protected Object[] elementData;

这里从某种角度来说可以说是java里对泛型支持的不足，因为内部保存数据的是Object[]，在存取数据的时候如果不注意的话会出现存取数据类型不一致的错误。所以在以下的某些个方法里需要加上@SuppressWarnings("unchecked")的声明。

  1. @SuppressWarnings("unchecked")
  2. E elementData(int index) {
  3. return (E) elementData[index];
  4. }

我们前面讨论的那些数组的增长，删除元素，查找元素以及修改等功能就占据了vector的大部分。如果有兴趣看vector的源代码的话，会发现里面主要就是这些功能的实现再加上一个迭代器功能。总共的代码不是很多，1200多行，这里就不再赘述了。

可以说，vector它本身就是一个可以动态增长的数组。和我们常用的ArrayList很像。和ArrayList的不同在于它对元素的访问都用synchronized修饰，也就是说它是线程安全的。在多线程的环境下，我们可以使用它。

总结

看前面这些代码，不但理顺了栈和vector的具体实现，还可以从中发现一些其他的东西。比如说，栈最大的长度取决于vector里面数组能有多长。这里vector里面最大能取到Integer.MAX_VALUE。 以前写c程序的代码时经常感叹，要是有那种可以自动增长的数组类型就好了。当然，c99后面确实提供了这个福利。在java里面，比较典型这一部分就由vector提供了。你看，他可以自动按照需要增长，本身是线程安全的，顺便帮你把清除元素时的内存泄露问题都考虑到了。简直是自动、安全、健康又环保啊：）

参考资料：

http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html

博客二：转载自http://www.jb51.net/article/37872.htm

Java中Vector与ArrayList的区别详解

首先看这两类都实现List接口，而List接口一共有三个实现类，分别是ArrayList、Vector和LinkedList。List用于存放多个元素，能够维护元素的次序，并且允许元素的重复。
3个具体实现类的相关区别如下：

1.ArrayList是最常用的List实现类，内部是通过数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要讲已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。

2.Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。

3.LinkedList是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，他还提供了List接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。

查看Java源代码，发现当数组的大小不够的时候，需要重新建立数组，然后将元素拷贝到新的数组内，ArrayList和Vector的扩展数组的大小不同。
ArrayList中：

复制代码
代码如下:

public boolean add(E e) {
    
ensureCapacity(size + 1);  // 增加元素，判断是否能够容纳。不能的话就要新建数组
    
elementData[size++] = e;
     return true;
 }
  public void
ensureCapacity(int minCapacity) {
     modCount++;
     int oldCapacity =
elementData.length;
     if (minCapacity > oldCapacity) {
        
Object oldData[] = elementData; // 此行没看出来用处，不知道开发者出于什么考虑
         int
newCapacity = (oldCapacity * 3)/2 + 1; // 增加新的数组的大小
         if (newCapacity
< minCapacity)
        newCapacity = minCapacity;
             //
minCapacity is usually close to size, so this is a win:
            
elementData = Arrays.copyOf(elementData, newCapacity);
    
}
 }

Vector中：

复制代码
代码如下:

private void ensureCapacityHelper(int
minCapacity) {
     int oldCapacity = elementData.length;
     if
(minCapacity > oldCapacity) {
         Object[] oldData =
elementData;
         int newCapacity = (capacityIncrement > 0)
?
        (oldCapacity + capacityIncrement) : (oldCapacity * 2);
        
if (newCapacity < minCapacity) {
        newCapacity =
minCapacity;
         }
        elementData = Arrays.copyOf(elementData,
newCapacity);
     }
 }

关于ArrayList和Vector区别如下：
1.ArrayList在内存不够时默认是扩展50%
+ 1个，Vector是默认扩展1倍。
2.Vector提供indexOf(obj,
start)接口，ArrayList没有。
3.Vector属于线程安全级别的，但是大多数情况下不使用Vector，因为线程安全需要更大的系统开销。

博客三：转载自http://uule.iteye.com/blog/2095650?utm_source=tuicool

队列Queue、双端队列Deque

注意：这都只是接口而已

1、Queue

API

在java5中新增加了java.util.Queue接口，用以支持队列的常见操作。该接口扩展了java.util.Collection接口。

  1. public interface Queue<E>
  2. extends Collection<E>

除了基本的 Collection 操作外，队列还提供其他的插入、提取和检查操作。

每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。

java三篇博客转载 详解-vector,stack,queue,deque

队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对元素进行排序。

在 FIFO 队列中，所有的新元素都插入队列的末尾，移除元素从队列头部移除。

Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素，使用element()或者peek()方法。

java三篇博客转载 详解-vector,stack,queue,deque

offer 方法可插入一个元素，否则返回 false。这与 Collection.add 方法不同，该方法只能通过抛出未经检查的异常使添加元素失败。

remove() 和 poll() 方法可移除和返回队列的头。到底从队列中移除哪个元素是队列排序策略的功能，而该策略在各种实现中是不同的。remove() 和 poll() 方法仅在队列为空时其行为有所不同：remove() 方法抛出一个异常，而 poll() 方法则返回 null。

element() 和 peek() 返回，但不移除，队列的头。

Queue 实现通常不允许插入 null 元素，尽管某些实现（如 LinkedList）并不禁止插入 null。即使在允许 null 的实现中，也不应该将 null 插入到 Queue 中，因为 null 也用作 poll 方法的一个特殊返回值，表明队列不包含元素。

值得注意的是LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

  1. import java.util.Queue;
  2. import java.util.LinkedList;
  3. public class TestQueue {
  4. public static void main(String[] args) {
  5. Queue<String> queue = new LinkedList<String>();
  6. queue.offer("Hello");
  7. queue.offer("World!");
  8. queue.offer("你好！");
  9. System.out.println(queue.size());
  10. String str;
  11. while((str=queue.poll())!=null){
  12. System.out.print(str);
  13. }
  14. System.out.println();
  15. System.out.println(queue.size());
  16. }
  17. }

2、Deque

API

  1. public interface Deque<E>
  2. extends Queue<E>

一个线性 collection，支持在两端插入和移除元素。

名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。

大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

java三篇博客转载 详解-vector,stack,queue,deque

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。因为此接口继承了队列接口Queue，所以其每种方法也存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。

a、在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：

java三篇博客转载 详解-vector,stack,queue,deque

b、用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：

java三篇博客转载 详解-vector,stack,queue,deque

相关文章