第三章_栈和队列

1、数据结构与算法设计（数据结构与算法设计（Java版）版）第1章 绪论第2章 线性表第3章 栈与队列第4章 串第5章 数组第6章 树和二叉树第7章 图第8章 排序第第3章章 栈和队列栈和队列3.1 栈栈3.2 队列队列 目的：目的：使用栈或队列求解应用问题。使用栈或队列求解应用问题。 要求：要求：掌握栈和队列抽象数据类型，以及顺掌握栈和队列抽象数据类型，以及顺 序和链式存储结构实现；理解对于怎序和链式存储结构实现；理解对于怎 样的应用问题，需要使用栈或队列，样的应用问题，需要使用栈或队列， 以及怎样使用。以及怎样使用。 重点：重点：栈和队列的设计和应用。栈和队列的设计和应用。 难点：难点：栈或队

2、列的使用场合，以及如何使用栈或队列的使用场合，以及如何使用 栈和队列求解应用问题。栈和队列求解应用问题。3.1 栈栈3.1.1 栈抽象数据类型栈抽象数据类型3.1.2 顺序栈顺序栈3.1.3 链式栈链式栈3.1.4 栈的应用栈的应用3.1.1 栈抽象数据类型栈抽象数据类型栈（栈（stack）是一种特殊的线性表，）是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。其插入和删除操作只允许在线性表的一端进行。 public interface SStack boolean isEmpty(); /判断是否空栈判断是否空栈 boolean push(E element); /入栈入栈 E

3、pop(); /出栈出栈 E get(); /取栈顶元素值取栈顶元素值3.1.2 顺序栈顺序栈public class SeqStack implements SStack private Object value ; private int top; /栈顶元素下标栈顶元素下标3.1.3 链式栈链式栈public class LinkedStack implements SStack private Node top;3.1.4 栈的应用栈的应用1.栈是嵌套调用机制的实现基础栈是嵌套调用机制的实现基础 2.使用栈以非递归方式实现递归算法使用栈以非递归方式实现递归算法 例例3.1 判断表达式中

4、圆括号是否匹配判断表达式中圆括号是否匹配例例3.2 使用栈计算表达式的值。使用栈计算表达式的值。中缀表达式中缀表达式1+2*(3-4)+51.将中缀表达式转换为后缀表达式将中缀表达式转换为后缀表达式2.后缀表达式求值后缀表达式求值 3.2 队列队列3.2.1 队列抽象数据类型队列抽象数据类型3.2.2 顺序队列顺序队列3.2.3 链式队列链式队列3.2.4 队列的应用队列的应用3.2.1 队列抽象数据类型队列抽象数据类型队列（队列（queue）是一种特殊的线性表，其插入和删除）是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。操作分别在线性表的两端进行。public interfac

5、e QQueue /队列接口队列接口 boolean isEmpty(); /判断队列是否为空判断队列是否为空 boolean enqueue(E element); /入队入队 E dequeue(); /出队出队 3.2.2 顺序队列顺序队列1.顺序队列，假溢出顺序队列，假溢出 2.顺序循环队列顺序循环队列 front=(front+1) % length;rear=(rear+1) % length;3.顺序循环队列类顺序循环队列类 public class SeqQueue implements QQueue private Object value; private int fron

6、t,rear; /队列头尾下标队列头尾下标3.2.3 链式队列链式队列public class LinkedQueue implements QQueue /链式队列类链式队列类 private Node front, rear; 3.2.4 队列的应用队列的应用例例3.3 求解素数环问题。求解素数环问题。 素数：质数（素数：质数（prime number）又称素数，有无）又称素数，有无限个。一个大于限个。一个大于1的的自然数自然数，除了，除了1和它本身外，和它本身外，不能被其他自然数不能被其他自然数整除整除（除（除0以外）的数称之为素以外）的数称之为素数（质数）；否则称为数（质数）；否则称为

7、合数合数。根据。根据算术基本定理算术基本定理，每一个比每一个比1大的整数，要么本身是一个质数，要么大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积；而且如果不考虑这些可以写成一系列质数的乘积；而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的质数在乘积中的顺序，那么写出来的形式是唯一的。最小的质数是。最小的质数是2。3.2.4 队列的应用队列的应用例例3.3 求解素数环问题。求解素数环问题。素数环：素数环： 将从将从1到到n这这n个整数围成一个圆环，若个整数围成一个圆环，若其中任意其中任意2个相邻的数字相加，结果均个相邻的数字相加，结果均为素数，那么这个环就成为素数环。为素数，那么这个环就成为素数环。使用顺序表和顺序队列来解素