青岛大学数据结构与算法——第3章

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 概述

  • 栈和队列的定义特点
  • 案例引入
  • 栈的表示和操作
  • 栈和递归
  • 队列的表示和操作的实现

二 栈和队列的定义特点

2.1 共同点

  • 插入和删除在表的端点进行
  • 线性表

2.2 栈stack

  • 后进先出(LIFO结构(Last In First Out))
  • 表尾：插入、删除
  • 栈顶/栈尾：表尾-栈顶(Top)、表头-栈底(Base)
  • 操作：入栈(Push)、出栈(Pop)
  • 示例：3个元素abc，出栈顺序由几种

2.3 队列

  • 先进先出(First In First Out-FIFO)-排队
  • 操作：表尾插入、表头删除
  • 实现方式：入队、出队

三 案例引入

  • 栈：进制转换-十进制159转换8进制、括号匹配的检验-([]())
  • 队列：表达式的求值-#3*(7-2)#、舞伴问题-舞会，男士/女士各一对

四 栈的表示和操作

4.1 栈的抽象数据类型定义ADT Stack

4.2 表示和实现

  • 初始化InitStack
  • 销毁栈DestoryStack
  • 判空StackEmpty
  • 栈的长度StackLength
  • 栈顶元素GetTop
  • 栈置空ClearStack
  • 入栈Push
  • 出栈Pop

五 栈和递归

  • 什么是递归
  • 求解问题：迷宫问题、汉诺塔问题
  • 递归方法的情况：数学函数、递归特性的数据结构、递归求解
  • 分治法求解：分治法一般形式
  • 函数调用过程：调用前，系统完成(3)、调用后，系统完成(3)
  • 示例：多函数嵌套、n!求解

六 队列的表示和操作的实现

  • 相关术语：队列、队尾、队头、FIFO
  • 队列的抽象数据类型定义ADT Queue
  • 基本操作：构造空队列InitQueue、队列销毁DestoryQueue、队列清空ClearQueue、队列的元素个数QueueLength、队头元素GetHead、队尾插入EnQueue、删除队头DeQueue
  • 解决上溢的方法：引入循环队列
  • 循环队列判满方法：少用一个元素空间

七 图示