数据结构与算法之美——栈——学习笔记分析

你猜 阅读:202 2021-06-15 11:21:15 评论:0

一、物理结构和逻辑结构

       常用的数据结构有很多,但大多数都以数组或链表作为存储方式。数组和链表可以被看做数据存储的“物理结构”?例如数组和链表,都是内存中实实在在的存储结构。接下来要讲解的两个常用数据结构:栈和队列以及二叉树。都属于逻辑结构。它们的物理实现既可以利用数组,也可以利用链表来完成。

一、栈

       栈就像一摞叠在一起的盘子,我们平时放盘子的时候,都是从下往上一个个放;取的时候,我们是从上往下一个一个依次取。

先进后出,这就是典型的栈结构。栈是一种“操作受限”的线性表,只允许在一段插入和删除数据。

       事实上,从功能上来说,数组或链表确实可以替代栈,特定的数据结构是对特定场景的抽象。数组或链表暴露了太多的操作接口,操作上的确灵活自由,但使用时就比较不可控,自然也就更容易出错。

       当某个数据集合只涉及在一端插入和删除数据,并且满足先进后出的特性,我们就应该首选“栈”这种数据结构。栈主要包含两个操作,入栈和出栈,也就是在栈顶插入一个数据和从栈顶删除一个数据

       栈既可以用数组来实现,也可以用链表来实现。用数组实现的栈,我们叫做顺序栈,用链表实现的栈,我们叫作链式栈。

       基于数组实现的顺序栈代码如下:        

//基于数组实现的顺序栈 
public class ArrayStack { 
    private String[] items;//数组 
    private Integer count; //当前栈中元素个数 
    private int n;//栈的大小 
 
    //初始化输入,申请一个大小为n的数组空间 
    public ArrayStack(int n) { 
        this.items = new String[n]; 
        this.n = n; 
        this.count = 0; 
    } 
 
    //入栈操作 
    public boolean push(String item){ 
        //数组空间不够了,直接返回false,入栈失败 
        if (count==n) return false; 
        //将item放到下标为count的位置,并且count加一 
        items[count] = item; 
        count++; 
        return true; 
    } 
    //出栈操作 
    public String pop(){ 
        //栈为空,直接返回null 
        if (count==null) return null; 
        //返回下标为count-1的数组元素,并且占中元素个数count-1 
        String tmp=items[count-1]; 
        count--; 
        return tmp; 
    } 
} 

二、支持动态扩容的顺序栈

       刚才那个基于数组实现的栈,是一个固定大小的栈,也就是说,在初始化栈时需要事先指定栈的大小。当栈满了之后,就无法再往栈里面添加数据了。尽管链式栈的大小不受限,但要存储next指针,内存消耗相对较多。那我们如何基于数组实现一个可以支持动态扩容的栈呢?

       你还记得,我们在数组那一节,是如何来实现一个支持动态扩容的数组的吗?当数组空间不够时,我们就重新申请一块更大的内存,将原来数组中数据统统拷贝过去。这样就实现了一个支持动态扩容的数组。

       所以,如果要实现一个支持动态扩容的栈,我们只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了之后,我们就申请一个更大的数组,将原来的数据搬移到新数组中。如下图所示。

                                         

       实际上,支持动态扩容的顺序栈,我们平时开发中并不常用到。下面分析一下支持动态扩容的顺序栈的入栈、出栈操作的时间复杂度。 

       对于出栈操作来说,我们不会涉及内存的重新申请和数据的搬移,所以出栈的时间复杂度仍然是O(1)。但是对于入栈操作来说,情况就不一样了。当栈中有空闲空间时,入栈操作的时间复杂度为O(1)。当当空间不够时,就需要重新申请内存和数据搬移,所以时间复杂度就变成了O(n)。

       也就是说,对于入栈操作来说最好情况时间复杂度是O(1),最坏情况时间复杂度是O(n)。那平均情况下的时间复杂度又是多少呢?还记得我们在复杂度分析那一节中讲的摊还分析法吗?这个入栈操作的平均情况下的时间复杂度可以用摊还分析法来分析。正好借此来实战一下摊还分析法。

       为了分析的方便,我们需要事先做一些假设和定义:

       1、栈空间不够时,我们重新申请一个是原来大小两倍的数组;

       2、为了简化分析,假设只有入栈操作没有出栈操作;

       3、定义不涉及内存搬移的入栈操作为simple-push操作,时间复杂度为O(1)。

       如果当前栈大小为K,并且已满,当再由新的数据要入栈时,就需要重新申请2倍大小的内存,并且做k个数据的搬移操作,然后再入栈。但是,接下来的K-1次入栈操作,我们都不需要再重新申请内存和搬移数据,所以这K-1次入栈操作都只需要一个simple-push操作就可以完成。为了更好直观地理解这个过程。如下图所示。

                             

可以看出,这K次入栈操作,总共涉及了K个数据的搬移,以及K次simple-push操作。将K个数据搬移均摊到K次入栈操作,那每个入栈操作只需要一个数据搬移和一个simple-push操作。以此类推,入栈操作的均摊时间复杂度就为O(1)。

       通过这个例子的实战分析,也印证了前面讲到的,均摊时间复杂度一般都等于最好情况时间复杂度。因为在大部分情况下,入栈操作的时间复杂度O都是O(1),只有个别时刻才会退化为O(n),所以把耗时多的入栈操作的时间均摊到其他入栈操作上,平均情况下的耗时就接近O(1)。

三、栈的应用

       1、栈在函数调用中的应用

        栈作为一个比较基础的数据结构,应用场景还是蛮多的。其中,比较经典的一个应用场景就是函数调用栈

        我们知道,操作系统给每个线程分配一个独立的内存空间,这块内存被组织成“栈”这个结构,用来存储函数调用时的临时变量。每进入一个函数,就会将临时变量作为一个栈帧入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧出栈。为了让你更好地理解,我们一块来看下这段代码的执行过程。    

int main() { 
   int a = 1;  
   int ret = 0; 
   int res = 0; 
   ret = add(3, 5); 
   res = a + ret; 
   printf("%d", res); 
   reuturn 0; 
} 
 
int add(int x, int y) { 
   int sum = 0; 
   sum = x + y; 
   return sum; 
}

       从代码中我们可以看出,main()函数调用了add()函数,获取计算结果,并且与临时变量a相加,最后打印res的值。为了让你清晰地看到这个过程对应的函数栈里出栈、入栈的操作,如下图所示,图中显示的是,在执行到add()函数时,函数调用栈的情况。

                                                   

       2、栈在表达式求值中的应用.

       我们再来看栈的另一个常见的应用场景,编译器如何利用栈来实现表达式求值

       为了方便解释,将算法表达式简化为只包含加减乘除四则运算,比如:34+13*9+44-12/3。对于这个四则运算,人脑可以很快求出答案,但对于计算机来说,理解这个表达式本身就是个挺难的事儿。如果换作你,让你来小hi爱你这样一个表达式求值的功能,你会怎么做呢?

       实际上,编译器就是通过两个栈来实现的。其中一个保存操作数的栈,另一个是保存运算符的栈。我们从左到右遍历表达式,当遇到数字,我们就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较。

       如果比运算符栈顶元素的优先级高,就将当前运算符入栈;如果比当前运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取2个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较。

       下图为将3+5*8-6这个表达式的计算过程画成了一张图,你可以结合图理解刚刚说的计算过程。

                            

        

       3、栈在括号匹配中的应用

       4、实现浏览器的前进、后退功能

        可以使用两个栈,X和Y,我们首次浏览的页面依次压入栈X,当点击后退按钮时,再依次从栈X中出栈,并将出栈的数据依次放入栈Y。当点击前进按钮时,依次从栈Y中取出数据,放入栈X中。当栈X中没有数据时,那就说明没有页面可以继续后退浏览了。当栈Y中没有数据,那就说明页面没有页面可以点击前进按钮浏览了。

        


标签:程序员
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号