栈与队列

发表于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

相关推荐

数据通信原理

数据通信原理通信系统的基本组成通信三要素：信源：信息的发送者，是发出各种信息（文字、图片或者数据）的信息源信宿：信息的接受者载体：传送信息的媒体（信道）噪声的存在对通信产生不利影响通信系统的基本组成变换器：将信源发出的信息变为载体上看传输的格式反变换器：将载体上传输的信息变换成信宿可识别格式信道：信息可以单向传输的途径按传输类型分类：有线信道无线信道按传输方式分类：模拟信道数字信道信道带宽：信道可以不失真地传输信号的频率范围信道容量：信道在单位时间内可以传输的最大信号量数据传输速率（bps）：信道在单位时间内可以传输的最大比特数。差错率、误码率：出错/总数、与传输距离成正比由于噪声的影响和信道带宽的限制，信号可能发生失真调制/解调：利用模拟信道支持数据信息传输的技术调制：将数据信息变换成适合于模拟信道上传输的电磁波信号（数字->模拟）解调：将从模拟信道上收取的载波信号还原成数据信息（模拟->数字）调制解调器：具有调制、解调功能的通信设备调制方法调制依据：模拟信号的三...

计算机网络概述

计算机网络概述网络的发展计算机网络 = 计算机 + 通信 + 用户需求计算机发展过程：单机：单个用户独占系统资源（主机）分时系统：分时多用户系统：多个用户利用多台终端共享单台计算机的资源远程访问系统：利用通信线路将远程终端连接到主机，不受地域限制地使用计算机资源网络：将多台计算机连接在一起，相互共享资源计算机网络以共享资源（硬件、软件和数据资源等）为目的而连接起来的、在协议控制下，由一台或多台计算机、若干台终端设备、数据传输设备等组成的系统的集合。这些计算机系统应当具有能独立自治能力的操作系统。计算机联网的主要目的：资源共享：硬件共享：大型计算机的处理能力，昂贵的外设软件共享：应用软件、系统软件等数据共享：用户数据等数据传输：支持用户之间的数据传输（如 smtp、ftp、ip 等），计算机网络可以使得分布于全球的计算机协作起来，形成一个巨大、虚拟的计算机。网络的类型：根据网络覆盖范围 Wide Area Network (WAN) 广域网 Local Area Network (LAN) 局域网...

树与二叉树

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

绪论O记号问题：随着问题规模的增长，计算成本是如何变化的？考虑的是计算成本的增长趋势分析：在问题规模足够大的情况下，计算成本如何变化：需要执行的基本操作次数T(n) 需要占用的存储单元数量S(n)，一般不考虑空间占用对于T(n)转为O(f(n)) 常系数可以忽略，低次项可以忽略 O复杂度计算基于悲观的角度判断代码的复杂度常数复杂度O(1)：不含转向（循环、调用、递归等），部分特例虽然含有循环、调用、递归等，但是需要考虑到实际情况才能确定。对数复杂度O(log n)：高效，复杂度无限接近常数多项式复杂度O(n^c)：界定为多项式的最高次项线性复杂度O(n) 指数复杂度O(c^n)：计算成本高 1234567void func(int n){ // n是正整数 int i = 1; while(i<=n)i*=2;}// 被嵌套的深层语句是i*=2；频率由i<=n决定，显然时间复杂度为O(log n) 冒泡排序观察：有序序列中，任意一对相邻元素顺序 / 无序序列中，存在一对相邻元素逆序 ...

设计模式学习笔记

创建型作用：如何创建对象 1 单例模式单例模式（Singleton）创建分为饿汉式和懒汉式，但是在开源项目中使用最多的主要有两种写法。 1.1 静态常量静态常量方式属于饿汉式，以静态变量的方式声明对象。这种单例模式在 Spring 中使用的比较多，举个例子，在 Spring 中对于 Bean 的名称生成有个类 AnnotationBeanNameGenerator 就是单例的。 1.2 双重检查机制双重检查机制（DCL）方式属于懒汉式。 123456789101112131415161718public class Singleton { private volatile static Singleton INSTANCE; private Singleton() {} public static Singleton getInstance() { if (INSTANCE == null) { synchronized (Singleton.class) {...

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