1 棧的基本實現（鏈式存儲）

對棧的鏈式存儲結構，我們可以參照單鏈表，為其設置一個頭結點。這裡，我們先來看看節點的定義：

（1）節點的定義實現

<code>/// <summary>
/// 基於鏈表的棧節點
/// /<summary>
/// <typeparam>
public class Node
{
    public T Item { get; set; }
    public Node Next { get; set; }

    public Node(T item)
{
        this.Item = item;
    }

    public Node()
{ }
}/<code>

（2）入棧操作的實現

實現Push方法，即向棧頂壓入一個元素，首先保存原先的位於棧頂的元素，然後新建一個新的棧頂元素，然後將該元素的下一個指向原先的棧頂元素。

<code>/// <summary>
/// 入棧
/// /<summary>
/// <param>新節點
public void Push(T item)
{
        Node oldNode = first;
        first = new Node();
        first.Item = item;
        first.Next = oldNode;

        index++;
}/<code>

（3）出棧操作的實現

實現Pop方法，首先保存棧頂元素的值，然後將棧頂元素設置為下一個元素：

<code>    /// <summary>
    /// 出棧
    /// /<summary>
    /// <returns>出棧元素/<returns>
    public T Pop()
    {
        T item = first.Item;
        first = first.Next;
        index--;

        return item;
    }/<code>

這裡還可以考慮將出棧元素的實例對象進行釋放資源操作。

（4）完整的代碼實現

<code>/// <summary>
/// 基於鏈表的棧節點
/// /<summary>
/// <typeparam>元素類型/<typeparam>
public class Node
{
    public T Item { get; set; }
    public Node Next { get; set; }

    public Node(T item)
{
        this.Item = item;
    }

    public Node()
{ }
}

/// <summary> 

/// 基於鏈表的棧實現
/// /<summary>
/// <typeparam>類型/<typeparam>
public class MyLinkStack
{
    private Node first;
    private int index;

    public MyLinkStack()
{
        this.first = null;
        this.index = 0;
    }

    /// <summary>
    /// 入棧
    /// /<summary>
    /// <param>新節點
    public void Push(T item)
{
        Node oldNode = first;
        first = new Node();
        first.Item = item;
        first.Next = oldNode;

        index++;
    }

    /// <summary>
    /// 出棧
    /// /<summary>
    /// <returns>出棧元素/<returns>
    public T Pop()
{
        T item = first.Item;
        first = first.Next;
        index--;

        return item;
    }

    /// <summary>
    /// 是否為空棧
    /// /<summary> 

    /// <returns>true/false/<returns>
    public bool IsEmpty()
{
        return this.index == 0;
    }

    /// <summary>
    /// 棧中節點個數
    /// /<summary>
    public int Size
    {
        get
        {
            return this.index;
        }
    }
}/<code>

（5）簡單的功能測試

這裡跟順序存儲結構的測試代碼一致，就不再貼出來，直接看運行結果吧：

2 棧的基本應用

棧的應用場景很多，最常見的莫過於遞歸操作了，另外在運算表達式的求值上也有應用。這裡看一個最經典的應用場景，進制轉換問題。講一個非負的十進制整數N轉換成其他D進制數是計算機計算的一個基本問題，如(135)10進制=(207)8進制。最簡單的解決辦法就是連續取模%和整除/，例如將10進制的50轉換為2進制數的過程如下圖所示：

由上圖的計算過程可知，D進制各位數的產生順序是從低位到高位，而輸出順序卻是從高位到低位，剛好和計算過程是相反的，因此可以利用棧進行逆序輸出。

<code>private static string DecConvert(int num, int dec)
{
    if (dec < 2 || dec > 16)
    {
        throw new ArgumentOutOfRangeException("dec", 
            "只支持將十進制數轉換為二進制到十六進制數");
    }

    MyLinkStack<char> stack = new MyLinkStack<char>();
    int residue;
    // 餘數入棧
    while (num != 0)
    {
        residue = num % dec;
        if (residue >= 10)
        {
            // 如果是轉換為16進制且餘數大於10則需要轉換為ABCDEF
            residue = residue + 55;
        }
        else
        {
            // 轉換為ASCII碼中的數字型字符1~9
            residue = residue + 48;
        }
        stack.Push((char)residue);
        num = num / dec;
    }
    // 反序出棧
    string result = string.Empty;
    while (stack.Size > 0)
    {
        result += stack.Pop();
    }
 

    return result;
}/<char>/<char>/<code>

這裡考慮到輸出，所以使用了char類型作為節點數據類型，因此需要考慮ASCII碼中的數字型字符與字母型字符。運行結果如下圖所示：

① 10進制數：350=>8進制數：536

② 10進制數：72=>16進制數：48

③ 10進制數：38=>2進制數：100110

3 .NET中的Stack

在.NET中，微軟已經為我們提供了一個強大的棧類型：Stack，這裡我們使用Reflector工具查看其具體實現，具體看看Push和Pop兩個方法，其他的各位童鞋可以自己去查看。

Push方法源碼

<code>public void Push(T item)
{
    if (this._size == this._array.Length)
    {
        T[] destinationArray = new T[(this._array.Length == 0) ? 4 : (2 * this._array.Length)];
        Array.Copy(this._array, 0, destinationArray, 0, this._size);
        this._array = destinationArray;
    }
    this._array[this._size++] = item;
    this._version++;
}/<code>

Pop方法源碼

<code>public T Pop()
{ 

    if (this._size == 0)
    {
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack);
    }
    this._version++;
    T local = this._array[--this._size];
    this._array[this._size] = default(T);
    return local;
}/<code>

可以看出，在.NET中Stack的實現是基於數組來實現的，在初始化時為其設置了一個默認的數組大小，在Push方法中當元素個數達到數組長度時，擴充2倍容量，然後將原數組拷貝到新的數組中。Pop方法中則跟我們剛剛實現的代碼基本相同。