数据结构(C#)：堆栈

OGeek|极客世界-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

堆栈是一种后进先出的数据结构，在某些程序设计中经常用到。堆栈只能取得栈顶元素、压栈、出栈、取得栈内元素数量及判断是否为空等操作。
堆栈可以用顺序表、链表实现，有了前面顺序表及链表，堆栈实现非常简单，这里用单链表实现。
1.实现代码

/*
* File     :   Stack.cs
* Author   :   Zhenxing Zhou
* Date     :   2008-12-07
* Blog     :   http://www.xianfen.net/
*/
namespace Xianfen.Net.DataStructure
{
    public class Stack<T>
    {
        protected SingleLinkedList<T> m_List;

        public int Count
        {
            get { return m_List.Count; }
        }

        public bool IsEmpty
        {
            get { return m_List.IsEmpty; }
        }

        public Stack()
        {
            m_List = new SingleLinkedList<T>();
        }

        public Stack(T t)
        {
            m_List = new SingleLinkedList<T>(t);
        }

        public T Pop()
        {
            T t = m_List.GetTail();
            m_List.RemoveTail();

            return t;
        }

        public T Top()
        {
            return m_List.GetTail();
        }

        public void Push(T t)
        {
            m_List.AddTail(t);
        }
    }
}

2.应用示例
一个及其无聊的字符串翻转程序。

char[] ch = "hello world!".ToCharArray();
Stack<char> s = new Stack<char>();

foreach (char c in ch)
{
s.Push(c);
}

int idx = 0;
while (!s.IsEmpty)
{
ch[idx++] = s.Pop();
}

Console.WriteLine(new string(ch));