Java数据结构基础丨栈

前言

数据结构从大的方向上分,可以分为逻辑结构和物理结构。逻辑结构是抽象的概念,它依赖于物理结构而存在。

  1. 物理结构可划分为:顺序存储结构与链式存储结构。

    • 顺序存储结构:把数据元素存放在地址连续存储单元里,其数据间的逻辑关系和物理关系是一致的。例如数组
    • 链式存储结构:其中逻辑关系和物理关系没有多大的关系,因为其中的数据元素会产生变化。链式存储结构是把数据元素存放在任意的存储单元里,存储单元可以是连续的也可以是不连续的。当然也比顺序存储结构更加灵活。例如链表
  2. 逻辑结构可划分为:线性结构与非线性结构。

    • 线性结构:顾名思义,一条线性的结构,元素间的关系就是一对一的。例如线性表队列
    • 非线性结构:包括树形结构、图形结构等。例如

栈的基本知识

栈,stack,又称堆栈,是一种线性结构。与数组相比,访问它的元素是受限制的:栈只能在同一端(栈顶)进行操作,且只允许访问一个数据项,即最后插入的数据项。栈中的元素只能先入后出(First In Last Out,简称FILO),最先进入的元素存放的位置叫栈底,最后进入的元素存放的位置叫栈顶

生活中也不缺可以体现出栈的特点的设计/例子,例如:老师批改一叠作业,正常情况下都是先拿起最上面的一本,处理完这本之后,再去批改下一本,从上到下,直到被压在最后的一本,但是最后一本是最开始放的。例如:兵乓球圆筒的一端封闭,另一端开口。往圆筒放入兵乓球,先放入的在圆筒底部,后放入的靠近圆筒入口。在圆筒直径条件限制下,只能按放入顺序相反的顺序取球。

栈的基本操作

  1. 入栈(push),就是把一个新元素放入栈中,只允许从栈顶一侧放入,下一个新元素放入的位置将成为新的栈顶。
  2. 出栈(pop),就是把一个元素从栈中弹出,只有栈顶的元素才允许弹出,出栈元素的前一个元素将成为新的栈顶。
  3. peek(),查看栈顶部的对象,但不对栈做任何改动。
  4. size(),返回栈内元素的大小。
  5. isEmpty(),测试栈是否为空,返回布尔值。
  6. isFull(),测试栈是否为满,返回布尔值。

栈的实现

栈既可以用数组来实现,也可以用链表来实现。注意,如果用数组来实现,需要先规定栈的大小;如果用链表来实现,则不需要先规定栈的容量。

栈的应用及效率

栈是一个重要的数据结构,其特性简而言之就是“先进后出”,可以用它辅助遍历二叉树的节点,也可以用它辅助查找图的顶点。
在计算机中,大部分微处理器运用基于栈的体系结构。在windows等大部分操作系统中,每个运行中的二进制程序都配有一个调用栈(Call Stack)和执行栈(Execution Stack)。当调用一个方法时,把它的返回地址和参数压入栈,方法结束返回时,那些数据就出栈,栈操作就嵌入在微处理器中。

  1. 用栈实现单词逆序;
  2. 中缀表达式求值;
  3. 实现十进制数和其他n进制数的转换;
  4. 用于解析某种类型的文本串,实现分隔符匹配;
  5. ......

栈操作所耗时间不依赖于栈中数据项的个数,因为入栈、出栈都是只影响到最后一个元素,不涉及比较和移动操作,所以无论是数组实现还是链表实现的,数据项入栈、出栈的时间复杂度都是常数级O(1)

打赏
评论区
头像
文章目录