栈与队列

发表于2024-08-10|更新于2026-06-10|Computer Basics

|浏览量:

栈与队列

栈`Stack`

栈：只允许在一段插入和删除的线性表（LIFO）
栈是操作受限的单向链表，只能在头部和尾部有操作

队列`Queue`

队列：先进先出的线性表（FIFO），只允许一端插入，另一端删除
循环队列：为了避免空间浪费引入。需要注意的是，插入的时候要注意要预判队首和队尾是否相连。

文章作者: xhj

文章链接: https://hzhzxfs.github.io/2024/08/10/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 xhj的博客！

Computer Basics

相关推荐

操作系统概述

操作系统概述操作系统的概念、特征、功能以及提供的服务概念控制程序（防止不当使用、为用户提供服务）一个系统软件控制程序执行过程防止错误或者计算机的不当操作执行用户程序为用户程序提供各种服务，方便用户使用计算机资源管理器（连接软件硬件，管理资源被高效利用，解决冲突确保公平）应用程序和硬件之间的中间层管理各种计算机软硬资源提供访问计算机软硬资源的高效手段解决资源访问冲突，确保资源公平使用特征并发计算机系统中存在多个运行的程序，需要OS进行管理和调度共享程序运行过程中，宏观上并行执行，微观上互斥共享软硬件资源虚拟利用多道程序设计技术（交替运行程序），让计算机的每个用户专门有一个用户为它访问的感观异步程序的执行不是一贯到底而是走走停停，向前推进的速度不可知，只要运行环境相同，操作系统应当保证每次返回的数值相同功能进程管理（处理机管理功能）进程控制、进程同步、进程通信、调度内存管理（存储器管理功能）内存分配、内存保护、地...

内存管理内存管理基础内存管理概念程序装入与链接程序包括代码、数据和堆栈三个部分。逻辑地址和物理地址空间物理地址空间：硬件支持的地址空间逻辑地址空间：CPU运行时，进程看到的进程空间逻辑地址的生成：高级语言源码 –编译–> 指令汇编码 –编译–> 二进制代码 –链接：函数库平移–> 调用函数库（如果需要调用别的内存地址的函数）程序加载重定位（逻辑地址平移）：内存实际分配位置不一定从0开始编译时：假设起始地址已知，如果起始地址改变必须重新编译加载时：如编译起始位置未知，编译器需要生成可重新定位的代码，加载时需要生成绝对地址执行时：执行代码可移动，需要地址转换（映射的支持）内存保护连续分配管理方式给进程分配一块不小于指定大小的连续的物理内存区域（代码数据堆栈）内存碎片：无法利用的空闲内存外部碎片：两个区域之间的未被使用区域内部碎片：分配单元内部的未被使用内存，取决于分配单元大小是否需要取整动态分区分配：（指定大小、可变、地址连续）操作系统维护数据结构：所有进程已分配分区和空闲分区策略：最先匹配，最佳匹配，最差匹配 ...

内部排序概述排序：将一组杂乱无章的数据按照一定规律顺次排列数据表：待排序数据元素的有限集合排序算法的稳定性：数据表中两个相同的值在经过算法排序后的相对位置是否改变内排序：排序期间数据元素全部在内存中外排序：数据太多，只能部分在内存中进行，需要不断进行内外存的数据转移排序的时间开销：衡量算法好坏的标志，主要表现是数据比较次数和数据移动次数总关键字比较次数：KCN 元素移动次数：RMN 内部排序插入排序：每步将一个待排序的元素按照其关键字的大小，插入到前面已经排好序的一组元素的适当位置上面，直到全部元素插入完毕为止直接插入排序：从unsorted的列表中找到最大的和sorted列表中最后一个元素交换折半插入排序：利用折半查找算法，找到合适的位置层层递进插入（类似二叉查找树），实际复杂度取决于数据表的初始排列 2-路插入排序：复制一个新的数据表，遍历原数据表时判断与新数据表的关系选择插入位置表插入排序：使用链表实现直接插入排序希尔排序：(缩小增量排序)按照一个k的维度进行排序，开始时k值较大，子序列中元素较少，速度快；后来基本已完成排序，需要移动的元素减少...

数组与广义表

数组与广义表一维数组数组是相同类型的数据元素的集合，而一维数组的每个数组元素是一个序对，由index和value组成一维数组一般会被看成向量vector，二维数组一般被看成向量组多维数组特殊矩阵的压缩存储特殊矩阵是指非零元素和零元素的分布有一定规律的矩阵特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵,为了节省存储空间,对可以不存储的元素,如零元素或者对称元素,不再存储对称矩阵沿着主对角线只需要一半的空间三对角矩阵沿着主对角线形成一个列表稀疏矩阵如果矩阵中很多数量是0，只需要存储对应的坐标和value的值即可在稀疏矩阵的三元组表中，非零矩阵元素按照行存放，行号相同的时候，按照列号递增存放十字链表对于稀疏矩阵，当非0元素的个数和位置在操作过程中变化较大时（如相加），采用练市存储结构比较方便广义表列表里面的元素自定义，也可以是一个类型，可以类比Python中的list Samples： A()：深度1，长度0 B(6,2)：深度1，长度2 C(‘a’,(5,2))：深度2，长度2 D(B, C)：深度3，长度2 F(4, F)：深度...

串串串（字符串）：由零个或者多个字符组成的有限序列。串值：双引号括起来的字符序列串长：所包含的字符总数量子串（substring）子串序号（index）串相等：长度相等且对应位置的字符也一样串常量：只能读，不能写串变量：可读可写串在计算机中的存储方式定长顺序存储表示堆分配存储块链存储（块的意思是每个结点存放不止一个字符）串的模式匹配算法模式匹配：子串在主串中的定位称为模式匹配或串匹配 Brute-Force模式匹配算法匹配流程代码 BF算法代码执行的复杂度为O(m+n)，最坏为O(m*n)。当遇到s=”001”,p=”00000000001”的串的时候，就会遇到最坏情况 KMP模式匹配算法改进点：每当一趟匹配出现字符不相等时，主串指示器不用回溯，而利用已经得到的部分匹配的结果，将模式匹配器向右尽可能滑动一段距离后在继续比较匹配流程代码 KMP算法代码可以大大缩短匹配的次数时间复杂度一定是O(m+n) 仅当模式与主串之间存在许多部分匹配的情况，才会比BF算法有明显的性能提升

树与二叉树

树与二叉树树定义：树是n个结点的有限集合，在任何一个非空的树中有且只有一个根节点子女：结点的子树非空，结点子树的根即为结点的子女双亲：结点有子女，该结点是子女的双亲兄弟：某一结点的所有子女，互为兄弟度：结点的子女个数分支结点：非终端结点叶：终端结点祖先：沿着双亲的路径返回均为祖先子孙：下属所有结点结点的层次：规定根节点在第一层，子女依次加1 深度：层次的最大值树的高度：根节点的高度->所有子女高度+1 有序树：树的结点的各棵子树是从左到右有顺序的无序树：无序，各棵子树之间的次序可以呼唤森林：m棵互不相交的树组成二叉树二叉树中不存在度大于2的结点满二叉树完全二叉树：k层二叉树除了第k层有从有向左的连续缺失的结点二叉树的顺序表示按照满二叉树的顺序，有数则填，无数则留空极端情况下，资源利用率特别低二叉树的链式表示二叉链表三叉链表二叉树遍历前序遍历（VLR）【-+a*b-cd/ef】中序遍历（LVR）【a+b*c-d-e/f】后序遍历（LRV）【abcd-*+ef/-】 ...