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

一 概述

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

二 栈和队列的定义特点

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
• 解决上溢的方法：引入循环队列
• 循环队列判满方法：少用一个元素空间

七 图示