数据结构和算法绪论 学习笔记（四）

• 什么是数据结构？
• 栈和队列

先反问下，什么是数据结构？

数据结构是一种在程序中系统化管理数据集合的形式。不过，数据结构很少单纯地表示数据集合，它通常由以下3个概念组合而成。

• 数据集合。 通过对象数据的本体（例如数组和结构体等基本数据结构）保存数据集合。
• 规则。保证数据集合按照一定规矩进行正确操作、管理和保存的规则。比如按照何种顺序取出数据等条款。
• 操作。“插入元素” 和 “取出元素” 等对数据集合的操作。“查询数据的元素数” 和 “检查数据的集合是否为空” 等查询也包含在内。

数据结构的概念

栈 和 队列

当然此处的栈不是内存中 栈的概念...

栈

栈是一种能有效帮助我们临时保存数据的数据结构，按照最后进入栈的数据最先出栈（后入先出，Last In First Out,LIFO）规则管理数据。

• 操作

  • push(x)：在栈中顶部添加元素 x
  • pop()：从栈顶部取出元素
  • isEmpty()：检查栈是否为空
  • isFull()： 检查栈是否已满
  • 另外，还有“引用栈顶元素” 和 “检查栈中是否含有指定数据” 的操作。

• 规则
  数据中最后加入的元素最先被取出，即 pop 取出的元素是最后一次被 push 的元素（距离上一次 push 最近的元素）。

仅限定在表尾进行插入或删除操作的线性表

队列

队列是一种等待处理的行列，按先后顺序处理数据时会用到这种数据结构。数据中最先放入的元素最先被取出，即按照先入先出（Fast In First Out ,FIFO） 的规则管理数据

• 操作

  • enqueue(x)：在队列末尾添加元素 x
  • dequeue()：从队列开头取出元素
  • isEmpty()：检查队列是否为空
  • isFull()： 检查队列是否已满
  • 另外，还有“引用队头元素” 和 “检查队列中是否含有指定数据” 的操作。

• 规则
  数据中最先进入队列的元素（即上一次 enqueue 时间最久的元素） 最先被取出，即 dequeue 操作按照元素被添加的先后顺序取出元素。

一种先进先出的线性表

笔记来源：

【数据结构】——严蔚敏 版本