【表达式类型】

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

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

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

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

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

【概述】

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

链栈的实现类如下：

【两类数据模型】

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

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

【概述】

早期计算机中，为更有效的利用存储空间，在顺序栈的基础上引入了双端栈，其又被称共享栈

双端栈令两个顺序栈共享一个数组空间，将栈底分别设为数组的两端，栈顶从两端向中间延伸，以达到利用同一个数组空间的目的

【查找的基本概念】

查找（search），又称搜索，是在数据集合中，寻找满足某种条件的数据的过程

用于查找的数据集合被称为查找表，其由同一类型的数据元素或记录组成，数据元素中唯一标识该元素的某个数据项的值，被称为关键字，通过关键字的查找，结果应当是唯一的

【概述】

对于数据库系统的体系结构，其分为内部体系结构、外部体系结构两个角度

从数据库管理系统角度来看，通常采用外模式、模式、内模式三级模式结构，这是数据库系统的内体系结构，又被称为数据库系统的模式结构

【概述】

对于数据库系统的体系结构，其分为内部体系结构、外部体系结构两个角度

从数据库管理系统角度来看，通常采用外模式、模式、内模式三级模式结构，这是数据库系统的内体系结构，又被称为数据库系统的模式结构

【概述】

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

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

【队列的定义】

队列（Queue），也是一种操作受限的线性表，只允许在表的一端插入，在表的另一端删除，其中，只允许删除的那一端称为队首，只允许插入的那一端称为队尾，当线性表中不含元素时，称为空队列

队列具有先进先出（First In First Out，FIFO）的操作性质，如下图所示，假设某个队列 $Q=(a_1,a_2,a_3,a_4,a_5)$ ，其中 $a_1$ 为队首元素，$a_5$ 为队尾元素，进队顺序为：$a_1,a_2,a_3,a_4,a_5$，出队顺序为：$a_1,a_2,a_3,a_4,a_5$