C# 數據結構與算法系列(四) 棧

棧（stack）在計算機科學中是限定僅在表尾進行插入或刪除操作的線形表。它按照後進先出的原則存儲數據，先進入的數據被壓入棧底，最後的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最後一個數據被第一個讀出來，它只能在某一端插入和刪除的特殊線性表。用桶堆積物品，先堆進來的壓在底下，隨後一件一件往堆。取走時，只能從上面一件一件取。堆和取都在頂部進行，底部一般是不動的。

棧就是一種類似桶堆積物品的數據結構，進行刪除和插入的一端稱棧頂，另一堆稱棧底。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。 棧也稱為後進先出表（LIFO表）。

1、進棧（PUSH）算法
1、若TOP≥ｎ時，則給出溢出信息，作出錯處理（進棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）；
2、置TOP=TOP+1（棧指針加１，指向進棧地址）；
3、S(TOP)=X，結束（X為新進棧的元素）；

2、退棧（POP）算法
1、若TOP≤0，則給出下溢信息，作出錯處理(退棧前先檢查是否已為空棧， 空則下溢；不空則作②)；
2、X=S(SOP)，（退棧後的元素賦給X）；
3、TOP=TOP-1，結束（棧指針減１，指向棧頂）。

下面看一下棧的實現接口：
   public interface IStack<T>
   {
       int Length();
       bool IsEmpty();
       void Clear();
       void Push(T items);
       T Pop();
       T GetPopValue();
   }

下面的代碼是棧的實現的類：
Code

   public class JStack<T> : IStack<T>
   {
       private int size;
       private T[] item;
       private int top;

       public T this[int index]
       {
           get { return item[index]; }
           set { item[index] = value; }
       }

       public int Size
       {
           get { return size; }
           set { size = value; }
       }

       public int Top
       {
           get { return top; }
       }

       public JStack(int length)
       {
           top = -1;
           size = length;
           item = new T[length];
       }

       public int Length()
       {
           return top + 1;
       }      

       public bool IsEmpty()
       {
           return (top == -1);
       }

       public void Clear()
       {
           top = -1;
       }

       public void Push(T items)
       {
           if (top < size - 1)
           {
               item[++top] = items;
           }
       }

       public T Pop()
       {
           T tmp = default(T);
           if (!IsEmpty())
           {
               tmp = item[top];
           }
           return tmp;
       }

       public T GetPopValue()
       {
           if (IsEmpty())
           {
               throw new ArgumentNullException("棧已經為空", "Item Null");
           }
           return item[top];
       }
    }

下面進行測試:

Code
           try
           {
               JStack<string> js = new JStack<string>(20);
               Console.WriteLine("------棧剛初始化完成----");
               Console.WriteLine(js.Length());
               Console.WriteLine(js.IsEmpty().ToString());
               js.Push("A");
               js.Push("B");
               js.Push("C");
               js.Push("D");
               Console.WriteLine("------棧已經插入數據----");
               Console.WriteLine(js.Length());
               Console.WriteLine(js.IsEmpty().ToString());

               Console.WriteLine("------取棧頂數據----");
               Console.WriteLine(js.GetPopValue().ToString());

               Console.WriteLine("------清棧----");
               js.Clear();
               Console.WriteLine(js.GetPopValue().ToString());
               Console.ReadLine();
           }
           catch (Exception ex)
           {