美文网首页
数据结构与算法(6):栈

数据结构与算法(6):栈

作者: 初心myp | 来源:发表于2019-06-13 17:35 被阅读0次

    首先,抛出一个问题,如何使用栈来完成浏览器的前进后退功能???

    如何理解"栈"???
    关于栈,有一个非常贴切的例子,那就是一摞叠在一起的盘子。我们平时放盘子的时候,是从下往上一个一个的放,取的时候从上往下一个一个的取,不能从中间任何位置取或是放。后进者先出,先进者后出,这就是典型的"栈"的结构。(如下图)

    栈结构图

    从栈的操作特性上来看,栈是一种操作受限的线性表,只允许在一端插入或删除数据。

    刚接触的时候,相对于数组和链表来比,感觉栈给我们带来的只有限制,没有什么优势。

    事实上,从功能上来说,数组和链表是可以代替栈的,但是我们要知道,特定的数据结构是对特定的场景的抽象,而数组和链表暴露的接口太多,操作上太灵活,所以很多时候不好控制,也就容易出现问题。

    当某个数据集合只涉及到在一端插入和删除数据,并且满足后进先出,先进后出的特性,我们就应该首选"栈"这种数据结构

    如何实现栈呢???
    在"栈"的定义里,只包含两个操作,入栈和出栈,也就是从栈顶插入一个数据或从栈顶删除一个数据。接下来我们用代码实现以下栈。【用数组实现的栈叫顺序栈,用链表实现的栈叫链式栈
    基于Java实现的顺序栈,代码如下:

    // 基于数组实现的顺序栈
    public class ArrayStack {
      private String[] items;  // 数组
      private int 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 == 0) return null;
        // 返回下标为 count-1 的数组元素,并且栈中元素个数 count 减一
        String tmp = items[count-1];
        --count;
        return tmp;
      }
    }
    

    了解了栈的基本操作,接下来我们分析一下,栈操作的时间复杂度和空间复杂的吧。

    无论是顺序栈还是链式栈,我们存储都只需要一个大小为n的数据就够了。在入栈和出栈的过程中,只需要两个临时变量的存储空间,所以空间复杂度是O(1)。

    注意:这里说到存储数据需要一个大小为n的数组,并不是说空间复杂度就是O(n)。因为这个n是空间必须的,无法省掉的。所以说,我们说空间复杂度的时候,是指除了原本数组存储空间外,算法运行还需的额外的存储空间。

    空间复杂度不难,时间复杂度也不难。无论是顺序栈还是链式栈,栈的入栈和出栈操作都是只涉及栈顶的个别数据的操作,所以时间复杂的是O(1)。

    支持动态扩容的顺序栈
    上面的那个是基于数组实现的栈,也就是一个固定大小的栈,也就是说在栈初始化的时候就要指定栈的大小。当栈满后,就无法存储数据了。尽管是链式栈的大小不受限制,但是存储next指针,内存消耗也是较多的。接下来我们学习一下基于数组实现一个支持动态扩容的栈。

    先回顾一下,数组是如何动态扩容的。当数组空间不够使,就要申请一块更大的内存空间,然后将原来数组里的数组拷贝过去,这样来完成扩容。

    所以,我们要实现一个动态扩容的栈,只需要底层依赖一个可以动态扩容的数组即可。当栈满的时候,在进行申请一个更大的数组既可以了。可以参考下图进行理解:

    image.png

    其实,支持动态扩容的顺序栈,我们平时是用不到的。但是我们可以通过这个来练习一下复杂度分析。
    现在我们可以一起分析一下,支持动态扩容的顺序栈的入栈出栈操作的复杂度分析。
    对于出栈操作来讲,不会涉及到内存的申请和数据搬移,所以什么情况下的时间复杂度都是O(1);
    对于入栈来讲,如果栈中有空余空间时,那么时间复杂度就是O(1),如果栈中没有空余空间时,需要申请内存空间,那么就涉及到内存的申请和数据搬移,这样,时间复杂度就是O(n)。
    也就是说,入栈的最好情况时间复杂度是O(1),最坏情况时间复杂度是O(n)。那平均时间复杂度是多少呢?这就需要用到我们之间文章里面提到过的摊还分析法了。

    为了方便分析,我们先做一些假设和定义

    • 假设栈空间不足的时候,我们需要重新申请原来大小两倍的数组大小
    • 假设我们只考虑入栈不考虑出栈
    • 定义不涉及到内存搬移的入栈操作为simple-push操作,时间复杂度为O(1)

    如果,当前栈的大小为k,并且已满,当有新的数据需要入栈的时候,就需要申请两倍大小的内存,并且做k个数据的搬移操作,然后在入栈。但是接下来的k-1次入栈操作,就不需要在此申请内存和数据搬移了,所以这k-1次入参操作都只需要一个simple-push操作就可以完成。
    可以根据下图进行理解。

    image.png

    可以看出这k次入栈操作,涉及到了k个数据的搬移操作和k次simple-single操作。将k个数据搬移的操作平均分到k次simple-push操作上,那没个数据入栈只需要一次数据搬移和一次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()函数时,函数调用栈的情况。

    image.png

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

    我们一起了解一下,编译器如何用栈来实现表达式求值的。

    我们简单举例学习,就说一下最简单的包含加减乘除的四则运算,比如3+5*8-6。对于这个四则运算,我们是很快就会算出来了,但是对于计算机来说,理解这个表达式就是很难得一件事情了。

    实际上,计算机就是通过两个栈来实现的。一个操作数栈,一个运算符栈。操作数栈就是用来存储操作数的,运算符栈就是用来存储运算符的。

    具体流程:
    首先,我们从左到右遍历表达式,遇到数字就压入操作数栈,遇到运算符就与运算符栈顶元素进行比较。如果比运算符栈顶元素优先级高,就将当前运算符压入栈中;如果比运算符栈顶元素优先级低或者相同,从运算符栈中取出栈顶运算符,从操作数栈的栈顶取两个操作数,然后进行计算,然后再把计算后的结果压入操作数栈中,继续比较。
    下面是例子中表达式的计算过程图,可以参考,便于理解


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

    除了用栈来实现表达式求值,我们还可以借助栈来检查表达式中的括号是否匹配。

    我们同样简化-下背景。我们假设表达式中只包含三种括号,圆括号0、方括号D和花括号},并且它们可以任意嵌套。比如,{[]]或[{0(D)]等都为台法格式,而{D0]或[(0]为不合法的格式。那我现在给你一个包含三种括号的表达式字符串,如何检查它是否台法呢?

    这里也可以用栈来解决。我们用栈来保存未匹配的左括号,从左到右依次扫描字符串。当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号。如果能够匹配,比如“(”跟“”匹配,"[”跟“”匹配,”{”跟“”匹配,则继续扫描剩下的字符串。如果扫描的过程中,遇到不能对的右括号,或者栈中没有数据,则说明为非法格式。

    当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式:否则,说明有未匹配的左括号,为非法格式。

    解答文章开头的问题
    实现浏览器的前进后退功能,我们需要两个栈,例如X、Y两个栈。我们首次浏览的页面依次压到X栈中,在点击后退的时候,在依次从X中出栈,然后依次压入Y栈中。如果前进呢,就从Y栈中出栈,然后压到X栈中。如果X栈中没有数据时,就说明没有页面可以后退了,同样,如果Y栈中没有数据了,就说明没有页面可以前进了。

    如果我们依次点开a,b,c三个页面,那么依次压入X栈中,如果后退,那么就将后退到c页面,这时c将从X栈出栈,压入Y栈中,在进行后退,就是将b从X栈出栈,在压入Y栈中。
    如果在前进的话,就是b页面从Y栈出栈,压入X栈中。这时候,你通过b页面直接跳到了d页面,页面c就无法通过前进、后退进行重复查看了,所以要清空Y栈。

    思考:
    JVM内存管理中,有个"堆栈"的概念。栈内存用来存储局部变量和方法调用,堆内存用来存储Java中的对象。那JVM中的栈和我们上文中的栈是一个么???

    解析:
    内存中的堆栈和数据结构中的堆栈不是一个概念,可以说内存中的堆栈是真是存在的物理区,数据结构中的堆栈是抽象的数据存储结构。
    内存空间在逻辑上分为三部分:代码区,静态数据区和动态数据区,动态数据区又分为栈区和堆区。
    1.代码区:存储方法体的二进制代码。高级调度(作业调度),中级调度(内存调度),低级调度(进程调度)控制代码区代码的切换
    2.静态数据区:存储全局变量、静态变量、常量,常量包括final修饰的常量和String常量。系统自动分配和回收。
    3.堆区:存储运行方法的形参、局部变量、返回值。有系统自动分配和回收。
    4.栈区:new一个对象的引用或者地址存储在栈区,指向该对象存储在堆区的真是数据。

    相关文章

      网友评论

          本文标题:数据结构与算法(6):栈

          本文链接:https://www.haomeiwen.com/subject/yvqsfctx.html