第04章栈和队列(Java版)详解.ppt

第4章 栈和队列 4.1 栈 4.2 队列 4.3 递归 目的：使用栈或队列求解应用问题。 要求：栈和队列的顺序和链式存储结构实现。 重点：栈和队列的设计和应用。 难点：栈或队列的使用场合，以及如何使用 栈和队列求解应用问题。 4.1 栈 4.1.1 栈抽象数据类型 栈（stack）是一种线性表，插入和删除操作只允许在线性表的一端进行。先进后出。 图4.1 栈（顺序栈）及其状态变化 {A, B, C, D} {入栈, 入栈, 出栈, 入栈, 入栈, 出栈, 出栈, 出栈} 栈抽象数据类型ADT，栈接口 public interface StackT { public abstract boolean isEmpty(); //判空 public abstract void push(T x); //x入栈 public abstract T peek(); //返回栈顶，未出栈 public abstract T pop(); //出栈，返回栈顶 } 习题4-3 习4-3 能否使用一个线性表对象作为栈，或将栈声明为继承线性表？入栈调用insert(0,x)函数，出栈调用remove(0)函数？为什么？ 【习题解答】都不能。 4.1.2 顺序栈 //顺序栈类，最终类，实现栈接口，T表示元素类型 public final class SeqStackT implements StackT { private SeqListT list; //顺序表 public SeqStack(int capacity) //构造空栈 public SeqStack() //构造空栈 public boolean isEmpty() //判空 public void push(T x) //x入栈 public T peek() //返回栈顶（未出栈） public T pop() //出栈，返回栈顶元素 } 习题解答4-4 使用顺序表对象作为栈成员变量的操作效率分析 4.1.3 链式栈 图4.3 链式栈的入栈和出栈操作 链式栈类LinkedStackT //链式栈类，最终类，实现栈接口，T表示元素类型 public final class LinkedStackT implements StackT { private SinglyListT list; //单链表 public LinkedStack() //构造空栈 public boolean isEmpty() //判空 public void push(T x) //x入栈 public T peek() //返回栈顶（未出栈） public T pop() //出栈，返回栈顶元素 } 习题解答4-4 使用单链表对象作为栈成员变量的操作效率分析 4.1.4 栈的应用 栈是嵌套调用机制的实现基础 使用栈以非递归方式实现递归算法 【例4.1】 括号匹配的语法检查。 图4.5 表达式中圆括号匹配的语法检查 【例4.2】 使用栈计算算术表达式值 中缀表达式：1+2*(3-4)+5 习题4-5 【习题解答】ABCDEF+*G/-H+*+IJ+K*- （1）将中缀表达式转换为后缀表达式 （2）后缀表达式求值 Expression public class Expression { StringBuffer toPostfix(String infix) //返回将infix中缀表达式转换成的后缀表达式 int toValue(StringBuffer postfix) //计算后缀表达式的值 } 【思考题4-2】 4.2 队列 4.2.1 队列抽象数据类型 队列（queue）是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。先进先出。 4.2.1 队列抽象数据类型 //队列接口，描述队列抽象数据类型，T表示元素类型 publ