1 棧的初體驗

現實生活中的事情往往都能總結歸納成一定的數據結構，例如餐館中餐盤的堆疊和使用，羽毛球筒裡裝的羽毛球等都是典型的棧結構。而在.NET中，值類型在線程棧上進行分配，引用類型在託管堆上進行分配，本文所說的“棧”正是這種數據結構。棧和隊列都是常用的數據結構，它們的邏輯結構與線性表相通，不同之處則在於操作受某種特殊限制。因此，棧和隊列也被稱為操作受限的線性表。這裡，我們首先來了解一下棧。

棧的基本特徵

棧（stack）是限定僅在表尾進行插入和刪除操作的線性表。其特點是：“後進先出“或“先進後出”。

棧的基本操作

（1）棧的插入操作，叫作進棧，也稱壓棧、入棧：

（2）棧的刪除操作，叫作出棧，也有的叫作彈棧：

2 棧的基本實現（順序存儲）

既然棧屬於特殊的線性表，那麼其實現也會有兩種形式：順序存儲結構和鏈式存儲結構。首先，對於Stack，我們希望能夠提供以下幾個方法供調用：

Stack()

創建一個空的棧

void Push(T s)

往棧中添加一個新的元素

T Pop()

移除並返回最近添加的元素

bool IsEmpty()

棧是否為空

int Size()

棧中元素的個數

對於順序存儲，我們可以參照順序表的實現方式，藉助數組來存儲各個數據元素，然後對這個數組進行一定的封裝，提供指定的操作對數據元素進行插入和刪除即可。

（1）入棧操作實現

代碼如下：

<code>/// <summary>
/// 入棧
/// /<summary>
/// <param>節點元素
public void Push(T node)
{
    if (index == nodes.Length)
    {
        // 增大數組容量
        ResizeCapacity(nodes.Length * 2);
    }

    nodes[index] = node; 

    index++;
}/<code>

藉助數組來實現入棧操作，其關鍵之處就在於top指針的移動。這裡index初始值為0，每次入棧一個則將index加1，即指向下一個即將入棧的位置。由於這裡採用了動態擴容的機制，所以沒有判斷棧中元素個數是否達到了最大值。

（2）出棧操作實現

出棧操作需要先去的要出棧的元素，然後將index減1，即指向下一個即將出棧的元素的位置。

<code>/// <summary>
/// 出棧
/// /<summary>
/// <returns>出棧節點元素/<returns>
public T Pop()
{
    if(index == 0)
    {
        return default(T);
    }

    T node = nodes[index - 1];
    index--;
    nodes[index] = default(T);

    if (index > 0 && index == nodes.Length / 4)
    {
        // 縮小數組容量
        ResizeCapacity(nodes.Length / 2);
    }
    return node;
}/<code>

這裡首先需要判斷index是否已經到達了最小值，出棧的元素位置需要置為默認值（如果是int數組，那麼會重置為0），最後返回出棧的元素對象。這裡當元素個數小於數組的四分之一時會進行容量收縮操作。

（3）完整的類實現

<code>/// <summary>
/// 基於數組的棧實現
/// /<summary>
/// <typeparam>類型/<typeparam>
public class MyArrayStack
{
    private T[] nodes;
    private int index;

    public MyArrayStack(int capacity)
{
        this.nodes = new T[capacity];
        this.index = 0;
    }

    /// <summary>
    /// 入棧
    /// /<summary>
    /// <param>節點元素
    public void Push(T node)
{
        if (index == nodes.Length)
        {
            // 增大數組容量
            ResizeCapacity(nodes.Length * 2);
        }

        nodes[index] = node;
        index++;
    }
 

    /// <summary>
    /// 出棧
    /// /<summary>
    /// <returns>出棧節點元素/<returns>
    public T Pop()
{
        if(index == 0)
        {
            return default(T);
        }

        T node = nodes[index - 1];
        index--;
        nodes[index] = default(T);

        if (index > 0 && index == nodes.Length / 4)
        {
            // 縮小數組容量
            ResizeCapacity(nodes.Length / 2);
        }
        return node;
    }

    /// <summary>
    /// 重置數組大小
    /// /<summary>
    /// <param>新的容量
    private void ResizeCapacity(int newCapacity)
{
        T[] newNodes = new T[newCapacity];
        if(newCapacity > nodes.Length)
        {
            for (int i = 0; i < nodes.Length; i++)
            {
                newNodes[i] = nodes[i];
            }
        }
        else
        {
            for (int i = 0; i < newCapacity; i++)
            {
                newNodes[i] = nodes[i];
            }
        }

        nodes = newNodes;
    }
 

    /// <summary>
    /// 棧是否為空
    /// /<summary>
    /// <returns>true/false/<returns>
    public bool IsEmpty()
{
        return this.index == 0;
    }

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

（4）簡單的功能測試

首先，順序入棧10個隨機數，輸出其元素個數與是否為空；

然後依次出棧，輸出每個數據元素；

最後，再入棧15個隨機數並出棧輸出。

<code>/// <summary>
/// 基於數組的棧的測試
/// /<summary>
static void StackWithArrayTest()
{
    MyArrayStack stack = new MyArrayStack(10);
    Console.WriteLine(stack.IsEmpty()); 


    Random rand = new Random();
    for (int i = 0; i < 10; i++)
    {
        stack.Push(rand.Next(1, 10));
    }
    Console.WriteLine("IsEmpty:{0}",stack.IsEmpty());
    Console.WriteLine("Size:{0}", stack.Size);
    Console.WriteLine("-------------------------------");

    for (int i = 0; i < 10; i++)
    {
        int node = stack.Pop();
        Console.Write(node + " ");
    }
    Console.WriteLine();
    Console.WriteLine("IsEmpty:{0}", stack.IsEmpty());
    Console.WriteLine("Size:{0}", stack.Size);
    Console.WriteLine("-------------------------------");

    for (int i = 0; i < 15; i++)
    {
        stack.Push(rand.Next(1, 15));
    }
    for (int i = 0; i < 15; i++)
    {
        int node = stack.Pop();
        Console.Write(node + " ");
    }
    Console.WriteLine();
}/<code>