每天5分钟，学习数据结构

介绍了栈的基本概念及其顺序存储方式的实现，本篇将会介绍链式存储方式的实现 以及 一个应用案例。

1 栈的基本实现（链式存储）

对栈的链式存储结构，我们可以参照单链表，为其设置一个头结点。这里，我们先来看看节点的定义：

（1）节点的定义实现

<code>/// <summary>
/// 基于链表的栈节点
/// /<summary>
/// <typeparam>
public class Node
{
    public T Item { get; set; }
    public Node Next { get; set; }

    public Node(T item)
{
        this.Item = item;
    }

    public Node()
{ }
}/<code>

（2）入栈操作的实现

实现Push方法，即向栈顶压入一个元素，首先保存原先的位于栈顶的元素，然后新建一个新的栈顶元素，然后将该元素的下一个指向原先的栈顶元素。

<code>/// <summary>
/// 入栈
/// /<summary>
/// <param>新节点
public void Push(T item)
{
        Node oldNode = first;
        first = new Node();
        first.Item = item;
        first.Next = oldNode;

        index++;
}/<code>

（3）出栈操作的实现

实现Pop方法，首先保存栈顶元素的值，然后将栈顶元素设置为下一个元素：

<code>    /// <summary>
    /// 出栈
    /// /<summary>
    /// <returns>出栈元素/<returns>
    public T Pop()
    {
        T item = first.Item;
        first = first.Next;
        index--;

        return item;
    }/<code>

这里还可以考虑将出栈元素的实例对象进行释放资源操作。

（4）完整的代码实现

<code>/// <summary>
/// 基于链表的栈节点
/// /<summary>
/// <typeparam>元素类型/<typeparam>
public class Node
{
    public T Item { get; set; }
    public Node Next { get; set; }

    public Node(T item)
{
        this.Item = item;
    }

    public Node()
{ }
}

/// <summary> 

/// 基于链表的栈实现
/// /<summary>
/// <typeparam>类型/<typeparam>
public class MyLinkStack
{
    private Node first;
    private int index;

    public MyLinkStack()
{
        this.first = null;
        this.index = 0;
    }

    /// <summary>
    /// 入栈
    /// /<summary>
    /// <param>新节点
    public void Push(T item)
{
        Node oldNode = first;
        first = new Node();
        first.Item = item;
        first.Next = oldNode;

        index++;
    }

    /// <summary>
    /// 出栈
    /// /<summary>
    /// <returns>出栈元素/<returns>
    public T Pop()
{
        T item = first.Item;
        first = first.Next;
        index--;

        return item;
    }

    /// <summary>
    /// 是否为空栈
    /// /<summary> 

    /// <returns>true/false/<returns>
    public bool IsEmpty()
{
        return this.index == 0;
    }

    /// <summary>
    /// 栈中节点个数
    /// /<summary>
    public int Size
    {
        get
        {
            return this.index;
        }
    }
}/<code>

（5）简单的功能测试

这里跟顺序存储结构的测试代码一致，就不再贴出来，直接看运行结果吧：

2 栈的基本应用

栈的应用场景很多，最常见的莫过于递归操作了，另外在运算表达式的求值上也有应用。这里看一个最经典的应用场景，进制转换问题。讲一个非负的十进制整数N转换成其他D进制数是计算机计算的一个基本问题，如(135)10进制=(207)8进制。最简单的解决办法就是连续取模%和整除/，例如将10进制的50转换为2进制数的过程如下图所示：

由上图的计算过程可知，D进制各位数的产生顺序是从低位到高位，而输出顺序却是从高位到低位，刚好和计算过程是相反的，因此可以利用栈进行逆序输出。

<code>private static string DecConvert(int num, int dec)
{
    if (dec < 2 || dec > 16)
    {
        throw new ArgumentOutOfRangeException("dec", 
            "只支持将十进制数转换为二进制到十六进制数");
    }

    MyLinkStack<char> stack = new MyLinkStack<char>();
    int residue;
    // 余数入栈
    while (num != 0)
    {
        residue = num % dec;
        if (residue >= 10)
        {
            // 如果是转换为16进制且余数大于10则需要转换为ABCDEF
            residue = residue + 55;
        }
        else
        {
            // 转换为ASCII码中的数字型字符1~9
            residue = residue + 48;
        }
        stack.Push((char)residue);
        num = num / dec;
    }
    // 反序出栈
    string result = string.Empty;
    while (stack.Size > 0)
    {
        result += stack.Pop();
    }
 

    return result;
}/<char>/<char>/<code>

这里考虑到输出，所以使用了char类型作为节点数据类型，因此需要考虑ASCII码中的数字型字符与字母型字符。运行结果如下图所示：

① 10进制数：350=>8进制数：536

② 10进制数：72=>16进制数：48

③ 10进制数：38=>2进制数：100110

3 .NET中的Stack

在.NET中，微软已经为我们提供了一个强大的栈类型：Stack，这里我们使用Reflector工具查看其具体实现，具体看看Push和Pop两个方法，其他的各位童鞋可以自己去查看。

Push方法源码

<code>public void Push(T item)
{
    if (this._size == this._array.Length)
    {
        T[] destinationArray = new T[(this._array.Length == 0) ? 4 : (2 * this._array.Length)];
        Array.Copy(this._array, 0, destinationArray, 0, this._size);
        this._array = destinationArray;
    }
    this._array[this._size++] = item;
    this._version++;
}/<code>

Pop方法源码

<code>public T Pop()
{ 

    if (this._size == 0)
    {
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack);
    }
    this._version++;
    T local = this._array[--this._size];
    this._array[this._size] = default(T);
    return local;
}/<code>

可以看出，在.NET中Stack的实现是基于数组来实现的，在初始化时为其设置了一个默认的数组大小，在Push方法中当元素个数达到数组长度时，扩充2倍容量，然后将原数组拷贝到新的数组中。Pop方法中则跟我们刚刚实现的代码基本相同。

3 小结

本文介绍了栈的链式存储的实现以及一个应用案例，最后带你看了.NET中的Stack的部分源码，下一篇我们会开始学习另一种操作受限的线性表：队列！

程杰，《大话数据结构》

陈广，《数据结构（C#语言描述）》

段恩泽，《数据结构（C#语言版）》

往期精彩

专栏：EdisonTalk（爱迪生说）

本文作者EdisonZhou，架构师，阿里云MVP，博客园"推荐博客"博主(Top10)，Scrum联盟认证CSM，.NET Core实践者与布道师，爱好阅读与分享。

本文首发于EdisonZhou的公众号“恰童鞋骚年”，欢迎关注，第一时间获得更多内容分享。

閱讀更多 EdisonTalk 的文章

關鍵字: 数据结构 分钟 每天