《数据结构》课件-3第3章堆栈与队列

1、? ?数据结构数据结构? ?课件课件-3-3第第3 3章章堆栈与队列堆栈与队列3.1.1 堆栈的根本知堆栈的根本知识识堆栈的定义堆栈的定义1. 假设对线性表加以限定，使得插入和删除操作只能在它的某一端进行，那么这种线性表就被称为“堆栈，简称为“栈。所以，栈是一种特殊的线性表。堆栈的根本知识堆栈的根本知识2. 在一个栈中，被允许进行插入和删除的那一端称为“栈顶(Top)，不能进行插入和删除的那一端称为“栈底(Bottom)。 .栈顶与栈底.进栈与出栈 从当前栈顶处插入一个新元素，称此操作为“进栈(Push)，插入的这个元素就成为了新的栈顶；从当前栈顶处删除一个元素，称此操作为“出栈(Pop)，这

2、时栈中被删元素的下一个元素成为新的栈顶。 topbottom(空栈)(栈顶、栈底)topbottom(有3个元素的栈)(栈底元素)(栈顶元素)a1a2a3出栈 进栈 . 最后插入栈的元素肯定最先移出栈。因此，栈是一种具有“后进先出(LIFO)逻辑特点的数据结构，其意思是元素到达栈的顺序与离开栈的顺序恰好是相反的。 3.1.2 堆栈的顺序存储实现堆栈的顺序存储实现新建顺序栈的算法新建顺序栈的算法算法算法3-1算法描述(1)算法分析(2)Create_Ss (Ss, Ss_top, Ss_max) elemtype SsMAX*size; Ss_max = MAX ; Ss_top = 0 ; r

3、eturn Ok; 由于每个进栈元素所需存储量为size，故Ss申请的存储量应该是Ss_max*size。 .324Ss_top=01Ss_maxSs_maxsize高低顺序栈Ss地址方向 刚建完的顺序栈其栈顶指针Ss_top设置为0，说明此时栈为空。随着元素进、出栈，用Ss_top进行计数，从1变化到Ss_max，它实际上就是数组的下标。 .算法讨论(3) 可以用C语言的数组来实现顺序栈。由于C语言的数组下标是从0开始的，因此最初应该把Ss_top设置成“ 1 ，变化范围是从0到Ss_max-1 ，这在具体程序设计时应该注意。顺序栈的进栈算法顺序栈的进栈算法算法算法3-2算法描述(1)算法分

4、析(2)Push_Ss(Ss, Ss_top, Ss_max, x) if (Ss_top = Ss_max) return ERROR ; else Ss_top+; Ss Ss_top = x; 插入时要先判断栈是否满，已经放有Ss_max个元素的栈是不可能再实施进栈操作的。在栈不满的前提下，该算法通过如下两条操作实现进栈： Ss_top+; Ss Ss_top = x;. 当栈里有元素时，Ss_top的值有两个意义：总是指向当前栈顶元素所在的栈位，总是当前栈里已有元素的个数。 . 假设条件：Ss_top = Ss_max成立，表示栈Ss满，就不能再做进栈操作了。如果在顺序栈满时仍打算进栈

5、，就称为发生了“上溢出错。 .A1Ss_top2顺序栈Ss3(Ss_max=6)4B56A1Ss_top2顺序栈Ss3(Ss_max=6)456A1Ss_top2顺序栈Ss3(Ss_max=6)4B56A1Ss_top2顺序栈Ss3(Ss_max=6)456CDEFBC顺序栈的出栈算法顺序栈的出栈算法算法算法3-3算法描述(1)算法分析(2)Pop_Ss (Ss, Ss_top, x) if (Ss_top = 0 ) printf (The stack is empty !); else x = SsSs_top ; Ss_top - ; 算法通过下面两条操作实现元素的出栈： x = SsS

6、s_top ; Ss_top - ;由于Ss_top总是指向栈中栈顶元素的位置，所以应先将里面内容读出送入变量 x，然后调整 Ss_top的指向，使其指向新的栈顶元素位置。. 出栈时要注意栈是否为空。这通过条件： Ss_top = 0来判断。如果在顺序栈空时仍打算出栈，就称为发生了“下溢出错。.ASs_topASs_topASs_topASs_topASs_topASs_topASs_topSs_top栈空栈空A进栈进栈B进栈进栈B出栈出栈C进栈进栈D进栈进栈E进栈进栈E出栈出栈BBCCDCDECDE获取顺序栈栈顶元素的算法获取顺序栈栈顶元素的算法算法算法3-4算法描述(1)算法分析(2)遍历

7、顺序栈算法遍历顺序栈算法算法算法3-5算法描述(1)算法分析(2)Get_Ss(Ss, Ss_top, x) if (Ss_top = 0) printf (The stack is empty !); else x = SsSs_top ; 获取顺序栈栈顶元素的操作与出栈操作是不一样的。比照算法3-3可以知道，这里没有调整Ss_top的操作。 Display_Ss(Ss, Ss_top) i = Ss_top ; for ( i, i=0, i-) printf (%d, Ssi); 由于要从顺序栈的栈顶到栈底逐个加以显示，所以用for 循环来实现。开始先把 Ss_top赋予变量i后，进入f

8、or循环，打印一个元素，变量i就减1，直至变为0，说明已经到达栈底了。 注意，操作“i = Ss_top ;是非常必要的。假设没有它，而是直接使用Ss_top那么算法执行完毕后，Ss_top就指向了顺序栈的栈底。这样一来，就再也找不到原先的栈顶在那里了。 .堆栈的链式存储实现堆栈的链式存储实现 当采用链式存储结构实现一个堆栈时，就称它为“链栈。由于堆栈是线性表的一个特例，因此，链栈就是链表的一个特例。.空链栈的形式 .Ls_top:(栈顶指针)Ls_top:(栈顶指针)(栈顶元素)(栈底元素)创立一个空链栈的算法创立一个空链栈的算法算法算法3-6算法描述(1)算法分析(2)Create_Ls

9、(Ls_top) Ls_top = NULL ; 创立一个链栈Ls很容易，只要建立一个栈顶指针Ls_top，并将它设置成NULL即可。 由于链栈是以单链表结构的形式表示的，是进栈和出栈操作都被限制在表首进行的一种单链表，因此不需要设表头结点。.一般链栈的形式.链栈的进栈算法链栈的进栈算法算法算法3-7算法描述(1)算法分析(2) 说明：这时的进栈，是指根据栈顶指针Ls_top的指向，将一个新的数据元素结点插入到链表之首的位置，成为新的栈顶元素。Push_Ls(Ls_top, x) ptr = malloc (size) ; ptr-Data = x ; ptr-Next = Ls_top ;

10、Ls_top = ptr ;. 先通过函数malloc()，申请一块存储空间，大小为size(一个存储结点的尺寸)。 . 接着做步操作，图(a)中的虚线给出的是当链栈为空时的进栈情形；图(b)中的虚线给出的是当链栈不为空时的进栈情形。 对于链栈而言，是动态申请存储结点，然后进行插入，所以根本不用考虑发生上溢的问题，这是链栈的一大优点。 .Ls_top:Ls_top=ptr ptr-Next=Ls_top ptr-Data=xptrLs_top: ptr-Data=xptrLs_top=ptr ptr-Next=Ls_top(a) 空链栈的插入(b) 非空链栈的插入(原栈顶元素)(欲插入元素)(

11、欲插入元素).链栈的出栈算法链栈的出栈算法算法算法3-8算法描述(1)算法分析(2) 说明：这时的出栈，即根据Ls_top的指向，读出当前的栈顶元素后，调整Ls_top将元素的存储结点从链中删除，释放它占用的存储区。.Pop_Ls (Ls_top, x) if (Ls_top = NULL) printf (The linked stack is underflow!); else ptr = Ls_top ; x = ptr-Data ; Ls_top = ptr-Next ; free (ptr) ; 算法先检查链栈的下溢问题。检查一个链栈是否为空，只要看指针Ls_top是否为NULL即可

12、。 . 链栈非空时，图(a)中的步给出的是链栈中只有一个元素时的出栈示意；图(b)中的给出的是一般情况下栈顶元素出栈的示意。 ptr=Ls_topptr free(ptr) Ls_top=ptr-Next x=ptr-DataX:Ls_top:(a) 只有一个元素时的链栈出栈Ls_top:ptr x=ptr-DataX: ptr=Ls_top free(ptr) Ls_top=ptr-Next(栈顶元素栈顶元素)(栈顶元素栈顶元素)(b) 一般情况时的链栈出栈(链栈底链栈底)队列的根本知识队列的根本知识1.队列的定义2.队列的根本知识.队尾与队首进队与出队 假设对线性表加以限定，使得插入操作在

13、表的一端进行，删除操作在表的另一端进行，那么这种线性表被称为“队列 。所以，队列是一种特殊的线性表。 在一个队列中，被允许进入队列的一端称为“队尾，被允许退出队列的一端称为“队首。 . 当元素从队列的队尾插入时，称为“进队，进入的元素成为新的队尾元素；从当前的队首删除一个元素时，称为“出队，被删元素的下一个元素成为了新的队首。 先进入队列的元素肯定先出队列。因此，队列是具有“先进先出(FIFO)逻辑特点的数据结构，其意是元素到达队列的顺序与离开队列的顺序是完全一致的。 .队列Q的前进方向a1a2a3an-1an出队进队队首队尾 队列的顺序存储实现队列的顺序存储实现.创立顺序队列的算法创立顺序队

14、列的算法算法算法3-9算法描述(1)算法分析(2) 当采用顺序式存储结构实现一个队列时，就称它为“顺序队列。由于队列是线性表的一个特例，因此，顺序队列就是顺序表的一个特例。Create_Qs(Qs_front, Qs_rear, Qs_max) elemtype QsMAX*size; Qs_max = MAX ; Qs_front = 0; Qs_rear = 0 ; return OK ;. 创立顺序队列Qs时，除需要分配一个连续的存储区、给出它的最大容量Qs_max外，还需要设置两个指针：指示队列首元素的队首指针Qs_front，指示队列尾元素的队尾指针Qs_rear。 . 最初，指针Q

15、s_front、Qs_rear都设置为0，成为一个空队列，整个队列最多可以容纳下Qs_max个元素。12345Qs_maxQs_rear=0Qs_front=0顺序队列Qs ：低高 由于顺序队列队尾指针Qs_rear初始为0，而顺序队列第1个可用队位的编号为1，因此往队尾插入一个元素时，先要将队尾指针加1，得到插入的真正位置，然后才能进行插入操作。顺序队列的进队算法顺序队列的进队算法算法算法3-10算法描述(1)算法分析(2)Insert_Qs(Qs_rear, Qs_max, x) if (Qs_rear = Qs_max) printf (The queue is overflow!);

16、else Qs_rear + ; QsQs_rear = x ; . 只有队列不满时，才能往里面插入新的元素，这是通过判断条件： Qs_rear = Qs_max是否成立而知的。假设条件成立，表示队列已满，就不能再进队了，否那么说发生“上溢。 12345Qs_maxQs_rearQs_front=0顺序队列Qs ：a1a2a3a4a5an算法讨论(3) 图里给出的是一种真正的队满。因为在那里，除了满足条件： Qs_rear = Qs_max外，还满足条件： Qs_rear-Qs_front=Qs_max这说明队列里已不再有空闲的队位可供新元素插入使用了。.顺序队列的出队算法顺序队列的出队算法算

17、法算法3-11算法描述(1)算法分析(2)Delete_Qs(Qs_front, Qs_rear, x) if (Qs_front = Qs_rear) printf (The queue is empty!); else Qs_front+ ; x = QsQs_front ; 由于队首指针Qs_front初始为0，而顺序队列第1个元素的编号为1，因此从队首删除元素时，先要将队首指针加1，得到删除的真正位置，然后才能进行删除操作。. 只有在顺序队列里有元素时，才能做出队操作。判断顺序队列是否为空的条件是： Qs_front = Qs_rearA123456780Qs_front、Qs_rea

18、r123456780Qs_frontBCDQs_rearE123456780Qs_frontBCDQs_rear123456780F123456780Qs_frontBCDQs_rear123456780Qs_frontGQs_rearE123456780Qs_frontFDQs_rearG123456780Qs_frontHQs_rearQs_front、Qs_rear 右图满足条件： Qs_rear-Qs_front=Qs_max但因Qs_rear指向了队列末，不能再通过Qs_rear往队列里插入新元素，所以是一种特殊的队“满情形。算法讨论(3) 这是队列“满的两种特殊情形：Qs里实际上有

19、空位，只是它们不能通过Qs_rear的管理进行分配罢了。这种有空闲空间、但又不能进行队列插入的情形，称为“假溢出。. 右图满足条件： Qs_rear-Qs_frontNext = NULL ; */. 由于链式队列是链表的特例，因此不必为其分配固定的存储区，而是通过函数malloc()根据需要以元素的存储结点大小实行动态存储分配。. 随数据的进队、出队，队尾、队首在不停地变化着，所以在创立链队Lq时，要设置两个指针：指示首元素的队首指针 Lq_front，指示尾元素的队尾指针 Lq_rear 。链式队列LqLq_front :Lq_rear:(头结点)链式队列LqLq_front :Lq_re

20、ar:(头结点)a1a2an(a) 空链式队列(b) 一般链式队列带头结点的链式队列进队算法带头结点的链式队列进队算法算法算法3-19算法描述(1)算法分析(2)Insert_Lq(Lq_rear, x) ptr = malloc(size) ; ptr-Data = x ; ptr-Next = Lq_rear-Next ; Lq_rear-Next = ptr ; Lq_rear = ptr ;. 先通过malloc()函数动态申请一个由指针ptr指向的存储结点，然后执行算法中标有的4个操作步骤。. 以下图是原链队为空时进入链式队列的的4个操作步骤执行情形。. 以下图是原链队为非空时进入链

21、式队列的的4个操作步骤执行情形。链式队列LqLq_front :Lq_rear:(头结点)a1链式队列LqLq_front :Lq_rear:(头结点)x ptr-Data=x ptr-Next=Lq_rear-Next Lq_rear-Next=ptrptr Lq_rear=ptr Lq_rear-Next=ptr ptr-Data=xx Lq_rear=ptrptr ptr-Next=Lq_rear-Next带头结点的链式队列出队算法带头结点的链式队列出队算法算法算法3-20算法描述(1)算法分析(2)Delete_Lq(Lq_front, Lq_rear, x) if (Lq_front

22、 = Lq_rear) printf (The linked queue is empty!) ; else ptr = Lq_front-Next ; x = ptr-Data ; Lq_front-Next = ptr-Next ; if (ptr-Next = NULL) Lq_rear = Lq_front ; free (ptr); . 出队操作时先要判断队列是否为空，判断链式队列为空的条件是： Lq_front = Lq_rear . 出队操作中，需注意原队列里只有一个元素的情形，即当条件： ptr-Next = NULL成立时，删除该元素后要调整Lq_rear，让它指向队列的头结

23、点，否那么它就 “悬空了。 以下图所示为原先队列里只有一个元素a1时，删除它的步操作过程示意。.链式队列LqLq_front :Lq_rear:(头结点)a1 Lq_front-Next=ptr-Next ptr=Lq_front-Nextx Lq_rear=Lq_frontptr x=ptr-Data free(ptr) 在队列里只有一个数据结点时，做出队操作就要对指针Lq_rear进行调整，以便让它指向头结点。可用改进的算法Delete_Lq1()，来防止队尾指针的调整。算法讨论(3).Delete_Lq1(Lq_front, Lq_rear, x) if (Lq_front = Lq_r

24、ear) printf (The linked queue is empty!) ; else ptr = Lq_front ; Lq_front = Lq_front-Next ; free (ptr); x = Lq_front-Data ; 该算法只修改链式队列首指针Lq_front，不动尾指针Lq_rear。具体地，出队时删除头结点，把要出队的队首元素结点改为头结点。这样一来，即使原来队列里只有一个数据元素，也不用修改队尾指针Lq_rear。. 以下图是链式队列里只有一个数据结点时，出队操作的实施步骤 。 . 以下图是一般链式队列出队操作的实施步骤 。.LqLq_front :Lq_r

25、ear:(新的头结点)x ptr=Lq_front Lq_front=Lq_front-Next free(ptr)ptr x=Lq_front-Dataa1LqLq_front :Lq_rear:(新的头结点)x ptr=Lq_front Lq_front=Lq_front-Next free(ptr)ptr x=Lq_front-Dataa1a2a3(原头结点)(原头结点) 所谓“算术表达式，是指用算术运算符将操作数连接起来组成的式子。算术表达式求值，是程序设计语言编译时必须解决的一个根本问题。 3.3.1 在算术表达式求值中使用堆在算术表达式求值中使用堆栈栈.算术表达式的概念算术表达式的

26、概念1. 常见的算术表达式的特点是运算符被置于两个操作数的中间，按“先括号内后括号外、“先乘除后加减、“同级运算先左后右的运算规那么进行求值。这种“运算符被置于两个操作数中间形式的算术表达式，称之为是“中缀表达式。 . 算术表达式还有前缀和后缀两种形式。如果将运算符放于两个操作数的前面，那就是“前缀表达式。如果将运算符放于两个操作数的后面，那就是“后缀表达式。 后缀表达式的特点是没有括号，没有运算符间的优先级，计算完全按照运算符出现的先后次序进行。因此，在语言编译系统里，总是先把中缀表达式转为后缀表达式，然后对后缀表达式进行一遍扫描，求得其结果。. 我们不去探究如何利用堆栈把中缀表达式转换为后

27、缀表达式，然后再求表达式值的问题。我们在此只是简单地介绍在中缀表达式的根底上，如何通过堆栈能够求得它的值。. 在栈开始工作前，往op栈底放一个特殊的运算符，比方“#，规定它的优先级为最低，以便扫描表达式时，遇到的第1个运算符可以顺利进入op栈。利用中缀表达式求表达式的值利用中缀表达式求表达式的值2. 设两个栈：num用以在处理表达式时存放取得的操作数，称操作数栈；op用以在处理表达式时存放取得的运算符，称运算符栈。 .自左至右扫描表达式“3+2*15/3时，具体的求值规那么如(1)(4)所示。 .假设当前取得的是操作数，就让它进num栈。 假设当前取得的是运算符，且优先级高于op栈栈顶元素的优

28、先级，就进op栈，并继续向右扫描。 假设当前取得的是运算符，其优先级不高于op栈顶元素的优先级，那么它暂时不进op栈，而是让当前op栈的顶元素出栈，让num栈顶的两个元素出栈，执行该运算，将计算结果进入num栈。然后将欲进栈的运算符与op栈栈顶元素比较，按不同情况处理。1234#numop#numop3#numop3+#numop3+2#numop3+2*#numop3+2*15#numop3+30/3#numop3+30/#numop3+30/#numop3+10#num op13(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k) 自左至右扫描表达式“48(18/ (4+5)

29、*3)的值时，需要增加对圆括号的处理，即除规那么(1)(4)外，还要增加(5)、(6)两条求值规那么。 #numop#numop48-#numop48-(#numop48-(18#numop48-(18/#numop48-(18/(#numop48-(18/(4#numop48-(18/(4+#numop48-(18/(4+5#numop48-(18/9*3#numop48-(2*#numop48-(2*#numop48-(2*#numop48-(6#numop48-6#numop42(b)(c)(d)(e)(a)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o). 遇到右圆括号符“时，不进op栈，而是不断地弹出op里的运算符、弹出num里的两个操作数、做运算、结果进num 栈，直至遇到左圆括号，让它出op 栈，继续进行后面的处理。遇到左圆括号符“时，