栈

栈和队列是非常重要的两种数据结构，在软件设计中应用很多。栈和队列也是线性结构，线性表、栈和队列这三种数据结构的数据元素以及数据元素间的逻辑关系完全相同，差别是线性表的操作不受限制，而栈和队列的操作受到限制。栈的操作只能在表的一端进行，队列的插入操作在表的一端进行而其它操作在表的另一端进行，所以，把栈和队列称为操作受限的线性表。

栈(Stack)是操作限定在表的尾端进行的线性表。表尾由于要进行插入、删除等操作，所以，它具有特殊的含义，把表尾称为栈顶（ Top），另一端是固定的，叫栈底（ Bottom）。当栈中没有数据元素时叫空栈(Empty Stack)。
栈通常记为： S= (a1,a2,…,an)，S是英文单词stack的第 1 个字母。a1为栈底元素，an为栈顶元素。这n个数据元素按照a1,a2,…,an的顺序依次入栈，而出栈的次序相反，an第一个出栈，a1最后一个出栈。所以，栈的操作是按照后进先出(Last In First Out，简称LIFO)或先进后出(First In Last Out，简称FILO)的原则进行的，因此，栈又称为LIFO表或FILO表。栈的操作示意图如图所示。

BCL中的栈

C#2.0 一下版本只提供了非泛型的Stack类(存储object类型)

C#2.0 提供了泛型的Stack<T>类

重要的方法如下

1.Push()入栈（添加数据）

2.Pop()出栈（删除数据，返回被删除的数据）

3.Peek()取得栈顶的数据，不删除

4.Clear()清空所有数据

5.Count取得栈中数据的个数

using System;
using System.Collections.Generic;

namespace StackTest
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            Stack<char> charStack = new Stack<char> ();
            charStack.Push (char.Parse("a"));
            charStack.Push (char.Parse("b"));
            charStack.Push (char.Parse("c"));
            charStack.Push('d');
            foreach (char letter in charStack) {
                Console.WriteLine (letter);
            }

            Console.WriteLine (charStack.Peek().ToString());//取得栈顶元素, 勿在空栈中调用peek
        }
    }
}

顺序栈

用一片连续的存储空间来存储栈中的数据元素(使用数组)，这样的栈称为顺序栈(Sequence Stack)。类似于顺序表，用一维数组来存放顺序栈中的数据元素。栈顶指示器 top 设在数组下标为 0 的端， top 随着插入和删除而变化，当栈为空时，top=-1。下图是顺序栈的栈顶指示器 top 与栈中数据元素的关系图。

using System;

namespace MyStackDS
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            MyStack<char> charStack = new MyStack<char> ();
            charStack.Push ('a');
            charStack.Push ('b');
            charStack.Push ('c');
            charStack.Push ('d');
            charStack.Push ('e');
            charStack.Push ('f');
            charStack.Push ('g');

            Console.WriteLine (charStack.ToString ());

            charStack.Pop ();

            Console.WriteLine (charStack.ToString ());

            Console.WriteLine (charStack.peek ());

            Console.WriteLine (charStack.GetLength ());

            charStack.Clear ();

            Console.WriteLine (charStack.ToString ());

            Console.WriteLine (charStack.IsEmpty ());
        }
    }

    class MyStack<T>:IMyStack<T> {
        T[] datas;
        int count = 0;

        public MyStack() {
            datas = new T[10];
        }

        public int Count { 
            get{
                return count;
            }
        }

        public int GetLength() {
            return count;
        }

        public bool IsEmpty() {
            return count == 0;
        }

        public void Clear() {
            datas = null;
            count = 0;
        }

        public void Push(T item) {
            if (count == datas.Length) {
                Console.WriteLine ("栈已满，无法再添加新元素");
            } else {
                datas [count] = item;
                count++;
            }
        }

        public void Pop() {
            if (count == 0) {
                Console.WriteLine ("栈已空，没有元素可以移除");
            } else {
                datas [count - 1] = default(T);
                count--;
            }
        }

        public T peek() {
            if (datas != null) {
                if (datas.Length > 0) {
                    return datas [0];
                }
            }

            return default(T);
        }

        public override string ToString ()
        {
            string str = "";
            if (datas == null) {
                return "stack empty";
            }
            foreach(T data in datas) {
                str += data.ToString () + ",";
            }
            str.Remove (str.Length - 1);
            return str;
        }
    }

    interface IMyStack<T> {
        int Count { get; }
        int GetLength();
        bool IsEmpty();
        void Clear();
        void Push(T item);
        void Pop();
        T peek();
    }
}

链栈

栈的另外一种存储方式是链式存储，这样的栈称为链栈(Linked Stack)。链栈通常用单链表来表示，它的实现是单链表的简化。所以，链栈结点的结构与单链表结点的结构一样。由于链栈的操作只是在一端进行，为了操作方便，把栈顶设在链表的头部，并且不需要头结点。

using System;

namespace MyLinkStackDS
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            MyLinkStack<char> charStack = new MyLinkStack<char> ();
            Console.WriteLine (charStack.ToString ());

            charStack.Push ('a');
            charStack.Push ('b');
            charStack.Push ('c');
            charStack.Push ('d');
            charStack.Push ('e');
            charStack.Push ('f');
            charStack.Push ('g');

            Console.WriteLine (charStack.ToString ());

            charStack.Pop ();

            Console.WriteLine (charStack.ToString ());

            Console.WriteLine (charStack.peek ().ToString());

            Console.WriteLine (charStack.GetLength ());

            charStack.Clear ();

            Console.WriteLine (charStack.ToString ());

            Console.WriteLine (charStack.IsEmpty ());
        }
    }

    class MyLinkStack<T>:IMyStack<T> {

        private LinkNode<T> topNode;

        public MyLinkStack() {

        }

        public int Count { 
            get{
                return GetLength();
            }
        }

        public int GetLength() {
            LinkNode<T> temp = topNode;
            int count = 1;
            while (true) {
                if (temp.Next != null) {
                    temp = temp.Next;
                    count++;
                } else {
                    break;
                }
            }

            return count;
        }

        public bool IsEmpty() {
            return topNode == null;
        }

        public void Clear() {
            topNode = null;
        }

        public void Push(T item) {
            if (topNode == null) {
                topNode = new LinkNode<T> ();
                topNode.Data = item;
            } else {
                LinkNode<T> temp = topNode;
                while (true) {
                    if (temp.Next != null) {
                        temp = temp.Next;
                    } else {
                        break;
                    }
                }

                LinkNode<T> nextItem = new LinkNode<T> (item);
                temp.Next = nextItem;
            }
        }

        public void Pop() {
            if (topNode != null) {
                LinkNode<T> temp = topNode;
                LinkNode<T> preNode = new LinkNode<T>();
                while (true) {
                    if (temp.Next != null) {
                        preNode = temp;
                        temp = temp.Next;
                    } else {
                        break;
                    }
                }
                if (preNode != null) {
                    preNode.Next = null;
                }

            } else {
                Console.WriteLine ("栈已空，没有元素可以移除");
            }
        }

        public T peek() {
            if (topNode != null) {
                return topNode.Data;
            }

            return default(T);
        }

        public override string ToString ()
        {
            string str = "";
            if (topNode == null) {
                return "stack empty";
            }
            LinkNode<T> temp = topNode;
            str += topNode.Data + ",";
            while (true) {
                if (temp.Next != null) {
                    temp = temp.Next;
                    str += temp.Data + ",";
                } else {
                    break;
                }
            }
            str = str.Remove (str.Length - 1);
            return str;
        }
    }

    interface IMyStack<T> {
        int Count { get; }
        int GetLength();
        bool IsEmpty();
        void Clear();
        void Push(T item);
        void Pop();
        T peek();
    }

    class LinkNode<T> {
        private T data;
        private LinkNode<T> next;

        public LinkNode(T value) {
            data = value;
        }

        public LinkNode(T value, LinkNode<T> next) {
            data = value;
            this.next = next;
        }

        public LinkNode(LinkNode<T> next) {
            this.next = next;
        }

        public LinkNode() {
            data = default(T);
            next = null;
        }

        public T Data {
            get { return data; }
            set { data = value; }
        }

        public LinkNode<T> Next {
            get { return next; }
            set { next = value; }
        }
    } 
}