C#数据结构与算法之栈浅析

C#数据结构与算法之栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线形表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来，它只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。

C#数据结构与算法之栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO表）。

C#数据结构与算法之栈1、进栈（PUSH）算法

◆若TOP≥ｎ时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；

◆置TOP=TOP+1（栈指针加１，指向进栈地址）；

◆S(TOP)=X，结束（X为新进栈的元素）；

C#数据结构与算法之栈2、退栈（POP）算法

◆若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；

◆X=S(SOP)，（退栈后的元素赋给X）；

◆TOP=TOP-1，结束（栈指针减１，指向栈顶）。

C#数据结构与算法之栈的实现接口：

public interface IStack<T>  


{  



    int Length();  




    bool IsEmpty();  




    void Clear();  




    void Push(T items);  



    T Pop();  


    T GetPopValue();  


} 

下面的代码是C#数据结构与算法之栈的实现的类：

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];  



    }  


 } 

下面是C#数据结构与算法之栈进行测试:

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)  



{  


    Console.WriteLine(ex.Message);  


    Console.ReadLine();  


}