当前位置:  首页  >  PHP资讯  >  业界资讯

深入分析JAVAVector和Stack的具体用法

这篇文章主要介绍了深入分析JAVAVector和Stack的具体用法,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧

前面我们已经接触过几种数据结构了,有数组、链表、Hash表、红黑树(二叉查询树),今天再来看另外一种数据结构:栈。

什么是栈呢,我们先看一个例子:栈就相当于一个很窄的木桶,我们往木桶里放东西,往外拿东西时会发现,我们最开始放的东西在最底部,最先拿出来的是刚刚放进去的。所以,栈就是这么一种先进后出(FirstInLastOut,或者叫后进先出)的容器,它只有一个口,在这个口放入元素,也在这个口取出元素。那么我们接下来学习JDK中的栈。

一、Vector&Stack的基本介绍和使用

我们先看下JDK种的定义:

 public class Stack extends Vector {

从上面可以看到Stack 是继承自于Vector的,因此我们要对Vector 也要有一定的认识。

Vector:线程安全的动态数组

Stack:继承Vector,基于动态数组实现的一个线程安全的栈;

1.Vector 和 Stack的特点:

Vector与ArrayList基本是一致的,不同的是Vector是线程安全的,会在可能出现线程安全的方法前面加上synchronized关键字;

Vector:随机访问速度快,插入和移除性能较差(数组的特点);支持null元素;有顺序;元素可以重复;线程安全;

Stack:后进先出,实现了一些栈基本操作的方法(其实并不是只能后进先出,因为继承自Vector,可以有很多操作,从某种意义上来讲,不是一个栈);

2.Vector 和 Stack 结构:

Vector类

与ArrayList基本一致,剩下的主要不同点如下:

1、Vector是线程安全的

2、ArrayList增长量和Vector的增长量不一致

其它,如构造方法不一致,Vector可以通过构造方法初始化capacityIncrement,另外还有其它一些方法,如indexOf方法,Vector支持从指定位置开始搜索查找;另外,Vector还有一些功能重复的冗余方法,如addElement,setElementAt方法,之所以这样,是由于历史原因,像addElement方法是以前遗留的,当集合框架引进的时候,Vector加入集合大家族,改成实现List接口,需要实现List接口中定义的一些方法,但是出于兼容考虑,又不能删除老的方法,所以出现了一些功能冗余的旧方法;现在已经被ArrayList取代,基本很少使用,了解即可。

Stack类

实现了栈的基本操作。方法如下:

 public Stack();

创建空栈

 public synchronized E peek();

返回栈顶的值;

 public E push(E item);

入栈操作;

 public synchronized E pop();

出栈操作;

 public boolean empty();

判断栈是否为空;

 public synchronized int search(Object o);

返回对象在栈中的位置;

对于上述的栈而言,我们基本只会经常用到上面的方法,虽然它继承了Vector,有很多方法,但基本不会使用,而只是当做一个栈来看待。

3.基本使用

Vector中的部分方法使用如下,另外Vector的遍历方式跟ArrayList一致,可以用foreach,迭代器,for循环遍历;

 import java.util.Arrays; import java.util.Iterator; import java.util.List; import java.util.ListIterator; import java.util.Vector; public class Test { public static void main(String[] args) { Vector vector = new Vector(); for(int i = 0; i <10; i++){ vector.add(i); } //直接打印 System.out.println(vector.toString()); //size() System.out.println(vector.size()); //contains System.out.println(vector.contains(2)); //iterator Iterator iterator = vector.iterator(); while(iterator.hasNext()){ System.out.print(iterator.next() + " "); } //toArray Object[] objArr = vector.toArray(); System.out.println("\nobjArr:" + Arrays.asList(objArr)); Integer[] intArr = vector.toArray(new Integer[vector.size()]); System.out.println("intArr:" + Arrays.asList(intArr)); //add vector.add(5); //remove vector.remove(5); System.out.println(vector); //containsAll System.out.println(vector.containsAll(Arrays.asList(5,6))); //addAll vector.addAll(Arrays.asList(555,666)); System.out.println(vector); //removeAll vector.removeAll(Arrays.asList(555,666)); System.out.println(vector); //addAll方法 vector.addAll(5, Arrays.asList(666,666, 6)); System.out.println(vector); //get方法 System.out.println(vector.get(5)); //set方法 vector.set(5, 55); System.out.println(vector.get(5)); //add方法 vector.add(0, 555); System.out.println(vector); //remove方法 vector.remove(0); System.out.println(vector); //indexof方法 System.out.println(vector.indexOf(6)); //lastIndexOf方法 System.out.println(vector.lastIndexOf(6)); //listIterator方法 ListIterator listIterator = vector.listIterator(); System.out.println(listIterator.hasPrevious()); //listIterator(index)方法 ListIterator iListIterator = vector.listIterator(5); System.out.println(iListIterator.previous()); //subList方法 System.out.println(vector.subList(5, 7)); //clear vector.clear(); System.out.println(vector); } }

Stack中的部分方法使用如下,因为Stack继承Vector,所以Vector可以用的方法,Stack同样可以使用,以下列出一些Stack独有的方法的例子,很简单,就是栈的一些基本操作,另外stack除了Vector的几种遍历方式外,还有自己独有的遍历元素的方式(利用empty方法和pop方法实现栈顶到栈底的遍历):

 import java.util.Stack; public class Test { public static void main(String[] args) { Stack stack = new Stack(); for(int i = 0; i <10; i++){ stack.add(i); } System.out.println(stack); System.out.println(stack.peek()); stack.push(555); System.out.println(stack); System.out.println(stack.pop()); System.out.println(stack); System.out.println(stack.empty()); System.out.println(stack.search(6)); System.out.println("stack遍历:"); while(!stack.empty()){ System.out.print(stack.pop() + " "); } } } 

小节:

Vector是线程安全的,但是性能较差,一般情况下使用ArrayList,除非特殊需求;

如果打算用Stack作为栈来使用的话,就老老实实严格按照栈的几种操作来使用,否则就是去了使用stack的意义,还不如用Vector;

二、Vector&Stacke的结构和底层存储

 public class Vector extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable

Vector是List的一个实现类,其实Vector也是一个基于数组实现的List容器,其功能及实现代码和ArrayList基本上是一样的。那么不一样的是什么地方的,一个是数组扩容的时候,Vector是*2,ArrayList是*1.5+1;另一个就是Vector是线程安全的,而ArrayList不是,而Vector线程安全的做法是在每个方法上面加了一个synchronized关键字来保证的。但是这里说一句,Vector已经不官方的(大家公认的)不被推荐使用了,正式因为其实现线程安全方式是锁定整个方法,导致的是效率不高,那么有没有更好的提到方案呢,其实也不能说有,但是还真就有那么一个,Collections.synchronizedList()

由于Stack是继承和基于Vector,那么简单看一下Vector的一些定义和方法源码:

 // 底层使用数组存储数据 protected Object[] elementData; // 元素个数 protected int elementCount ; // 自定义容器扩容递增大小 protected int capacityIncrement ; public Vector( int initialCapacity, int capacityIncrement) { super(); // 越界检查 if (initialCapacity <0) throw new IllegalArgumentException( "Illegal Capacity: " + initialCapacity); // 初始化数组 this.elementData = new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; } // 使用synchronized关键字锁定方法,保证同一时间内只有一个线程可以操纵该方法 public synchronized boolean add(E e) { modCount++; // 扩容检查 ensureCapacityHelper( elementCount + 1); elementData[elementCount ++] = e; return true; } private void ensureCapacityHelper(int minCapacity) { // 当前元素数量 int oldCapacity = elementData .length; // 是否需要扩容 if (minCapacity > oldCapacity) { Object[] oldData = elementData; // 如果自定义了容器扩容递增大小,则按照capacityIncrement进行扩容,否则按两倍进行扩容(*2) int newCapacity = (capacityIncrement > 0) &#63; (oldCapacity + capacityIncrement) : (oldCapacity * 2); if (newCapacity  

Vector就简单看到这里,其他方法Stack如果没有调用的话就不进行分析了,不明白的可以去看ArrayList源码解析。

三、主要方法分析

1.peek()——获取栈顶的对象

 /** * 获取栈顶的对象,但是不删除 */ public synchronized E peek() { // 当前容器元素个数 int len = size(); // 如果没有元素,则直接抛出异常 if (len == 0) throw new EmptyStackException(); // 调用elementAt方法取出数组最后一个元素(最后一个元素在栈顶) return elementAt(len - 1); } /** * 根据index索引取出该位置的元素,这个方法在Vector中 */ public synchronized E elementAt(int index) { // 越界检查 if (index >= elementCount ) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } // 直接通过数组下标获取元素 return (E)elementData [index]; }

2.pop()——弹栈(出栈),获取栈顶的对象,并将该对象从容器中删除

 /** * 弹栈,获取并删除栈顶的对象 */ public synchronized E pop() { // 记录栈顶的对象 E obj; // 当前容器元素个数 int len = size(); // 通过peek()方法获取栈顶对象 obj = peek(); // 调用removeElement方法删除栈顶对象 removeElementAt(len - 1); // 返回栈顶对象 return obj; } /** * 根据index索引删除元素 */ public synchronized void removeElementAt(int index) { modCount++; // 越界检查 if (index >= elementCount ) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } else if (index <0) { throw new ArrayIndexOutOfBoundsException(index); } // 计算数组元素要移动的个数 int j = elementCount - index - 1; if (j > 0) { // 进行数组移动,中间删除了一个,所以将后面的元素往前移动(这里直接移动将index位置元素覆盖掉,就相当于删除了) System. arraycopy(elementData, index + 1, elementData, index, j); } // 容器元素个数减1 elementCount--; // 将容器最后一个元素置空(因为删除了一个元素,然后index后面的元素都向前移动了,所以最后一个就没用了 ) elementData[elementCount ] = null; /* to let gc do its work */ }

3.push(E item)——压栈(入栈),将对象添加进容器并返回

 /** * 将对象添加进容器并返回 */ public E push(E item) { // 调用addElement将元素添加进容器 addElement(item); // 返回该元素 return item; } /** * 将元素添加进容器,这个方法在Vector中 */ public synchronized void addElement(E obj) { modCount++; // 扩容检查 ensureCapacityHelper( elementCount + 1); // 将对象放入到数组中,元素个数+1 elementData[elementCount ++] = obj; }

4.search(Object o)——返回对象在容器中的位置,栈顶为1

 /** * 返回对象在容器中的位置,栈顶为1 */ public synchronized int search(Object o) { // 从数组中查找元素,从最后一次出现 int i = lastIndexOf(o); // 因为栈顶算1,所以要用size()-i计算 if (i >= 0) { return size() - i; } return -1; }

5.empty()——容器是否为空

 /** * 检查容器是否为空 */ public boolean empty() { return size() == 0; }

小节:

到这里Stack的方法就分析完成了,由于Stack最终还是基于数组的,理解起来还是很容易的(因为有了ArrayList的基础啦)。

虽然jdk中Stack的源码分析完了,但是这里有必要讨论下,不知道是否发现这里的Stack很奇怪的现象,

(1)Stack为什么是基于数组实现的呢?

我们都知道数组的特点:方便根据下标查询(随机访问),但是内存固定,且扩容效率较低。很容易想到Stack用链表实现最合适的。

(2)Stack为什么是继承Vector的?

继承也就意味着Stack继承了Vector的方法,这使得Stack有点不伦不类的感觉,既是List又是Stack。如果非要继承Vector合理的做法应该是什么:Stack不继承Vector,而只是在自身有一个Vector的引用,聚合对不对?

唯一的解释呢,就是Stack是jdk1.0出来的,那个时候jdk中的容器还没有ArrayList、LinkedList等只有Vector,既然已经有了Vector且能实现Stack的功能,那么就干吧。。。既然用链表实现Stack是比较理想的,那么我们就来尝试一下吧:

 import java.util.LinkedList; public class LinkedStack { private LinkedList linked ; public LinkedStack() { this.linked = new LinkedList(); } public E push(E item) { this.linked .addFirst(item); return item; } public E pop() { if (this.linked.isEmpty()) { return null; } return this.linked.removeFirst(); } public E peek() { if (this.linked.isEmpty()) { return null; } return this.linked.getFirst(); } public int search(E item) { int i = this.linked.indexOf(item); return i + 1; } public boolean empty() { return this.linked.isEmpty(); } }

这里使用的LinkedList实现的Stack,记得在LinkedList中说过,LinkedList实现了Deque接口使得它既可以作为栈(先进后出),又可以作为队列(先进先出)。

四、Vector&ArrayList的区别

List接口一共有三个实现类,分别是ArrayList、Vector和LinkedList。List用于存放多个元素,能够维护元素的次序,并且允许元素的重复。

3个具体实现类的相关区别如下:

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

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

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

五、队列Queue、双端队列Deque简单了解

1、Queue

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

 public interface Queue extends Collection 

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

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

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

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

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

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来用。

 import java.util.Queue; import java.util.LinkedList; public class TestQueue { public static void main(String[] args) { Queue queue = new LinkedList(); queue.offer("Hello"); queue.offer("World!"); queue.offer("你好!"); System.out.println(queue.size()); String str; while((str=queue.poll())!=null){ System.out.print(str); } System.out.println(); System.out.println(queue.size()); } }

2、Deque

 public interface Deque extends Queue 

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

名称 deque 是“double ended queue(双端队列)”的缩写,通常读为“deck”。

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

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

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

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

内容推荐:免费高清PNG素材下载
吐了个 "CAO" !
扫码关注 PHP1 官方微信号
PHP1.CN | 中国最专业的PHP中文社区 | PNG素材下载 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved PHP1.CN 第一PHP社区 版权所有 京ICP备19059560号-4