博客

数据结构与算法—动态数组（2）顺序栈ArrayStack、双端栈ArrayStackDoubleEnd

  • Post author:
  • Post category:其他


  1. 栈的顺序存储结构

    a.栈的定义：栈是限定仅在表尾进行插入和删除操作的线性表

    在这里插入图片描述
    我们把允许插入和删除的一端称为栈顶，另一端称为栈底


    栈又称为后进先出的线性表


    定义中说的时在线性表的表尾进行插入和删除，这里

    表尾是栈顶


    栈的插入操作，叫做进栈，也称压栈，入栈

    栈的删除操作，叫做出栈，也称弹栈

    b.栈的接口定义

    在这里插入图片描述
    成员变量，成员函数

    我们可以将顺序表看成时栈的一个成员变量

    在这里插入图片描述
    c.接口的实现

    接口的实现我们都可以基于顺序表来实现，直接调用顺序表的方法

    在这里插入图片描述
    在这里插入图片描述
  2. 双端栈的顺序存储结构


    是指将一个线性表的两端当作栈底分别经行入栈和出栈操作


    在这里插入图片描述
    在这里插入图片描述
    双端栈的内部变量

    在这里插入图片描述

    因为双端栈需要在两端都可以进行操作，所以简单的顺序表就已经不能实现它了，我们则需要重写他的底层实现

    成员变量

    在这里插入图片描述
    成员函数

    在这里插入图片描述

    获取栈中所有有效元素的个数


    1.当前栈分为左右两个部分，我们想要获取栈中全部的有效个数，则需要分别获取左右两边的有效元素个数

    2.左边有效元素个数就是栈底位置+1（lefttop+1)

    3.右边有效元素个数为数组的长度-右端顶的位置（data.length-righttop)

    3.将左右两个有效元素个数相加，则为栈中所有有效元素的个数

    在这里插入图片描述

    判断栈是否为空


    我们继续将他从左右两边分开判断

    1.判断左栈是否为空 lefttop=-1；

    2.判断右栈是否为空righttop=data.length;

    3.如果左右两边同时为空，则栈为空，否则就不为空

    在这里插入图片描述

    元素e进栈


    依旧分为左右两边进栈

    1.左边进栈，首先判断左栈是否为满（lefttop+1=righttop),若为满则需扩容，然后将元素放入，若不满，则直接lefttop+1处放元素e

    2.右边进栈，判断右栈是否满了（righttop-1=lefttop),若为满则需扩容，然后将元素放入，若不满，则直接righttop-1处放元素e

    3.判断左栈和右栈元素的个数，那边少就往那边进

    在这里插入图片描述

    扩容


    在这里插入图片描述
    在这里插入图片描述
    1.先创建一个新数组，然后开始赋值

    2.左边的lefttop位置不变，所以继续遍历它

    3.右边我们则需要遍历，右边有效元素次，然后将他赋给新数组

    在这里插入图片描述

    弹栈


    依旧是分为左右两边

    1.判断左边是否为空，若为空则提示，若不为空则返回data[leftTop–]

    2.判断右边是否为空，若为空则提示，若不为空则返回data[rightTop++]

    3.总的弹栈，谁多谁出，但是要考虑缩容，所以先将值赋给一个变量，然后缩容（当前长度小于等于长度的四分之一并且缩后的长度大于10），最后返回变量。

    在这里插入图片描述


    缩容


    在这里插入图片描述
    1.放入新数组后左边的lefttop依旧不变，所以将原来左边的元素放入新数组

    2.右边的元素则需要从原来的righttop开始，到data.length,将原来位置的元素i，放入到新数组中的i-newData.length的位置

    3.同时righttop=righttop-newdata.length

    在这里插入图片描述

    查看栈顶元素和清空栈


    在这里插入图片描述

    重写


    和线性表一样，调用StringBuilder,StingFormart,append（）方法

    继续分为左右两个部分，若左端为空，则输出左端为空，否则则开始遍历，右端同样的操作

    在这里插入图片描述


版权声明：本文为qq_45161607原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。