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

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

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

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

我们先看下JDK种的定义&＃xff1a;

public class Stack extends Vector {

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

Vector&＃xff1a;线程安全的动态数组

Stack&＃xff1a;继承Vector&＃xff0c;基于动态数组实现的一个线程安全的栈&＃xff1b;

1.Vector 和 Stack的特点&＃xff1a;

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

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

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

2.Vector 和 Stack 结构&＃xff1a;

Vector类

与ArrayList基本一致&＃xff0c;剩下的主要不同点如下&＃xff1a;

1、Vector是线程安全的

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

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

Stack类

实现了栈的基本操作。方法如下&＃xff1a;

public Stack();

创建空栈

public synchronized E peek();

返回栈顶的值&＃xff1b;

public E push(E item);

入栈操作&＃xff1b;

public synchronized E pop();

出栈操作&＃xff1b;

public boolean empty();

判断栈是否为空&＃xff1b;

public synchronized int search(Object o);

返回对象在栈中的位置&＃xff1b;

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

3.基本使用

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

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 &＃61; new Vector();

for(int i &＃61; 0; i <10; i&＃43;&＃43;){

vector.add(i);

}

//直接打印

System.out.println(vector.toString());

//size()

System.out.println(vector.size());

//contains

System.out.println(vector.contains(2));

//iterator

Iterator iterator &＃61; vector.iterator();

while(iterator.hasNext()){

System.out.print(iterator.next() &＃43; " ");

}

//toArray

Object[] objArr &＃61; vector.toArray();

System.out.println("\nobjArr:" &＃43; Arrays.asList(objArr));

Integer[] intArr &＃61; vector.toArray(new Integer[vector.size()]);

System.out.println("intArr:" &＃43; 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 &＃61; vector.listIterator();

System.out.println(listIterator.hasPrevious());

//listIterator(index)方法

ListIterator iListIterator &＃61; vector.listIterator(5);

System.out.println(iListIterator.previous());

//subList方法

System.out.println(vector.subList(5, 7));

//clear

vector.clear();

System.out.println(vector);

}

}

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

import java.util.Stack;

public class Test {

public static void main(String[] args) {

Stack stack &＃61; new Stack();

for(int i &＃61; 0; i <10; i&＃43;&＃43;){

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遍历&＃xff1a;");

while(!stack.empty()){

System.out.print(stack.pop() &＃43; " ");

}

}

}

小节&＃xff1a;

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

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

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

public class Vector

extends AbstractList

implements List, RandomAccess, Cloneable, java.io.Serializable

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

由于Stack是继承和基于Vector&＃xff0c;那么简单看一下Vector的一些定义和方法源码&＃xff1a;

// 底层使用数组存储数据

protected Object[] elementData;

// 元素个数

protected int elementCount ;

// 自定义容器扩容递增大小

protected int capacityIncrement ;

public Vector( int initialCapacity, int capacityIncrement) {

super();

// 越界检查

if (initialCapacity <0)

throw new IllegalArgumentException( "Illegal Capacity: " &＃43;

initialCapacity);

// 初始化数组

this.elementData &＃61; new Object[initialCapacity];

this.capacityIncrement &＃61; capacityIncrement;

}

// 使用synchronized关键字锁定方法&＃xff0c;保证同一时间内只有一个线程可以操纵该方法

public synchronized boolean add(E e) {

modCount&＃43;&＃43;;

// 扩容检查

ensureCapacityHelper( elementCount &＃43; 1);

elementData[elementCount &＃43;&＃43;] &＃61; e;

return true;

}

private void ensureCapacityHelper(int minCapacity) {

// 当前元素数量

int oldCapacity &＃61; elementData .length;

// 是否需要扩容

if (minCapacity > oldCapacity) {

Object[] oldData &＃61; elementData;

// 如果自定义了容器扩容递增大小&＃xff0c;则按照capacityIncrement进行扩容&＃xff0c;否则按两倍进行扩容(*2)

int newCapacity &＃61; (capacityIncrement > 0) ?

(oldCapacity &＃43; capacityIncrement) : (oldCapacity * 2);

if (newCapacity

newCapacity &＃61; minCapacity;

}

// 数组copy

elementData &＃61; Arrays.copyOf( elementData, newCapacity);

}

}

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

三、主要方法分析

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

/**

* 获取栈顶的对象&＃xff0c;但是不删除

*/

public synchronized E peek() {

// 当前容器元素个数

int len &＃61; size();

// 如果没有元素&＃xff0c;则直接抛出异常

if (len &＃61;&＃61; 0)

throw new EmptyStackException();

// 调用elementAt方法取出数组最后一个元素(最后一个元素在栈顶)

return elementAt(len - 1);

}

/**

* 根据index索引取出该位置的元素&＃xff0c;这个方法在Vector中

*/

public synchronized E elementAt(int index) {

// 越界检查

if (index >&＃61; elementCount ) {

throw new ArrayIndexOutOfBoundsException(index &＃43; " >&＃61; " &＃43; elementCount);

}

// 直接通过数组下标获取元素

return (E)elementData [index];

}

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

/**

* 弹栈&＃xff0c;获取并删除栈顶的对象

*/

public synchronized E pop() {

// 记录栈顶的对象

E obj;

// 当前容器元素个数

int len &＃61; size();

// 通过peek()方法获取栈顶对象

obj &＃61; peek();

// 调用removeElement方法删除栈顶对象

removeElementAt(len - 1);

// 返回栈顶对象

return obj;

}

/**

* 根据index索引删除元素

*/

public synchronized void removeElementAt(int index) {

modCount&＃43;&＃43;;

// 越界检查

if (index >&＃61; elementCount ) {

throw new ArrayIndexOutOfBoundsException(index &＃43; " >&＃61; " &＃43;

elementCount);

}

else if (index <0) {

throw new ArrayIndexOutOfBoundsException(index);

}

// 计算数组元素要移动的个数

int j &＃61; elementCount - index - 1;

if (j > 0) {

// 进行数组移动&＃xff0c;中间删除了一个&＃xff0c;所以将后面的元素往前移动(这里直接移动将index位置元素覆盖掉&＃xff0c;就相当于删除了)

System. arraycopy(elementData, index &＃43; 1, elementData, index, j);

}

// 容器元素个数减1

elementCount--;

// 将容器最后一个元素置空(因为删除了一个元素&＃xff0c;然后index后面的元素都向前移动了&＃xff0c;所以最后一个就没用了 )

elementData[elementCount ] &＃61; null; /* to let gc do its work */

}

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

/**

* 将对象添加进容器并返回

*/

public E push(E item) {

// 调用addElement将元素添加进容器

addElement(item);

// 返回该元素

return item;

}

/**

* 将元素添加进容器&＃xff0c;这个方法在Vector中

*/

public synchronized void addElement(E obj) {

modCount&＃43;&＃43;;

// 扩容检查

ensureCapacityHelper( elementCount &＃43; 1);

// 将对象放入到数组中&＃xff0c;元素个数&＃43;1

elementData[elementCount &＃43;&＃43;] &＃61; obj;

}

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

/**

* 返回对象在容器中的位置&＃xff0c;栈顶为1

*/

public synchronized int search(Object o) {

// 从数组中查找元素&＃xff0c;从最后一次出现

int i &＃61; lastIndexOf(o);

// 因为栈顶算1&＃xff0c;所以要用size()-i计算

if (i >&＃61; 0) {

return size() - i;

}

return -1;

}

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

/**

* 检查容器是否为空

*/

public boolean empty() {

return size() &＃61;&＃61; 0;

}

小节&＃xff1a;

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

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

(1)Stack为什么是基于数组实现的呢&＃xff1f;

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

(2)Stack为什么是继承Vector的&＃xff1f;

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

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

import java.util.LinkedList;

public class LinkedStack {

private LinkedList linked ;

public LinkedStack() {

this.linked &＃61; 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 &＃61; this.linked.indexOf(item);

return i &＃43; 1;

}

public boolean empty() {

return this.linked.isEmpty();

}

}

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

四、Vector&ArrayList的区别

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

3个具体实现类的相关区别如下&＃xff1a;

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

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

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

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

1、Queue

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

public interface Queue

extends Collection

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

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

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

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

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

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

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

element() 和 peek() 返回&＃xff0c;但不移除&＃xff0c;队列的头。

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

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

import java.util.Queue;

import java.util.LinkedList;

public class TestQueue {

public static void main(String[] args) {

Queue queue &＃61; new LinkedList();

queue.offer("Hello");

queue.offer("World!");

queue.offer("你好&＃xff01;");

System.out.println(queue.size());

String str;

while((str&＃61;queue.poll())!&＃61;null){

System.out.print(str);

}

System.out.println();

System.out.println(queue.size());

}

}

2、Deque

public interface Deque

extends Queue

一个线性 collection&＃xff0c;支持在两端插入和移除元素。

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

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

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

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

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