Skeleton Layout

堆栈和队列

1. 堆栈(堆栈的基本概念，堆栈的用途)((顺序堆栈类的设计方法，链式堆栈类的设计方法))
   1. 堆栈的基本概念
      1. 定义:限定只能在固定一端进行插入和删除操作的线性表
      2. 特点:后进先出(LIFO)
      3. 允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。
      4. 从输入和输出数据元素的位置关系看，堆栈的功能和一种火车调度装置的功能类同。
   2. 堆栈抽象数据类型
      1. 数据集合:
         1. 堆栈的数据集合可以表示为a0,a1,…,an-1，
         2. 每个数据元素的数据类型可以是任意的类类型。
      2. 操作集合:
         1. push(obj):入栈
         2. pop():出栈
         3. getTop():取栈顶数据元素
         4. notEmpty():堆栈是否非空

      3. 堆栈抽象数据类型的Java接口定义

   3. 顺序堆栈
      1. 顺序堆栈:
         1. 顺序存储结构的堆栈。
      2. 顺序栈的存储结构:
         1. 它是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，

         2. 其结构如图p7

      3. 顺序堆栈类设计见教材P45

      4. 优缺点
         1. 优点:内存利用率高
         2. 缺点:需给出最大元素个数
   4. 链式堆栈类
      1. 链式堆栈
         1. 顺序存储结构的堆栈。
      2. 链式栈的存储结构
         1. 和单链表相同，链式堆栈也是由一个个结点组成的，每个结点由两个域组成，一个是存放数据元素的数据元素域element，另一个是存放指向下一个结点的对象引用（即指针）域next。
         2. 堆栈有两端，插入数据元素和删除数据元素的一端为栈顶，另一端为栈底。
         3. 链式堆栈都设计成把靠近堆栈头head的一端定义为栈顶。

         4. 链式堆栈类设计见教材P47

         5. 优点、缺点
2. 堆栈的应用
   1. 括号匹配问题(设计思路:用栈暂存左括号)
   2. 表达式计算问题
3. 队列(队列的基本概念，队列的用途)(顺序循环队列的基本实现原理，顺序循环队列的队空和队满判断方法，顺序循环队列类的设计方法)(链式堆栈类的设计方法)
   1. 队列的基本概念
      1. 定义:只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。队尾插入、队头删除
      2. 一个队列的示意图p20
   2. 队列抽象数据类型
      1. 数据集合:队列的数据集合可以表示为a0,a1,…,an-1，每个数据元素的数据类型可以是任意的类类型。
      2. 操作集合:
         1. append(obj):入队列
         2. delete():出队列
         3. getFront():取队头数据元素
         4. notEmpty():非空否
      3. 顺序队列p23
         1. 顺序队列的存储结构
         2. 顺序队列的“假溢出”问题
      4. 如何解决顺序队列的假溢出问题？可采取四种方法：
         1. 采用顺序循环队列；
         2. 按最大可能的进队操作次数设置顺序队列的最大元素个数；
         3. 修改出队算法，使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置；
         4. 修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向队头移动，然后再完成入队操作。
      5. 顺序循环队列的基本原理
         1. 把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到MaxQueueSize-1后，再前进一个位置就自动到０。
         2. 顺序循环队列的队空和队满判断问题新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有三：
            1. 少用一个存储单元判队满：
               1. front=＝(rear+1)%MaxQueueSize
               2. 判队空： rear==front
            2. 加设标志位，出队时置０,入队时置１,则可识别当前front=rear属于何种情况
               1. 判队满：tag==1 && rear==front
               2. 判队空：tag==0 && rear==front
            3. 使用一个计数器count记录队列中元素个数（即队列长度）；
               1. 判队满：count>0 && rear==front
               2. 判队空：count==0

      6. 顺序循环队列类设计见教材P58

      7. 链式队列
         1. 具有链式存储结构的队列称之为链式队列。
            1. 链式队列的存储结构
               1. 链式队列的队头指针指向队列的当前队头结点;队尾指针指在队列的当前队尾结点,下图是一个不带头结点的链式队列的结构

               2. 链式队列类的设计见教材P60

            2. 队列的应用

            3. 回文函数见教材P61

            4. 基数排序（桶排序）

4. 优先级队列(优先级队列的概念，优先级队列的用途，顺序优先级 队列的入队列和出队列操作设计方法)
   1. 优先级序列
      1. 优先级队列是带有优先级的队列。
      2. 用顺序存储结构实现的优先级队列称作顺序优先级队列。
      3. 用链式存储结构存储的优先级队列称作链式优先级队列。
   2. 顺序优先级队列类
      1. 区别****顺序优先级队列和顺序循环队列相比主要有两点不同：
         1. 对于顺序优先级队列来说，出队列操作不是把队头数据元素出队列，而是把队列中优先级最高的数据元素出队列。
         2. 对于顺序优先级队列来说，数据元素由两部分组成，一部分是原先意义上的数据元素，另一部分是优先级。通常设计优先级为int类型的数值，并规定数值越小优先级越高。

      2. 顺序优先级队列类设计见教材P62

      3. 思考：链式优先级队列的设计

      4. 顺序优先级队列出队操作的实现：首先在遍历队列数据元素的基础上找出优先级最高的数据元素；然后依次把从该数据元素后一个的元素直到队尾的元素前移一个位置（这和顺序表删除操作的方法类似）。
      5. 顺序优先级队列不会出现“假溢出”问题，不用设计成循环结构。

      6. 顺序优先级队列类设计见教材P62

      7. 思考：链式优先级队列的设计

      8. 优先级队列的应用

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 963614756@qq.com。