stack源碼分析

## 一、簡介


棧是資料結構中一種很重要的資料結構類型，因為棧的後進先出功能是實際的開發中有很多的應用場景。java api中提供了棧（stacck)的實作。stack類繼承了vector類，而vector類繼承了abstractlist抽象類，實作了list類，cloneable接口，randomacces接口以及serializable接口。

## 二、源碼閱讀

#### 1.構造方法

```java

public stack() {

}

```

建立一個空棧。

#### 2.入棧push

public e push(e item) {

    addelement(item);

    return item;

public synchronized void addelement(e obj) {

    modcount++;

    ensurecapacityhelper(elementcount + 1);

    elementdata[elementcount++] = obj;

入棧是一個同步的方法，調用vector的**addelement**方法，也是一個同步方法，先将修改次數加一，之後調用**ensurecapacityhelper**确認數組有足夠的空間能夠容納新的元素。最後将元素新增到數組，即vector的末尾。

#### 3.出棧pop

public synchronized e pop() {

    e       obj;

    int     len = size();

    obj = peek();

    removeelementat(len - 1);

    return obj;

出棧同樣是一個同步方法，先定義一個泛型對象obj，擷取到數組長度len，然後調用**peek()**方法，擷取棧頂的元素指派給obj，然後删除棧頂元素。

public synchronized e peek() {

    if (len == 0)

        throw new emptystackexception();

    return elementat(len - 1);

很顯然，peek()方法直接調用了vector的elementat方法，該方法不删除棧頂的元素。

#### 4.判斷棧是否為空

/**

 * 通過數組長度判斷棧是否為空。

 *

 * @return  <code>true</code> if and only if this stack contains

 *          no items; <code>false</code> otherwise.

 */

public boolean empty() {

    return size() == 0;

#### 5.查詢元素到棧頂的距離

 * returns the 1-based position where an object is on this stack.

 * if the object <tt>o</tt> occurs as an item in this stack, this

 * method returns the distance from the top of the stack of the

 * occurrence nearest the top of the stack; the topmost item on the

 * stack is considered to be at distance <tt>1</tt>. the <tt>equals</tt>

 * method is used to compare <tt>o</tt> to the

 * items in this stack.

 * @param   o   the desired object.

 * @return  the 1-based position from the top of the stack where

 *          the object is located; the return value <code>-1</code>

 *          indicates that the object is not on the stack.

public synchronized int search(object o) {

    int i = lastindexof(o);

    if (i >= 0) {

        return size() - i;

    }

    return -1;

一個同步方法，找到指定元素o到棧頂的距離，可以看到用到了lastindexof方法，如果找不到元素，則傳回-1。

## 三、總計

通過源碼我們可以看到vector底層是一個數組，說明stack的實作是通過數組來實作的，然後通過對數組的操作來模仿棧的各種功能。而且在源碼中vector的很多方法都是synchronized 的，也就是說是線程安全，是以說在多線程中是可以安全使用的，不過這樣效率上肯定是會降低的。