前面我們已經接觸過幾種數據結構了，有數組、鏈表、hash表、紅黑樹(二叉查詢樹)，今天再來看另外一種數據結構：棧。
什么是棧呢，我們先看一個例子：棧就相當于一個很窄的木桶，我們往木桶里放東西，往外拿東西時會發現，我們最開始放的東西在最底部，最先拿出來的是剛剛放進去的。所以，棧就是這么一種先進后出（firstinlastout，或者叫后進先出）的容器，它只有一個口，在這個口放入元素，也在這個口取出元素。那么我們接下來學習jdk中的棧。
一、vector&stack的基本介紹和使用
我們先看下jdk種的定義：
|
1
|
public class stack<e> extends vector<e> { |
從上面可以看到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類
實現了棧的基本操作。方法如下：
|
1
|
public stack(); |
創建空棧
|
1
|
public synchronized e peek(); |
返回棧頂的值；
|
1
|
public e push(e item); |
入棧操作；
|
1
|
public synchronized e pop(); |
出棧操作；
|
1
|
public boolean empty(); |
判斷棧是否為空；
|
1
|
public synchronized int search(object o); |
返回對象在棧中的位置；
對于上述的棧而言，我們基本只會經常用到上面的方法，雖然它繼承了vector，有很多方法，但基本不會使用，而只是當做一個棧來看待。
3.基本使用
vector中的部分方法使用如下，另外vector的遍歷方式跟arraylist一致，可以用foreach，迭代器，for循環遍歷；
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
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方法實現棧頂到棧底的遍歷）：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
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() + " "); } }} |
小節：
vector是線程安全的，但是性能較差，一般情況下使用arraylist,除非特殊需求；
如果打算用stack作為棧來使用的話，就老老實實嚴格按照棧的幾種操作來使用，否則就是去了使用stack的意義，還不如用vector;
二、vector&stacke的結構和底層存儲
|
1
2
3
|
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的一些定義和方法源碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
// 底層使用數組存儲數據 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()——獲取棧頂的對象
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
/** * 獲取棧頂的對象，但是不刪除 */ 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()——彈棧（出棧），獲取棧頂的對象，并將該對象從容器中刪除
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
/** * 彈棧，獲取并刪除棧頂的對象 */ 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)——壓棧（入棧），將對象添加進容器并返回
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
/** * 將對象添加進容器并返回 */ 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
2
3
4
5
6
7
8
9
10
11
12
13
|
/** * 返回對象在容器中的位置，棧頂為1 */ public synchronized int search(object o) { // 從數組中查找元素，從最后一次出現 int i = lastindexof(o); // 因為棧頂算1，所以要用size()-i計算 if (i >= 0) { return size() - i; } return -1; } |
5.empty()——容器是否為空
|
1
2
3
4
5
6
|
/** * 檢查容器是否為空 */ 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是比較理想的，那么我們就來嘗試一下吧：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
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的區別
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接口。
|
1
2
|
public interface queue<e> extends collection<e> |
除了基本的 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來用。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
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
|
1
2
|
public interface deque<e> extends queue<e> |
一個線性 collection，支持在兩端插入和移除元素。
名稱 deque 是“double ended queue（雙端隊列）”的縮寫，通常讀為“deck”。
大多數 deque 實現對于它們能夠包含的元素數沒有固定限制，但此接口既支持有容量限制的雙端隊列，也支持沒有固定大小限制的雙端隊列。
此接口定義在雙端隊列兩端訪問元素的方法。提供插入、移除和檢查元素的方法。因為此接口繼承了隊列接口queue，所以其每種方法也存在兩種形式：一種形式在操作失敗時拋出異常，另一種形式返回一個特殊值（null 或 false，具體取決于操作）。
a、在將雙端隊列用作隊列時，將得到 fifo（先進先出）行為。將元素添加到雙端隊列的末尾，從雙端隊列的開頭移除元素。從 queue 接口繼承的方法完全等效于 deque 方法，如下表所示：
b、用作 lifo（后進先出）堆棧。應優先使用此接口而不是遺留 stack 類。在將雙端隊列用作堆棧時，元素被推入雙端隊列的開頭并從雙端隊列開頭彈出。堆棧方法完全等效于 deque 方法，如下表所示：
原文鏈接：http://www.cnblogs.com/pony1223/p/7940116.html
