首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构基础温故-2.栈

数据结构基础温故-2.栈

作者头像
Edison Zhou
发布2018-08-20 15:57:28
3550
发布2018-08-20 15:57:28
举报
文章被收录于专栏:EdisonTalkEdisonTalk

现实生活中的事情往往都能总结归纳成一定的数据结构,例如餐馆中餐盘的堆叠和使用,羽毛球筒里装的羽毛球等都是典型的栈结构。而在.NET中,值类型在线程栈上进行分配,引用类型在托管堆上进行分配,本文所说的“栈”正是这种数据结构。栈和队列都是常用的数据结构,它们的逻辑结构与线性表相通,不同之处则在于操作受某种特殊限制。因此,栈和队列也被称为操作受限的线性表。这里,我们首先来了解一下栈。

一、栈的概念及操作

1.1 栈的基本特征

(stack)是限定仅在表尾进行插入和删除操作的线性表。其特点是:”后进先出“或”先进后出“。

1.2 栈的基本操作

  (1)栈的插入操作,叫作进栈,也称压栈、入栈:

  (2)栈的删除操作,叫作出栈,也有的叫作弹栈:

二、栈的基本实现

  既然栈属于特殊的线性表,那么其实现也会有两种形式:顺序存储结构和链式存储结构。首先,对于Stack,我们希望能够提供以下几个方法供调用:

Stack<T>()

创建一个空的栈

void Push(T s)

往栈中添加一个新的元素

T Pop()

移除并返回最近添加的元素

bool IsEmpty()

栈是否为空

int Size()

栈中元素的个数

2.1 栈的顺序存储实现

  对于顺序存储,我们可以参照顺序表的实现方式,借助数组来存储各个数据元素,然后对这个数组进行一定的封装,提供指定的操作对数据元素进行插入和删除即可。

  (1)入栈操作实现

        /// <summary>
        /// 入栈
        /// </summary>
        /// <param name="node">节点元素</param>
        public void Push(T node)
        {
            if (index == nodes.Length)
            {
                // 增大数组容量
                ResizeCapacity(nodes.Length * 2);
            }

            nodes[index] = node;
            index++;
        }

  借助数组来实现入栈操作,其关键之处就在于top指针的移动。这里index初始值为0,每次入栈一个则将index加1,即指向下一个即将入栈的位置。由于这里采用了动态扩容的机制,所以没有判断栈中元素个数是否达到了最大值。

  (2)出栈操作实现

  出栈操作需要先去的要出栈的元素,然后将index减1,即指向下一个即将出栈的元素的位置。

        /// <summary>
        /// 出栈
        /// </summary>
        /// <returns>出栈节点元素</returns>
        public T Pop()
        {
            if(index == 0)
            {
                return default(T);
            }

            T node = nodes[index - 1];
            index--;
            nodes[index] = default(T);

            if (index > 0 && index == nodes.Length / 4)
            {
                // 缩小数组容量
                ResizeCapacity(nodes.Length / 2);
            }
            return node;
        }

  这里首先需要判断index是否已经到达了最小值,出栈的元素位置需要置为默认值(如果是int数组,那么会重置为0),最后返回出栈的元素对象。这里当元素个数小于数组的四分之一时会进行容量收缩操作。

  (3)完整的类实现

    /// <summary>
    /// 基于数组的栈实现
    /// </summary>
    /// <typeparam name="T">类型</typeparam>
    public class MyArrayStack<T>
    {
        private T[] nodes;
        private int index;

        public MyArrayStack(int capacity)
        {
            this.nodes = new T[capacity];
            this.index = 0;
        }

        /// <summary>
        /// 入栈
        /// </summary>
        /// <param name="node">节点元素</param>
        public void Push(T node)
        {
            if (index == nodes.Length)
            {
                // 增大数组容量
                ResizeCapacity(nodes.Length * 2);
            }

            nodes[index] = node;
            index++;
        }

        /// <summary>
        /// 出栈
        /// </summary>
        /// <returns>出栈节点元素</returns>
        public T Pop()
        {
            if(index == 0)
            {
                return default(T);
            }

            T node = nodes[index - 1];
            index--;
            nodes[index] = default(T);

            if (index > 0 && index == nodes.Length / 4)
            {
                // 缩小数组容量
                ResizeCapacity(nodes.Length / 2);
            }
            return node;
        }

        /// <summary>
        /// 重置数组大小
        /// </summary>
        /// <param name="newCapacity">新的容量</param>
        private void ResizeCapacity(int newCapacity)
        {
            T[] newNodes = new T[newCapacity];
            if(newCapacity > nodes.Length)
            {
                for (int i = 0; i < nodes.Length; i++)
                {
                    newNodes[i] = nodes[i];
                }
            }
            else
            {
                for (int i = 0; i < newCapacity; i++)
                {
                    newNodes[i] = nodes[i];
                }
            }

            nodes = newNodes;
        }

        /// <summary>
        /// 栈是否为空
        /// </summary>
        /// <returns>true/false</returns>
        public bool IsEmpty()
        {
            return this.index == 0;
        }

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

  (4)简单的功能测试

  首先,顺序入栈10个随机数,输出其元素个数与是否为空;然后依次出栈,输出每个数据元素;最后,再入栈15个随机数并出栈输出。

        /// <summary>
        /// 基于数组的栈的测试
        /// </summary>
        static void StackWithArrayTest()
        {
            MyArrayStack<int> stack = new MyArrayStack<int>(10);
            Console.WriteLine(stack.IsEmpty());

            Random rand = new Random();
            for (int i = 0; i < 10; i++)
            {
                stack.Push(rand.Next(1, 10));
            }
            Console.WriteLine("IsEmpty:{0}",stack.IsEmpty());
            Console.WriteLine("Size:{0}", stack.Size);
            Console.WriteLine("-------------------------------");

            for (int i = 0; i < 10; i++)
            {
                int node = stack.Pop();
                Console.Write(node + " ");
            }
            Console.WriteLine();
            Console.WriteLine("IsEmpty:{0}", stack.IsEmpty());
            Console.WriteLine("Size:{0}", stack.Size);
            Console.WriteLine("-------------------------------");

            for (int i = 0; i < 15; i++)
            {
                stack.Push(rand.Next(1, 15));
            }
            for (int i = 0; i < 15; i++)
            {
                int node = stack.Pop();
                Console.Write(node + " ");
            }
            Console.WriteLine();
        }

  运行结果如下所示:

2.2 栈的链式存储实现

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

  (1)节点的定义实现

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

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

        public Node()
        { }
    }

  (2)入栈操作的实现

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

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

         index++;
     }

  (3)出栈操作的实现

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

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

        return item;
    }

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

  (4)完整的代码实现

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

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

        public Node()
        { }
    }

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

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

        /// <summary>
        /// 入栈
        /// </summary>
        /// <param name="item">新节点</param>
        public void Push(T item)
        {
            Node<T> oldNode = first;
            first = new Node<T>();
            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;
            }
        }
    }

  (5)简单的功能测试

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

三、栈的基本应用

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

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

        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类型作为节点数据类型,因此需要考虑ASCII码中的数字型字符与字母型字符。运行结果如下图所示:

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

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

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

四、.NET中的Stack<T>

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

  (1)Push方法源码

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++;
}

  (2)Pop方法源码

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;
}

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

参考资料

(1)程杰,《大话数据结构》

(2)陈广,《数据结构(C#语言描述)》

(3)段恩泽,《数据结构(C#语言版)》

(4)yangecnu,《浅谈算法与数据结构:—栈和队列

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2015-07-04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、栈的概念及操作
    • 1.1 栈的基本特征
      • 1.2 栈的基本操作
      • 二、栈的基本实现
        • 2.1 栈的顺序存储实现
          • 2.2 栈的链式存储实现
          • 三、栈的基本应用
          • 四、.NET中的Stack<T>
          • 参考资料
          相关产品与服务
          对象存储
          对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档