深入分析JAVA Vector和Stack的具體用法
前面我們已經接觸過幾種數據結構了，有數組、鏈表、Hash表、紅黑樹(二叉查詢樹)，今天再來看另外一種數據結構：棧。
什么是棧呢，我們先看一個例子：棧就相當于一個很窄的木桶，我們往木桶里放東西，往外拿東西時會發(fā)現，我們最開始放的東西在最底部，最先拿出來的是剛剛放進去的。所以，棧就是這么一種先進后出（FirstInLastOut，或者叫后進先出）的容器，它只有一個口，在這個口放入元素，也在這個口取出元素。那么我們接下來學習JDK中的棧。
一、Vector&Stack的基本介紹和使用
我們先看下JDK種的定義：
public class Stack<E> extends Vector<E> {
從上面可以看到Stack 是繼承自于Vector的，因此我們要對Vector 也要有一定的認識。
Vector：線程安全的動態(tài)數組
Stack：繼承Vector，基于動態(tài)數組實現的一個線程安全的棧；
1.Vector 和 Stack的特點：
Vector與ArrayList基本是一致的，不同的是Vector是線程安全的，會在可能出現線程安全的方法前面加上synchronized關鍵字；
Vector：隨機訪問速度快，插入和移除性能較差(數組的特點)；支持null元素；有順序；元素可以重復；線程安全；
Stack：后進先出，實現了一些?；静僮鞯姆椒ǎㄆ鋵嵅⒉皇侵荒芎筮M先出，因為繼承自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();
創(chuàng)建空棧
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循環(huán)遍歷；
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<Integer> vector = new Vector<Integer>();
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<Integer> 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<Integer> listIterator = vector.listIterator();
System.out.println(listIterator.hasPrevious());
//listIterator(index)方法
ListIterator<Integer> 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<Integer> stack = new Stack<Integer>();
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() + " ");
}
}
}
小節(jié)：
Vector是線程安全的，但是性能較差，一般情況下使用ArrayList,除非特殊需求；
如果打算用Stack作為棧來使用的話，就老老實實嚴格按照棧的幾種操作來使用，否則就是去了使用stack的意義，還不如用Vector;
二、Vector&Stacke的結構和底層存儲
public class Vector<E> extends AbstractList<E> implements List<E>, 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) ?
(oldCapacity + capacityIncrement) : (oldCapacity * 2);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
// 數組copy
elementData = Arrays.copyOf( elementData, 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;
}
小節(jié)：
到這里Stack的方法就分析完成了，由于Stack最終還是基于數組的，理解起來還是很容易的（因為有了ArrayList的基礎啦）。
雖然jdk中Stack的源碼分析完了，但是這里有必要討論下，不知道是否發(fā)現這里的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<E> {
private LinkedList<E> linked ;
public LinkedStack() {
this.linked = new LinkedList<E>();
}
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的區(qū)別
List接口一共有三個實現類，分別是ArrayList、Vector和LinkedList。List用于存放多個元素，能夠維護元素的次序，并且允許元素的重復。
3個具體實現類的相關區(qū)別如下：
1.ArrayList是最常用的List實現類，內部是通過數組實現的，它允許對元素進行快速隨機訪問。數組的缺點是每個元素之間不能有間隔，當數組大小不滿足時需要增加存儲能力，就要講已經有數組的數據復制到新的存儲空間中。當從ArrayList的中間位置插入或者刪除元素時，需要對數組進行復制、移動、代價比較高。因此，它適合隨機查找和遍歷，不適合插入和刪除。
2.Vector與ArrayList一樣，也是通過數組實現的，不同的是它支持線程的同步，即某一時刻只有一個線程能夠寫Vector，避免多線程同時寫而引起的不一致性，但實現同步需要很高的花費，因此，訪問它比訪問ArrayList慢。
3.LinkedList是用鏈表結構存儲數據的，很適合數據的動態(tài)插入和刪除，隨機訪問和遍歷速度比較慢。另外，他還提供了List接口中沒有定義的方法，專門用于操作表頭和表尾元素，可以當作堆棧、隊列和雙向隊列使用。
五、隊列Queue、雙端隊列Deque簡單了解
1、Queue
在java5中新增加了java.util.Queue接口，用以支持隊列的常見操作。該接口擴展了java.util.Collection接口。
public interface Queue<E> extends Collection<E>
除了基本的 Collection 操作外，隊列還提供其他的插入、提取和檢查操作。
每個方法都存在兩種形式：一種拋出異常（操作失敗時），另一種返回一個特殊值（null 或 false，具體取決于操作）。
隊列通常（但并非一定）以 FIFO（先進先出）的方式排序各個元素。不過優(yōu)先級隊列和 LIFO 隊列（或堆棧）例外，前者根據提供的比較器或元素的自然順序對元素進行排序，后者按 LIFO（后進先出）的方式對元素進行排序。
在 FIFO 隊列中，所有的新元素都插入隊列的末尾，移除元素從隊列頭部移除。
Queue使用時要盡量避免Collection的add()和remove()方法，而是要使用offer()來加入元素，使用poll()來獲取并移出元素。它們的優(yōu)點是通過返回值可以判斷成功與否，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<String> queue = new LinkedList<String>();
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<E> extends Queue<E>
一個線性 collection，支持在兩端插入和移除元素。
名稱 deque 是“double ended queue（雙端隊列）”的縮寫，通常讀為“deck”。
大多數 Deque 實現對于它們能夠包含的元素數沒有固定限制，但此接口既支持有容量限制的雙端隊列，也支持沒有固定大小限制的雙端隊列。
此接口定義在雙端隊列兩端訪問元素的方法。提供插入、移除和檢查元素的方法。因為此接口繼承了隊列接口Queue，所以其每種方法也存在兩種形式：一種形式在操作失敗時拋出異常，另一種形式返回一個特殊值（null 或 false，具體取決于操作）。
a、在將雙端隊列用作隊列時，將得到 FIFO（先進先出）行為。將元素添加到雙端隊列的末尾，從雙端隊列的開頭移除元素。從 Queue 接口繼承的方法完全等效于 Deque 方法，如下表所示：
b、用作 LIFO（后進先出）堆棧。應優(yōu)先使用此接口而不是遺留 Stack 類。在將雙端隊列用作堆棧時，元素被推入雙端隊列的開頭并從雙端隊列開頭彈出。堆棧方法完全等效于 Deque 方法，如下表所示：
相關文章
這篇文章主要介紹了MyBatis Generator生成代碼及使用方式的相關資料,非常不錯，具有參考借鑒價值，需要的朋友可以參考下2016-09-09
下面小編就為大家?guī)硪黄狫ava基礎的幾道練習題(分享)。小編覺得挺不錯的，現在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧，希望可以幫到你2021-07-07
Java 實戰(zhàn)項目之教材管理系統(tǒng)的實現流程
讀萬卷書不如行萬里路，只學書上的理論是遠遠不夠的，只有在實戰(zhàn)中才能獲得能力的提升，本篇文章手把手帶你用java+SSM+jsp+mysql+maven實現教材管理系統(tǒng),大家可以在過程中查缺補漏，提升水平2021-11-11
跟著思路走，之后從簡單題入手，反復去看，做過之后可能會忘記，之后再做一次，記不住就反復做，反復尋求思路和規(guī)律，慢慢積累就會發(fā)現質的變化2022-03-03
SpringCloud網關(Zuul)如何給多個微服務之間傳遞共享參數
這篇文章主要介紹了SpringCloud網關(Zuul)如何給多個微服務之間傳遞共享參數，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-03-03
本文主要介紹了在Spring Boot中使用@Controller、@ResponseBody和@RestController注解進行HTTP響應返回的方法,具有一定的參考價值,感興趣的可以了解一下2025-03-03
Hystrix是SpringCloud中重要的熔斷保護組件,由Netflix開源,主要提供延遲和容錯管理,以保障分布式系統(tǒng)的高可用性和魯棒性,通過封裝依賴項實現服務間隔離,引入回退邏輯應對依賴服務故障,有效防止系統(tǒng)崩潰和服務級聯(lián)故障2024-10-10
這篇文章主要介紹了Mybatis Log Plugin的使用方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-02-02
Springboot作為當下最主流的java開發(fā)框架,已成為IT從業(yè)人員的入門必備技能,本文主要介紹了搭建SpringBoot項目三種方式,感興趣的可以了解一下2023-09-09
這篇文章主要介紹了Java的Cglib動態(tài)代理實現方式詳解,CGLIB是強大的、高性能的代碼生成庫,被廣泛應用于AOP框架,它底層使用ASM來操作字節(jié)碼生成新的類,為對象引入間接級別,以控制對象的訪問,需要的朋友可以參考下2023-11-11