数据结构栈和队列课件

1、栈和队列Chapter 3 栈和队列3.1 栈 3.1.12 栈的定义、特征和抽象数据类型 3.1.3 顺序栈 3.1.4 链栈 3.2 顺序栈的应用3.3 队列 3.3.12 队列的定义、特征和抽象数据类型 3.3.34 顺序队列和顺序循环队列 3.3.5 链队列 3.3.6 顺序队列的应用（定义、特征和应用是重点要求能正确应用它们解决实际问题）3.1 栈3.1.1 栈（Stack）的基本概念 定义什么是栈?盘子的叠放： 取出或放入一个盘子, 在顶部操作才是最方便的栈是限定只能在表的一端进行 插入和删除运算的线性表例：a0a1an-2an-1插入/入栈(Push) a0,a1, , an-1

2、an-1, a1,a0表尾/栈顶(top)表头/栈底删除/出栈(Pop)栈s=(a0,a1,an-1) 特征 每次取出（或删除）的总是刚压进的元素，而最先压入的元素则被放在栈底后进先出 （Last In First Out, LIFO）ADT Stack 数据元素： ai,i=0,1,n-1 (n0)， ai类型为DataType 结构：对所有的数据元素ai (0in-2)存在次序关系 , a0无前趋，an-1无后继。 逻辑操作：设S为 Stack 型 Initiate(S) /构造一个空栈S。 NotEmpty(S) /*判断栈S非空否，若S非空，则返回1， 否则返回0。 */ Push(S

3、,x) /在栈S的栈顶插入一个值为x的元素。 Pop(S,x) /*删除栈S的栈顶元素，被删除的栈顶元素 通过x带回。*/ GetTop(S) /取栈S中栈顶元素，并由函数返回。3.1.2 栈的抽象数据类型3.1.3 顺序栈及其实现 顺序栈类定义class SeqStackprivate:DataType dataMaxStackSize;/堆栈int top;/栈顶位置指示器、表长 public:SeqStack(void) top = 0;/构造函数SeqStack(void) ; /析构函数void Push(const DataType item); /入栈DataType Pop(v

4、oid); /出栈DataType GetTop(void) const; /取栈顶数据元素int NotEmpty(void) constreturn(top != 0); /堆栈非空否 ;SeqStack.h文件实现顺序栈类#define MaxStackSize typedef char DataType; 栈操作时栈顶指针的变化情况：MaxStackSize-101栈空 top0元素A入栈后Atop110MaxStackSize-1栈操作时栈顶指针的变化情况（续）： top= MaxStackSize-1元素P出栈后ABOtopMaxStackSize01栈满ABOPPDataType

5、 SeqStack:GetTop(void) const/取当前栈顶数据元素并返回if(top = 0)cout 堆栈空! endl;exit(0); return datatop-1;/返回当前栈顶元素【顺序栈取栈顶元素算法】/时间复杂度：O(1) void SeqStack:Push(const DataType item)/把元素item入栈if(top = MaxStackSize) /栈满异常退出cout 堆栈已满! endl;exit(0);datatop = item;/先存储itemtop+;/然后top加1【 顺序栈入栈算法】/时间复杂度：O(1)DataType SeqSt

6、ack:Pop( )/出栈并返回栈顶元素if(top = 0)/栈空异常退出cout堆栈已空!endl; exit(0);top-;/top先减1return datatop;/然后取元素返回【顺序栈出栈算法】/时间复杂度：O(1)headheaddatanextan-1a03.1.4 单链栈及其实现 逻辑描述：指针方向从栈顶向下链接栈顶结点栈底结点栈顶指针非空链栈空链栈 链栈结点类定义template class LinStack;/前视定义,否则友元无法定义template /模板类型为Tclass StackNodefriend class LinStack;/定义类LinStack为友

7、元private:T data;/数据元素StackNode *next;/指针public:/构造函数1，用于构造头结点StackNode(StackNode *ptrNext = NULL)next = ptrNext;/构造函数2，用于构造其它结点StackNode(const T& item, StackNode *ptrNext= NULL)data = item;next = ptrNext;StackNode( );LinStack.h文件实现单链栈类 链栈类定义template class LinStackprivate:StackNode *head;/头指针int size

8、;/数据元素个数public:LinStack(void);/构造函数（实现略讲）LinStack(void);/析构函数（实现略讲）void Push(const T& item);/入栈T Pop(void);/出栈T GetTop(void) const;/取栈顶元素（实现略讲）int NotEmpty(void) const;/堆栈非空否（实现略讲）;template void LinStack:Push(const T& item)/新结点newNode的data域值为item，next域值为head-nextStackNode*newNode=new StackNode ( ite

9、m, head-next);head-next = newNode;/新结点插入栈顶size+;/元素个数加1【单链栈入栈算法】/时间复杂度：O(1)template T LinStack:Pop(void)if(size = 0) cout 堆栈已空无元素可删！ endl;exit(0);StackNode *p = head-next;/p:缓冲被删结点指针T data = p-data;head-next = head-next-next;/原栈顶元素结点脱链delete p;/释放原栈顶结点空间size-;/结点个数减1return data;/返回原栈顶结点的data域值 【单链栈出

10、栈算法】/时间复杂度：O(1)小 结实际应用中，顺序栈比链栈用得更广泛顺序栈容易根据栈顶位置，进行相对位移、快速定位、并读取栈的内部元素顺序栈读取内部元素的时间为O(1)，而链栈为O(n)一般来讲，栈不允许“读取内部元素”，只能在栈顶操作3.2 栈的应用*引 言通常，数据处理的逻辑或框架是：搜索（或遍历）操作对象集合，在搜索（遍历）的同时访问或处理各个对象。当遍历结束时，完成所有处理。当正在访问或处理的对象当前不能完成所有对它的处理时，需要缓存该对象。当等待到合适时机，取出该对象并完成所有对它的处理。如果先访问或处理的对象最后才能完成所有对它的处理，或者，最后访问或处理的对象最先完成所有对它的

11、处理，则采用栈作为未完成处理的对象的缓存数据结构。3.2 栈的应用 （P69 括号匹配问题 略） 1、计算算术表达式的值 中缀表达式 运算符在两个操作数的中间 需要括号改变优先级，例如 后缀表达式 操作符在两个操作数的后面后缀操作数的顺序同于中缀；操作符的顺序就是表达式计算的顺序，完全不需要括号。例如因此，后缀表达式适合用来计算表达式的值计算算术表达式值的两个步骤 对一个中缀表达式的计算可以通过两个步骤来实现： 先把中缀表达式变换为后缀表达式； 根据后缀表达式计算表达式的值。 对后缀表达式如何进行计算呢？ 很简单，只要从左到右依次扫描表达式的各单词。由于扫描到的操作数并不能马上参加运算，并且先

12、扫描到的操作数将后参与计算，因此采用栈来缓存操作数。因此，如果当前读到的是操作数，存入一个栈（操作数栈）中，如果当前读到的是运算符，就取栈前面的两个操作数（即从栈顶依次弹出两个元素）进行运算，中间结果同样存入栈中，作为下一次运算的操作数。如此反复，直到表达式处理完毕。 using namespace std;#include /调用isdigit( )函数#include #include #include “LinStack.h“/使用链栈template int IsOptr(T& c) /* 判断c是否为运算符 */ switch(c) case+: case-: case*: case

13、/: case(: case): case#: return 1; default: return 0; void main(void) LinStack s;/T类型是int PostExp(s);ExpressionTest.cpp文件实现根据后缀表达式求值 如何将中缀表达式变换成后缀表达式？ 利用运算符优先级法。 中缀表达式的计算次序（算术四则运算规则） 有括号，则先括号内后括号外； 在无括号或同层括号时，先乘除后加减； 同级运算从左到右。 从而得到两个相继出现的运算符x1（出现在前）和x2（出现在后）之间的优先关系：见书上P72表3-1。+ - * / ( ) # + - * / (

14、ERROR1 # 后缀)1置运算符栈S为空栈，然后表达式起始符#入栈。2循环：读入中缀表达式中的一个字符， 2.1 若是操作数，就将其输出，接着读下一字符(转2)； 2.2 若是运算符（x2），则与运算符栈中的栈顶元素 （ x1）比较优先级： 若x2的优先级高于x1：将x2进栈；读下一字符(转2) 若低于：则取出栈顶运算符x1 ，并作为后缀表达式 的一个单词输出，再转2.2。 若相等：若栈顶元素为(，读入的字符为)， 则( 退栈；读下一字符(转2)。 直至整个表达式处理完毕(当#时)。 例：利用上述算法，转换中缀表达式A(BCD)E为后缀表达式。 中缀表达式 Stack 输出(后缀表达式) A

15、/(B+C*D)E /(B+C*D)E A (B+C*D)E A B+C*D) E ( A +C*D) E ( AB C*D) E ( AB *D）E ( ABC 中缀表达式 Stack 输出(后缀表达式) D）E ( +* ABC ）E ( +* ABCD ）E ( + ABCD* ）E ( ABCD*+ E ABCD*+ E ABCD*+/ E ABCD*+/ ABCD*+/E ABCD*+/E,结束 3.2 栈的应用 2、实现递归算法（运行时栈）P133154多个函数的嵌套调用 例：main( )sub1( )sub2( )sub3( )RST需要保存返回地址TSR存：R，S，T取：T，

16、S，R后调用先返回递归函数是自己（直接或间接地）调用自己的函数 例2：2阶Fibonacci数列-+-=1n )2()1(1n 10n 0)(nFibnFibnFib 例1：阶乘的递归定义阶乘n!的递归定义计算n！的两个函数long fact(int n) /使用循环迭代方法，计算n!的函数long m=1;int i;if(n0)for(i=1;i=n;i+)m=m*i;return m;/时间复杂度：O(n)long Fact(int n) long y; if (n0) cout“参数错误”endl; reurn -1; if (n=0) return 1; else y=Fact(n-

17、1); return n*y; main( ) long fn=Fact(4);coutfn0) for(i=1;i=n;i+)m=m*i; return m; /时间复杂度：O(n)long Fact(int n) long y; if (n0) reurn -1; if (n=0) return 1; else y=Fact(n-1); return n*y; /时间复杂度：O(n)递归示例：2阶斐波那契数列递归函数必须包含一个递归出口。递归调用部分所使用的参数值应比函数的参数值要小，以便重复调用能最终获得基本部分所提供的值。int fibonacci(int n) if(n=0) ret

18、urn 0; if(n=1) return 1; int oneBack=1; int twoBack=0; for(int i=2;i=n;i+) int current=oneBack+twoBack; twoBack=oneBack; oneBack=current; return current;/时间复杂度：O(n)int Fibonacci(int n) if(n=0) return 0; if(n=1) return 1; return Fibonacci(n-1) +Fibonacci(n-2);/时间复杂度为O(2n)递归原理每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。递归工作栈 局部变量返回地址参数活动记录框架递归工作记录main( )4ny=Fact(3)返回4*63ny=Fact(2)返回3*22ny=Fact(1)返回2*11ny=Fact(0)Fact(4)0n返回1递归调用子程序Fact(3)递归调用子程序Fact(2)递归调用子程序Fact(1)递归调用子程序Fact(0)结果返回返回1*1结果