四川大学数据结构第3章 栈和队列.pptVIP

数据结构与算法(C++版) 第3章 栈和队列 3.1 栈(stack) 一、栈的基本概念 1. 栈 的概念与特点 只允许在一端插入和删除的线性表 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 特点 后进先出 (LIFO) 二、栈的数组表示—— 顺序栈 三、链式栈 链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 链式栈入栈和出栈操作都非常简单，一般都不使用头结点直接实现 3.2 队列 一、队列(Queue)的基本概念 1. 队列的初步认识 定义 队列是只允许在一端删除，在另一端插入的线性表 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特性 先进先出(FIFO, First In First Out) 二、链队列 1. 链队列的基本概念 链式队列在入队时无队满问题，但有队空问题。 队空条件为 front == rear 1. 链队列的类模板 三、循环队列——队列的顺序存储结构 3. 循环队列 (Circular Queue) 队列存放数组被当作首尾相接的表处理。 队头front、队尾rear自加1时从maxSize -1直接进到0，可用语言的取模(余数)运算实现。 队头front自加1: front = (front+1) % maxSize; 队尾rear自加1: rear = (rear+1) % maxSize; 队列初始化：front = rear = 0; 队空条件：front == rear 或 Length() == 0; 队满条件：(rear+1) % maxSize == front 或 Length() == maxSize – 1。 一、表达式基础 一个表达式由操作数(亦称运算对象)、操作符 (亦称运算符) 和分界符组成。 算术表达式有三种表示： 中缀(infix)表示 操作数 操作符 操作数，如 A+B； 前缀(prefix)表示 操作符 操作数 操作数，如 +AB； 后缀(postfix)表示 操作数 操作数 操作符，如 AB+； 二、表达式的中缀表示 表达式中相邻两个操作符的计算次序为： 优先级高的先计算； 优先级相同的自左向右计算； 当使用括号时从最内层括号开始计算。 五、中缀算术表达式求值算法 使用两个栈，操作符栈optr (operator)，操作数栈opnd (operand)， 对中缀表达式求值的一般规则： 在optr栈中压入一个= 。 从输入流获取一字符ch。 取出optr的栈顶optrTop 。 当optrTop != =或ch != = 时, 循环执行以下工作, 否则结束算法。此时在opnd栈的栈顶得到运算结果。 while(optrTop!== ||ch != = ){ ① 若ch不是操作符，则将字符放回输入流(cin.putback)，读操作数operand并进opnd栈，并读入下一字符送入ch； ② 若ch是操作符，将比较ch的优先级和optrTop的优先级： ? 若optrTopch，则ch进optr栈，从中缀表达式取下一字符送入ch； ? 若optrTopch，则从opnd栈退出a2和a1，从optr栈退出θ, 形成运算指令 (a1)θ(a2)，结果进opnd栈； ? 若optrTop=ch(此处特指optrTop与ch的优先级相等)且ch == )，此时optrTop为(，则从optr栈退出栈顶的‘(’，对消括号，然后从中缀表达式取下一字符送入ch ； ? 若optrTop e ch，则出现表达式错误，终止执行。 ③ 取出optr的栈顶optrTop。 } 六、中缀表达式中操作符的优先级的另一个表示方法 Isp叫做栈内(in stack priority)优先数，实际为表达式中左操作符的优先数。 Icp叫做栈外(in coming priority)优先数，实际为表达式中右操作符的优先数。 操作符优先数相等的情况只出现在括号配对或栈底的=号与输入流最后的=号配对时。 七、中缀算术表达式求值的另一种算法 使用两个栈，操作符栈optr (operator)，操作数栈opnd (operand)， 对中缀表达式求值的一般规则： 在optr栈中压入一个= 。 从输入流获取一字符ch。 取出optr的栈顶optrTop 。 当optrTop != =或ch != = 时, 循环执行以下工作, 否则结束算法。此时在opnd栈的栈顶得到运算结果。 while(optrTop != = ||ch != = ){ ① 若ch不是操作符，则将字符放回输入流