链栈的结构

链栈是堆栈的链式存储结构，它的结构和单链表的结构一模一样，每个节点都有一个唯一的后驱节点，其中头节点作为栈顶，尾节点作为栈底。它的入栈和出栈只能在头节点进行，也就是说，它是受限制的单链表。链栈相对于顺序栈最大的优点就是，它可以动态分配内存空间，原则上只要内存允许，不会出现栈满的情况。
也可以这么理解，如果一个单链表只允许在头节点进行增加和删除操作，那么这个单链表就可以叫做链栈，链栈的具体结构图如下：

链栈的定义

我们在程序中声明Node类和LinkedStack类。Node类声明链栈中每个节点的类型。LinkedStack类封装了链栈相关的算法。具体示例代码如下：

public class Node
{
    public int Data;//数据元素
    public Node Next;//指向下一个节点的指针
    public Node(int data)
    {
        this.Data = data;
    }
}
/// <summary>
/// 链栈
/// </summary>
internal class LinkedStack
{
    Node top;//栈顶
    int _length;//长度
}

在LinkedStack中我们声明了一个栈顶指针top，它代表栈顶元素。_length变量代表链栈中节点的数量。

算法1：入栈

入栈分两种情况
第一种：首次入栈，top==null的情况下，直接给top赋值即可 top=newNode;
第二中：非首次入栈，top!=null，则需要newNode.Next=top;top=newNode; 两个步骤。

public void Push(int data)
{
    Node newNode = new Node(data);
    if (top == null)
    {
        top = newNode;
    }
    else
    {
        newNode.Next = top;
        top = newNode;
    }
    _length++;
}

算法2：出栈

出栈需要先判断栈是否为空，如果为空，则抛出异常。如果不为空，则直接执行返回当前top指针并且将top指向top的下一个节点top=top.Next;

public Node Pop()
{
    if (top == null)
    {
        return null;
    }

    Node node = top;
    top = top.Next;
    _length--;
    return node;
}

算法3：获取栈顶元素

先判断栈顶是否为空，如果不为空，直接返回站点元素即可。

public Node Peek()
{
    if (top == null)
    {
        throw new Exception("空栈！");
    }
    return top;
}

算法4：栈是否为空

top==null的时候栈是空的。

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

示例代码地址

https://gitee.com/jiamingyuanjin_admin/data_struct/blob/master/DataStruct/06LinkedStack.cs

总结

链栈和顺序栈相比，最大的优点就是可以动态分配存储空间。理论上只要内存不受限制，就不存在栈满的情况，但它的缺点就是需要额外的指针字段，空间使用率较低。

链栈