堆栈是一种后进先出的数据结构,在某些程序设计中经常用到。堆栈只能取得栈顶元素、压栈、出栈、取得栈内元素数量及判断是否为空等操作。
堆栈可以用顺序表、链表实现,有了前面顺序表及链表,堆栈实现非常简单,这里用单链表实现。
1.实现代码
堆栈可以用顺序表、链表实现,有了前面顺序表及链表,堆栈实现非常简单,这里用单链表实现。
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;
{
get { return m_List.Count; }
}
{
get { return m_List.IsEmpty; }
}
{
m_List = new SingleLinkedList<T>();
}
{
m_List = new SingleLinkedList<T>(t);
}
{
T t = m_List.GetTail();
m_List.RemoveTail();
}
{
return m_List.GetTail();
}
{
m_List.AddTail(t);
}
}
}
* 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();
}
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));