倚楼听风雨
淡看江湖路

浅析数据结构之栈stack,顺便全面复习线性表List

在说栈之前,离不开线性表的这一数据结构的概念,毕竟栈、队列等其实都是一种特殊的线性表而已,它们跟线性表一样都有前驱后继关系,特殊之处只不过在于限制了这个线性表的插入或者删除位置。

一、线性表相关基础知识回顾

1.线性表(List)的定义: 零个或者多个数据元素的有限序列。线性表元素的个数n(n≥0)定义为线性表的长度,当n=0,我们叫做空表。

2.线性表的抽象数据类型及相关基本操作

  • 初始化 --建立空的线性表

  • 判空 --为空返回true

  • 清空 --将线性表清空

  • 获取 --将线性表中第i个位置元素值返回

  • 匹配 --在线性表中查找给定值相等的元素

  • 插入
  • 删除
  • 线性表的长度

3.线性表之顺序存储结构: 用一段地址连续的存储单元一次存储线性表的数据元素

  • 存储空间的起始位置 --数组data,它的存储位置就是存储空间的存储位置
  • 线性表的最大存储容量 --数组长度MaxSize

  • 线性表的当前长度 --length(线性表的长度应该小于等于数组的长度)

解释一下列表中后两条的注释,我们都知道线性表的顺序存储结构我们一般都会使用数组来表示,比如说Java中的Array、ArrayList(本质通过Array实现元素存储,底层借助System实现自动扩容)。但是数组长度与线性表的长度是有区别的: 数组的长度是存放线性表的存储空间的长度,存储分配后这个量一般是不变的。线性表的长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的。举例说,我们定义一个数组来表示线性表,比如给容量为88,但是我们在线性表中只操作1-9这九个元素,线性表的长度会随着我们的插入删除操作而变化,但是数组的长度始终都是88。所以在任意时刻,线性表的长度应该小于等于数组的长度。

4.线性表之顺序存储结构的插入与删除操作

插入算法的思路:
  • 如果插入位置i不合理,抛出异常

  • 如果线性表长度大于等于数组长度,则抛出异常或者动态增加容量

  • 从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置

  • 将要插入元素填入位置i

  • 线性表长加1

删除算法的思路:
  • 如果删除位置不合理,抛出异常

  • 取出删除元素

  • 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置

  • 线性表长减1

接下来我们使用Java代码模拟一下线性表的书序存储结构的插入删除,即最基本的ArrayList类基本思路:

线性表的顺序存储结构的优缺点:

优点
缺点
无须为表示表中元素之间的逻辑关系而增加额外的存储空间
插入和删除操作需要移动大量元素
可以快速的存取表中任意位置的元素
当线性表长度变化较大时,难以确定存储空间的容量
造成存储空间的"碎片"

5.线性表的链式存储结构: 用一组任意的存储单元存储线性表的数据元素,可以连续,也可以不连续

  • 结点: 由存放数据元素的数据域和存放后继结点地址的指针域组成

  • 头指针: 链表中第一个结点的存储位置叫做头指针

  • 头结点: 第一个结点前附设一个结点,称为头结点。头结点的数据域可以不存储任何信息,但是一般会存储线性表的长度等附加信息,头结点的指针域存储指向第一个结点的指针。
  • 单链表: 每个结点中只包含一个指针域

一张图看懂头指针与头结点的区别:

数据结构中线性表之链表的头指针与头结点的区别示例图

再来使用表格总结一下头结点与头指针的差异:

头指针
头结点
头指针是指链表指向第一个节点的指针,若链表有头结点,则是指向头结点的指针
头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义(也可存放链表的长度)
头指针具有标识作用,所以常用头指针冠以链表的名字
有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其它结点的操作就统一了
不论链表是否为空,头指针均不为空。头指针是链表的必要元素
头结点不一定是链表必须要素

6.线性表之单链表的读取:

获取链表第i个数据的思路:

  • 声明一个指针p指向链表第一个结点,初始化j从1开始

  • 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1

  • 若到链表末尾p为空,则说明第i个结点不存在

  • 否则查找成功,返回结点p的数据

7.线性表之单链表的插入与删除:

单链表第i个数据插入结点的算法思路:

  • 声明一个指针p指向链表第一个结点,初始化j从1开始

  • 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1

  • 若到链表末尾p为空,则说明第i个结点不存在

  • 否则查找成功,在系统中生成一个空结点s;

  • 将数据元素赋值给s->data

  • 单链表的插入标准语句s->next=p->next;p->next=s;

  • 返回成功

单链表第i个数据删除结点的算法思路:

  • 声明一个指针p指向链表第一个结点,初始化j从1开始

  • 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1

  • 若到链表末尾p为空,则说明第i个结点不存在

  • 若到链表末尾p为空,则说明第i个结点不存在

  • 单链表的删除标准语句: p->next=q->next;

  • 将q结点中的数据赋值给e,作为返回

  • 释放q结点;

  • 返回成功

8.线性表之单链表的整表创建

  • 声明一指针p和计数器变量i

  • 声明一指针p和计数器变量i

  • 让L的头结点的指针指向null,即建立一个带头结点的单链表

  • 循环:

    生成一新结点赋值给p

    随机生成一数字赋值给p的数据域p->data;

    将p插入到头结点与前一新结点之间

  • 头插法: 新结点在第一的位置
  • 尾插法: 新结点都插在终端点的后面

9.单链表的整表删除

  • 单链表的整表删除

  • 将第一个结点赋值给p

  • 循环

    将下一结点赋值给q
    释放p
    将q赋值给p
10.单链表结构与顺序结构优缺点
图表总结一下线性表中单链表与顺序结构存储的优缺点:
顺序存储结构
单链表结构
存储分配方式
连续的存储单元一次存储线性表的数据元素
链式的存储结构,一组任意的存储单元存放线性表的元素
时间性能
查找 --O(1)
插入与删除 --O(n)
查找 --O(n)
插入与删除 --O(1)
空间性能
预分配存储空间,分大了浪费,分小了溢出
不需要分配存储空间,有就可以分配,个数也不受限制

我们知道Java中的链表表示一般是LinkedList,接下来我们模拟一下LinkedList的实现思路,具体源码可以参考JDK中LinkedList的源码实现。

11.线性表的链式存储结构之循环链表: 将单链表中终端结点的指针端由空指针改为指向头结点,使得整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表。

12.线性表的链式存储结构之双向链表: 在单链表的每个结点中,再设置一个指向其前驱结点的指针域

在Java中,其实LinkedList就是双向链表,LinkedList实现了List和Deque接口,在插入和删除数据时效率更高,老四这里就不贴LinkedList的源码了~~~

以上只是简单的复习重点知识,而不是给大家讲解具体的线性表特性已经各种复杂的数据结构知识点,所以刚入门的人可能看的比较晕,还是适合有一定的基础的作为知识回顾和重点记忆人,见谅。

复习完线性表知识之后,我们就可以来说说"栈"这个数据结构了。

二、数据结构之栈相关知识浅析 基于Java

1.栈的定义: 栈(stack)是限定仅在表尾进行插入和删除操作的线性表。

允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(LastIn First Out)的线性表,简称LIFO结构。

注意: 栈首先是一个线性表,即栈元素具有线性关系-前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作,这里表尾是指栈顶,而不是栈底。栈底是固定的,最先进栈的只能在栈底。栈的插入操作,叫作进栈,也称压栈、入栈。

2.Java版栈的顺序存储结构实现

根据前面回顾线性表的知识我们知道,栈也是一种特殊的线性表,所以栈的实现自然也有顺序存储结构和链式存储结构。我们先来看一下在Java中实现栈的顺序存储结构思路以及一些基本的操作。

3.Java版栈的链式存储结构实现

4.栈的重要应用-递归

老四曾经在《浅析数据结构排序篇之快速排序Quick Sort》中介绍过递归的一些相关知识,包括尾递归等等。 我们都知道,把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称作递归函数。递归最近点示例应该就是斐波那契数列了。

斐波那契数列公式

斐波那契数列(意大利语:Successione di Fibonacci),又译为菲波拿契数列菲波那西数列斐波那契数列黄金分割数列

在数学上,费波那契数列是以递归的方法来定义:

  • {\displaystyle F_{0}=0}
  • {\displaystyle F_{1}=1}
  • {\displaystyle F_{n}=F_{n-1}+F_{n-2}}(n≧2)

用文字来说,就是费波那契数列由0和1开始,之后的费波那契系数就是由之前的两数相加而得出。首几个费波那契系数是:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

特别指出:0不是第一项,而是第零项。

更多内容可以参考一下维基百科:

简单的说一下递归过程为什么适用于栈这种数据结构,递归过程退回的顺序是它前行顺序的逆序。在退回过程中,可能要执行某些动作,包括恢复在前行过程中存储起来的某些数据。这种存储某些数据,并在后面又以存储的逆序恢复这些数据,以提供之后使用的需求,显然很符合栈这样的数据结构,因此,编译器使用栈实现递归就没什么好惊讶的了。简单的说,就是在前行阶段,对于每一层递归,函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段,位于栈顶的局部变量、参数值和返回地址被弹出,用于返回调用层次中执行代码的其余部分,也就是恢复了调用的状态。

Java中斐波那契数列的两种实现方式如下:

5.栈的重要应用-四则运算求值

我们都知道在四则运算中,先乘除后加减,括号优先级最大,这对于计算机处理起来这样的运算逻辑是非常困难的。早起一些伟大的数学家就发明了一种"后缀表示法(所有的符号都是在要运算数字的后面出现)"来,这种表示法巧妙的将括号进行了转换,不复存在,虽然看起来别扭,但是程序喜欢。形如: 9+(2-1)×3+8÷4改写成"9 2 1-3*+8 4/+"。这样的表达式我们就可以轻松的使用栈这种数据结构来求得结果值。

从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。细节就不讲了,想要更深入的研究可以参考一下逆波兰表达的维基百科:

更博不易,如果觉得文章对你有帮助并且有能力的老铁烦请赞助盒烟钱,点我去赞助。或者扫描文章下面的微信/支付宝二维码打赏任意金额,老四这里抱拳了。赞助时请备注姓名或者昵称,因为您的署名会出现在赞赏列表页面,您的赞赏钱财也会被用于小站的服务器运维上面,再次抱拳。

赞(11) 给你买杜蕾斯
本站原创文章受自媒体平台原创保护,未经允许不得转载高老四博客 » 浅析数据结构之栈stack,顺便全面复习线性表List
分享到: 更多 (0)

开始你的表演 2

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    文章不错非常喜欢

    新闻3周前 (11-21)回复
    • 感谢您的喜欢,但是目前不会放过这种形式链接的推广......

      Glorze3周前 (11-21)回复

觉得文章有用就打赏一下老四,鼓励我更好的创作

支付宝扫一扫打赏

微信扫一扫打赏