栈的链式存储结构，简称为链栈。
想想看，栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？
由于单链表有头指针，而栈顶指针也是必须的，那么干嘛不让他们合二为一呢，所以比较好的办法是把栈顶放到单链表的头部。
另外栈顶在头部了，那么单链表的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。
同样对于链栈来说，基本不存在栈满的情况，除非内存已经没有可用的空间了。
栈的链式存储结构与线性表的链式存储结构差不多，但是其相对比较简单，只在表尾进行操作。
刚好复习下之前学习的线性表中的链表。
但是链栈和线性表的链式存储结构是有区别的，链栈不需要头结点，有栈顶就可以了。
首先定义一个链栈的接口：
/// <summary> /// 链栈接口 /// </summary> public interface IChainStack<T> { /// <summary> /// 清空栈 /// </summary> /// <returns></returns> bool ClearStack(); /// <summary> /// 判断栈是否为空 /// </summary> /// <returns>true:空、false：不空</returns> bool IsEmptyStack(); /// <summary> /// 获取栈顶元素 /// </summary> /// <returns></returns> T GetTopStack(); /// <summary> /// 入栈 /// </summary> /// <returns></returns> bool PushStack(T val); /// <summary> /// 出栈 /// </summary> /// <returns></returns> bool PopStack(); /// <summary> /// 获取栈长度 /// </summary> /// <returns></returns> int LengthStack(); /// <summary> /// 判断栈是否已满 /// </summary> /// <returns></returns> bool IsFull(); /// <summary> /// 打印栈 /// </summary> void paint(); }
然后定义一个链栈的节点
/// <summary> /// 链栈节点类 /// </summary> public class ChainStackNode<T> { /// <summary> /// 链表中的数据域 /// </summary> public T data; /// <summary> /// 链表中的下一个节点的指针域 /// </summary> public ChainStackNode<T> Next; // 每个结点有两部分组成，指针+数据，第一个节点没有数据，只有指针，最后一个节点只有数据，没有指针。 // 那么构造函数需要有三次重载。 /// <summary> /// 中间节点构造函数 /// </summary> /// <param name="val"></param> /// <param name="index"></param> public ChainStackNode(T val, ChainStackNode<T> index) { this.data = val; this.Next = index; } /// <summary> /// 最后一个节点构造函数 /// </summary> /// <param name="val"></param> public ChainStackNode(T val) { this.data = val; this.Next = null; } /// <summary> /// 第一个节点构造函数 /// </summary> /// <param name="val"></param> /// <param name="index"></param> public ChainStackNode(ChainStackNode<T> index) { // 默认值 this.data = default(T); this.Next = index; } /// <summary> /// 定义一个空节点 /// </summary> /// <param name="val"></param> /// <param name="index"></param> public ChainStackNode() { this.data = default(T); this.Next = null; } }
最后我们定义一个类来实现上边定义的接口;实现链栈的操作功能。
public class ChainStackList<T> : IChainStack<T> { /// <summary> /// 存储栈顶指针，其是有指针，没有数据 /// </summary> public ChainStackNode<T> top = null; /// <summary> /// 栈数量 /// </summary> public int count = 0; public ChainStackList() { top = new ChainStackNode<T>(); count = 0; } /// <summary> /// 清空栈 /// </summary> /// <returns></returns> public bool ClearStack() { count = 0; top = null; return true; } /// <summary> /// 获取栈顶数据 /// </summary> /// <returns></returns> public T GetTopStack() { return top.Next.data; } /// <summary> /// 栈是否为空 /// </summary> /// <returns></returns> public bool IsEmptyStack() { if (top.Next == null || count == 0) { return true; } else { return false; } } /// <summary> /// 栈是已满,链接基本上不存在满栈的情况，因为满栈基本上意味着系统崩溃 /// </summary> /// <returns></returns> public bool IsFull() { if (top == null) { return true; } else { return false; } } /// <summary> /// 获取栈长度 /// </summary> /// <returns></returns> public int LengthStack() { return count; } /// <summary> /// 打印栈 /// </summary> public void paint() { ChainStackNode<T> tempTop = top; ChainStackNode<T> temp = new ChainStackNode<T>(); for (int i = 0; i < count+1; i++) { temp = tempTop.Next; Console.WriteLine("data:"+ tempTop.data+"index:"+top.Next); tempTop = temp; } } /// <summary> /// 出栈 /// </summary> /// <returns></returns> public bool PopStack() { if (IsEmptyStack()) { Console.WriteLine("链栈为空，无法弹出"); return false; } // 定义一个节点存储栈顶的下一个节点 ChainStackNode<T> temp = top.Next; // 现在栈顶的下一个节点等于原来栈顶下一个节点的先一个节点 top.Next = temp.Next; count--; return true; } /// <summary> /// 入栈 /// </summary> /// <param name="val">入栈数据</param> /// <returns></returns> public bool PushStack(T val) { ChainStackNode<T> temp = new ChainStackNode<T>(val); if (temp == null) { Console.WriteLine("栈已满"); return false; } // 将栈顶的下一个节点赋值给新节点 temp.Next = top.Next; // 将新节点赋值给栈顶的下一个值 top.Next = temp; count++; return true; } }
调用示例：
static void Main(string[] args) { ChainStackList<string> chainStrackList = new ChainStackList<string>(); chainStrackList.PushStack("11111"); chainStrackList.PushStack("22222"); chainStrackList.PushStack("33333"); chainStrackList.PushStack("44444"); chainStrackList.PushStack("55555"); Console.WriteLine("添加数据"); Console.WriteLine("========================================="); Console.WriteLine("打印数据"); chainStrackList.paint(); Console.WriteLine("========================================="); chainStrackList.PopStack(); chainStrackList.PopStack(); Console.WriteLine("弹出栈"); Console.WriteLine("========================================="); Console.WriteLine("打印数据"); chainStrackList.paint(); Console.WriteLine("========================================="); Console.WriteLine("获取栈顶数据："+ chainStrackList.GetTopStack()); Console.WriteLine("========================================="); Console.WriteLine("获取栈的长度：" + chainStrackList.LengthStack()); Console.WriteLine("========================================="); Console.ReadKey(); }
如上图所示：
在写链栈的时候，只需要搞清楚一件事情就可以了，栈顶top存储的是事实上的栈顶的指针。
Top.Next = 真正的栈顶。
那么添加数据时：
newNode.Next = top.Next；// 将栈顶的下一个节点赋值给新节点 top.Next = newNode；// 将新节点赋值给栈顶的下一个节点
删除数据时：
Temp = top.Next；// 定义一个节点存储栈顶的下一个节点 Top.next = temp.next；// 现在栈顶的下一个节点等于原来栈顶下一个节点的先一个节点
以上基本上就是链栈的精髓所在，最后放上一张上边代码最终运行的效果图：代码实例在文末，可下载。
