【概述】

链式队列是采取链式存储的队列，其不存在队列满而导致上溢的情况，通常设计为一个带头结点的单链表，其有两个指针，队头指针向队头结点，尾指针指向队尾结点

链式队列的实现类如下：

【概述】

由于顺序队列中的假溢出会造成极大的空间浪费，为避免这种浪费，对可采用以下两种方法来克服：

1. 将队列中所有元素均向低地址区移动
2. 将存储队列的数组头尾相接，当存放到 $n$ 地址后，下一个地址就翻转为 $1$

【概述】

关系模型是最重要的一种逻辑模型，在数据库领域上，当前的研究工作都是以关系方法为基础，目前常见的数据库系统基本都是采用关系模型作为数据的组织方式，即关系型数据库

关系模型建立在严格的数学概念的基础上，可以描述一对一、一对多、多对多的联系，同时概念单一，实体、各类联系、对数据的检索结果都用关系来表示，具有更高的数据独立性、更好的安全保密性，此外存取路径对用户透明，用户只要指出干什么，不必详细说明怎么干，简化了数据库建立的过程，也精简了程序员的工作

【概述】

数据库领域主流的逻辑模型随着时代的发展不断在变化，格式化模型（层次模型、网状模型）在 20 世纪 70 年代到 80 年代初期十分流行，占据主导地位，但现在已逐渐被关系模型的数据库系统取代

同时，自 80 年代面向对象技术在计算机各领域广泛应用后，数据库领域针对于面向对象方法也进行了研究，这就有了面向对象模型，之后为进一步支持面向对象模型，许多数据库厂商对关系模型进行了扩展，这就产生了对象关系数据模型

【概述】

顺序队列是采取顺序方式存储的队列，利用一组地址连续的存储单元自队首到队尾存放数据元素，并通过队首指针来指示当前队首元素位置，通过队尾指针来指示当前队尾元素的下一位置

对于存储空间的分配，若采用静态分配方式，一经分配不可修改，若采用动态分配方式，分配后在 $O(n)$ 的时间复杂度内可以更改

括号匹配问题是指，在给出一个包含 (、{、[、)、}、] 的序列，问这个序列的括号是否匹配

解决括号匹配问题的基本思想是：

1. 扫描整个序列，遇到左括号时，令左括号入栈，遇到右括号时，令左括号出栈，进行匹配操作
2. 若出栈的左括号与当前右括号不匹配，则整个序列不匹配
3. 若栈为空，且扫描到右括号，则整个序列不匹配
4. 若扫描完序列后，栈中仍有左括号（判断栈是否为空即可），则整个序列不匹配

【表达式类型】

一个表达式一般由操作数、运算符、界限符三个部分组成，根据运算符的位置，表达式可分为以下三类：

• 中缀表达式（算术表达式）：运算符在两运算数中间，界限符反映了计算的先后顺序
• 前缀表达式（波兰式）：无界限符，运算符在前，操作数在后
• 后缀表达式（逆波兰式）：无界限符，运算符在后，操作数在前

【信息世界中的基本概念 】

实体（Entity）是客观存在并且可以相互区别的事物，可以是具体的人、事、物，也可以是抽象的概念或联系

实体集（Entity set）是同一类型实体的集合

【概述】

链栈是采取链式存储的栈，其不存在栈满上溢的情况，通常采用不带头结点的单链表来实现，且一般规定所有的操作都在单链表表头进行，以保证出栈、入栈、取栈顶操作的时间复杂度为 $O(1)$

链栈的实现类如下：

【两类数据模型】

数据模型是对现实世界数据特征的抽象，用于描述、组织、处理数据，其分为概念模型、逻辑模型和物理模型两类：

• 概念模型：也称信息模型，是按用户的观点来对数据和信息建模，用于数据库设计
• 逻辑模型和物理模型：
  • 逻辑模型：主要包括网状模型、层次模型、关系模型、面向对象模型等，按计算机系统的观点对数据建模，用于 DBMS 实现
  • 物理模型：对数据最底层的抽象，描述数据在系统内部的表示方式和存取方法，或在磁盘或磁带上的存储方式和存取方法