《数据结构》课程授课教案（讲稿）第三章 堆栈和队列 第一节 堆栈

课程名称：数据结构第5周，第5讲次摘要第三章堆栈和队列授课题目（章、节）第一节堆栈【目的要求】通过本讲课程的学习，理解堆栈的逻辑结构定义及在两种存储结构上如何实现堆栈的基本运算。要求在掌握堆栈的特点的基础上，懂得在什么样的情况下能够使用堆栈。【重点】明确堆栈的逻辑结构特点，掌握入栈、出栈等基本操作。【难点】堆栈的应用。内容【本讲课程的引入】线性表是最简单常用的线性结构，这一次课我们再介绍一种线性结构这种线性结构可以看成是线性表的特殊情况，也可以称作是一种受限的线性表，这就是堆栈。【本讲课程的内容】3.1堆栈3.1.1堆栈的基本概念堆栈（栈）是一种特殊的线性表，堆栈的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置进行插入和删除操作，而堆栈只允许在固定一端进行插入和删除操作。也可以看作是在表尾进行插入、删除操作的线性表。表尾（即an-1端）称为栈顶；表头（即ao端）称为栈底插入元素到栈顶的操作，称为入栈。从栈顶删除一个元素的操作，称为出栈。从输入和输出数据元素的位置关系看，堆栈的功能和一种火车调度装置的功能类同。火车头1火车头1=O(a)O(c)注：堆栈可以完成比较复杂的数据元素特定序列的转换任务，但它不能完成任何输入输出序列的转换任务。例：一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？解：可以通过穷举所有可能性来求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入，3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；即321；③1、2、3入，3、2、1出

课程名称：数据结构 第 5 周，第 5 讲次 摘 要 授课题目（章、节） 第三章 堆栈和队列 第一节 堆栈 【目的要求】通过本讲课程的学习，理解堆栈的逻辑结构定义及在两种存储结构上如何实现堆栈的基本运算。 要求在掌握堆栈的特点的基础上，懂得在什么样的情况下能够使用堆栈。 【重 点】明确堆栈的逻辑结构特点，掌握入栈、出栈等基本操作。 【难 点】堆栈的应用。 内 容 【本讲课程的引入】线性表是最简单常用的线性结构，这一次课我们再介绍一种线性结构， 这种线性结构可以看成是线性表的特殊情况，也可以称作是一种受限的线性表，这就是堆 栈。 【本讲课程的内容】 3.1 堆栈 3.1.1 堆栈的基本概念 堆栈（栈）是一种特殊的线性表，堆栈的数据元素以及数据元素间的逻辑关系和线性 表完全相同，其差别是线性表允许在任意位置进行插入和删除操作，而堆栈只允许在固定 一端进行插入和删除操作。也可以看作是在表尾进行插入、删除操作的线性表。 表尾(即 an-1 端)称为栈顶 ; 表头(即 a0 端)称为栈底 插入元素到栈顶的操作，称为入栈。 从栈顶删除一个元素的操作，称为出栈。 从输入和输出数据元素的位置关系看，堆栈的功能和一种火车调度装置的功能类同。 注：堆栈可以完成比较复杂的数据元素特定序列的转换任务，但它不能完成任何输入输出 序列的转换任务。 例：一个栈的输入序列为 1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是 什么？ 解：可以通过穷举所有可能性来求解： ① 1 入 1 出， 2 入 2 出，3 入 3 出， 即 123； ② 1 入 1 出， 2、3 入，3、2 出， 即 132； ③ 1、2 入，2 出， 3 入 3 出， 即 231； ④ 1、2 入，2、1 出，3 入 3 出， 即 213； ⑤ 1、2、3 入，3、2、1 出， 即 321；

合计有5种可能性。例：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？答：43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，每压入一数便立即弹出即可。讨论：有无通用的判别原则？有！若输入序列是,PjPkPi…(Pj<Pk<Pi），一定不存在这样的输出序列,Pi.PPk..3.1.2堆栈抽象数据类型数据集合堆栈的数据集合可以表示为ao,al，…,an-1，每个数据元素的数据类型可以是任意的类类型。操作集合（1）入栈pushobi)：把数据元素obj插入堆栈。（2）出栈pop)：出栈，删除的数据元素由函数返回。（3）取栈顶数据元素getTop（)：取堆栈当前栈顶的数据元素并由函数返回。（4）非空否notEmptyO：若堆栈非空则函数返回true，否则函数返回false。堆栈数据类型的Java接口定义：public interface Stackfpublic void push(Object obj)throwsException;public Object popOthrows Exception;public ObjectgetTop()throws Exception;public boolean notEmptyO:h3.1.3顺序堆栈1顺序堆栈的存储结构顺序存储结构的堆栈称作顺序堆栈。2顺序堆栈类的设计publicclassSeqStackimplementsStackffinal int defaultSize = 10;int top;Object[] stack;int maxStackSize;public SeqStackOinitiate(defaultSize);1public SeqStack(int sz)(initiate(sz):1private void initiate(int sz){maxStackSize = sz;

合计有 5 种可能性。 例：一个栈的输入序列是 12345，若在入栈的过程中允许出栈，则栈的输出序列 43512 可 能实现吗？12345 的输出呢？ 答：43512 不可能实现，主要是其中的 12 顺序不能实现； 12345 的输出可以实现，每压入一数便立即弹出即可。 讨论：有无通用的判别原则？ 有！若输 入序列 是 .,Pj.Pk.Pi .(Pj<Pk<Pi) ，一 定不存 在这样 的输出序 列 .,Pi.Pj.Pk . 3.1.2 堆栈抽象数据类型 数据集合 堆栈的数据集合可以表示为 a0,a1,.,an-1，每个数据元素的数据类型可以是任意的 类类型。 操作集合 （1）入栈 push(obj)：把数据元素 obj 插入堆栈。 （2）出栈 pop()：出栈, 删除的数据元素由函数返回。 （3）取栈顶数据元素 getTop()：取堆栈当前栈顶的数据元素并由函数返回。 （4）非空否 notEmpty()：若堆栈非空则函数返回 true，否则函数返回 false。 堆栈数据类型的 Java 接口定义： public interface Stack{ public void push(Object obj) throws Exception; public Object pop() throws Exception; public Object getTop() throws Exception; public boolean notEmpty(); } 3.1.3 顺序堆栈 1 顺序堆栈的存储结构 顺序存储结构的堆栈称作顺序堆栈。 2 顺序堆栈类的设计 public class SeqStack implements Stack{ final int defaultSize = 10; int top; Object[] stack; int maxStackSize; public SeqStack(){ initiate(defaultSize); } public SeqStack(int sz){ initiate(sz); } private void initiate(int sz){ maxStackSize = sz;

top = 0;stack = new Object[sz];public void push(Object obj)throws Exceptiontif(top==maxStackSize)(thrownewException（"堆栈已满！"）；1stack[top] = obj:top ++;子public Object popO) throws Exceptiontif(top ==o) thrownewException("堆栈己空！")；1top--;return stack[top]:子public Object getTopO throws Exceptionif(top ==o)(thrownewException（"堆栈已空！"）：+return stack[top-1];public boolean notEmptyOfreturn (top>0);13.1.4链式堆栈1链式堆栈的存储结构和单链表相同，链式堆栈也是由一个个结点组成的，每个结点由两个域组成，一个是存放数据元素的数据元素域element，另一个是存放指向下一个结点的对象引用（即指针）域next。以头指针为栈顶，在头指针处插入或删除。2链式堆栈类的设计public class LinStack implements StackfNode head;int size;public voidLinStackOhead = null;size = 0;Ipublic void push(Object obj)(head =newNode(obj,head);size ++;public ObjectpopOthrows Exceptionf

top = 0; stack = new Object[sz]; } public void push(Object obj) throws Exception{ if(top == maxStackSize){ throw new Exception("堆栈已满！"); } stack[top] = obj; top ++; } public Object pop() throws Exception{ if(top == 0){ throw new Exception("堆栈已空！"); } top-; return stack[top]; } public Object getTop() throws Exception{ if(top == 0){ throw new Exception("堆栈已空！"); } return stack[top-1]; } public boolean notEmpty(){ return (top > 0); } } 3.1.4 链式堆栈 1 链式堆栈的存储结构 和单链表相同，链式堆栈也是由一个个结点组成的，每个结点由两个域组成，一个是存 放数据元素的数据元素域 element，另一个是存放指向下一个结点的对象引用（即指针） 域 next。以头指针为栈顶，在头指针处插入或删除. 2 链式堆栈类的设计 public class LinStack implements Stack{ Node head; int size; public void LinStack(){ head = null; size = 0; }public void push(Object obj){ head = new Node(obj, head); size ++; } public Object pop() throws Exception{

if(size =- 0) {thrownewException（"堆栈已空！"）：1Object obj = head.element;head = head.next;size --;return obj:1public booleannotEmptyO(return head != null;1publicObjectgetTop({return head.element;113.2堆栈的应用堆栈是各种软件系统中应用最广泛的数据结构之一。括号匹配和表达式计算是编译软件中的基本问题，其软件设计中都需要使用堆栈。3.2.1括号匹配问题假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号是否正确匹配的函数。以表达式（［（1+2）×3+4)×5+6)×7为例分析。设计分析：算术表达式中右括号和左括号匹配的次序，正好符合后到的括号要最先被匹配的后进先出的操作特点，因此可以借助一个堆栈来进行判断。算法描述：（1）顺序扫描算术表达式，当遇到三种类型的左括号时让这些括号进栈：（2）当扫描到某一种括号的右括号时，比较当前栈顶括号是否与之匹配，若匹配则退栈继续进行判断；（3）若当前栈顶括号与当前扫描的括号类型不相同，则左右括号配对次序不正确；（4）若字符串当前为某种类型的右括号而堆栈为已空，则右括号多于左括号：（5）字符串循环扫描结束时，若堆栈非空，则说明左括号多于右括号；（6）否则左右括号配对匹配正确。public static void expIsCorrect(Stringlexp,int n)(SeqStackmyStack=newSeqStackOfor(inti=O;i<n;i++)f1I1if((exp[ij.Equals("("))(exp[il.Equals("["))(exp[i].Equals("(")))myStack.push(exp[i]);&&elseif((exp[i].Equals(")"))myStack.notEmptyO&&myStack.getTop().Equals("("))myStack.popO:elseif((exp[i].Equals(")"))&&myStack.notEmptyO&&myStack.getTop(.Equals("("))(Console.WriteLine（"左、右括号匹配次序不正确！"）

if(size == 0){ throw new Exception("堆栈已空！"); } Object obj = head.element; head = head.next; size -; return obj; } public boolean notEmpty(){ return head != null; } public Object getTop(){ return head.element; } } 3.2 堆栈的应用 堆栈是各种软件系统中应用最广泛的数据结构之一。括号匹配和表达式计算是编译软 件中的基本问题，其软件设计中都需要使用堆栈。 3.2.1 括号匹配问题 假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别 表达式中括号是否正确匹配的函数。 以表达式{[（1＋2）×3＋4]×5＋6}×7 为例分析。 设计分析：算术表达式中右括号和左括号匹配的次序，正好符合后到的括号要最先被匹 配的后进先出的操作特点，因此可以借助一个堆栈来进行判断。 算法描述： （1）顺序扫描算术表达式，当遇到三种类型的左括号时让这些括号进栈； （2）当扫描到某一种括号的右括号时，比较当前栈顶括号是否与之匹配，若匹配则退栈 继续进行判断； （3）若当前栈顶括号与当前扫描的括号类型不相同，则左右括号配对次序不正确； （4）若字符串当前为某种类型的右括号而堆栈为已空，则右括号多于左括号； （5）字符串循环扫描结束时，若堆栈非空，则说明左括号多于右括号； （6）否则左右括号配对匹配正确。 public static void expIsCorrect(String[] exp,int n) { SeqStack myStack = new SeqStack(); for(int i = 0; i < n; i ++){ if((exp[i].Equals("(")) || (exp[i].Equals("[")) || (exp[i].Equals("{"))) myStack.push(exp[i]); else if((exp[i].Equals(")")) && myStack.notEmpty()&& myStack.getTop().Equals("(")) myStack.pop(); else if((exp[i].Equals(")")) && myStack.notEmpty() && !myStack.getTop().Equals("(")){ Console.WriteLine("左、右括号匹配次序不正确！");

return;1elseif((exp[i].Equals("]"))&&myStack.notEmpty&myStack.getTopO.Equals("["))myStack.popO;&&elseif((exp[i].Equals("j"))myStack.notEmptyO&&!myStack.getTopO.Equals("["))(Console.WriteLine（"左、右括号匹配次序不正确！"）；return;子if((exp[i].Equals(")"))&&&&elsemyStack.notEmpty()myStack.getTop(.Equals("("))myStack.pop;elseif((exp[i].Equals("}"))&&myStack.notEmptyO&&!myStack.getTopO.Equals("["))Console.WriteLine（"左、右括号匹配次序不正确！"）；return;小11elseif(((exp[i].Equals(")"))(exp[i].Equals("]"))(exp[i].Equals(")")))&&！myStack.notEmpty())(Console.WriteLine（"右括号多于左括号！"）：return;11if(myStack.notEmptyO)Console.WriteLine（"左括号多于右括号！"）；elseConsole.WriteLine（"左、右括号匹配次序正确！"）：【本讲课程的小结】这次课我们学习了一种受限的线性表一一堆栈，之所以是受限的是因为只能在固定的一端进行插入和删除操作，也就使得堆栈这种结构的特点是后进先出，不论是顺序堆栈还是链式堆栈，它的入栈出栈操作实现起来相对比较容易，所以我们对于堆栈关键是要掌握它的结构特点，并根据它的特点在实际问题中能够合理的应用。【本讲课程的作业】编写判断一个字符序列是否是回文的函数，要求使用堆栈

return; } else if((exp[i].Equals("]")) && myStack.notEmpty()&& myStack.getTop().Equals("[")) myStack.pop(); else if((exp[i].Equals("]")) && myStack.notEmpty() && !myStack.getTop().Equals("[")){ Console.WriteLine("左、右括号匹配次序不正确！"); return; } else if((exp[i].Equals("}")) && myStack.notEmpty() && myStack.getTop().Equals("{")) myStack.pop(); else if((exp[i].Equals("}"))&& myStack.notEmpty() && !myStack.getTop().Equals("{")){ Console.WriteLine("左、右括号匹配次序不正确！"); return; } else if(((exp[i].Equals(")")) || (exp[i].Equals("]")) || (exp[i].Equals("}"))) && !myStack.notEmpty()){ Console.WriteLine("右括号多于左括号！"); return; } } if(myStack.notEmpty()) Console.WriteLine("左括号多于右括号！"); else Console.WriteLine("左、右括号匹配次序正确！"); } 【本讲课程的小结】这次课我们学习了一种受限的线性表——堆栈，之所以是受限的是因 为只能在固定的一端进行插入和删除操作，也就使得堆栈这种结构的特点是后进先出，不 论是顺序堆栈还是链式堆栈，它的入栈出栈操作实现起来相对比较容易，所以我们对于堆 栈关键是要掌握它的结构特点，并根据它的特点在实际问题中能够合理的应用。 【本讲课程的作业】 编写判断一个字符序列是否是回文的函数，要求使用堆栈