数据结构 栈与队列ppt课件.ppt

《数据结构 栈与队列ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章栈与队列第3章栈与队列学习目的要求:栈的基本概念和栈的基本运算。栈在计算机中的应用。队列的基本概念和队列的基本运算。队列在计算机中的应用。3.1栈3.2队列第3章栈与队列3.1栈3.1.1栈的定义栈（Stack）又称堆栈，是一种特殊的线性表，它限定线性表中元素的插入和删除操作只能在线性表的一端进行。允许插入和删除的一端为变化的一端，称为栈顶（top），栈顶的第一个元素称为栈顶元素，栈的另一端称为栈底（bottom）。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成

2、为新的栈顶元素。从一个栈删除一个元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。所以又把栈称为后进先出表（LastInFirstOut），简称为LIFO表。3.1栈（1）InitStack（）初始化操作，建立一个空栈S。（2）GetTop（&S，&x）取栈顶元素操作，若栈S不空，则取栈顶元素，用x返回栈顶元素。（3）Push（&S，x）进栈操作，在S栈的栈顶压入一个元素x。（4）Pop（&S，&x）出栈操作，删除已存在且非空的栈S的栈顶元素，用x返回栈顶元素。（5

3、）Empty（&S）判断一个栈是否为空，若S为空栈，返回一个真值。3.1栈栈常用的基本操作:3.1.2栈的顺序存储结构及其运算栈的顺序存储结构，简称顺序栈，它是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。#defineMAXLEN10typedefintelementtype;typedefstruct/*栈的顺序存储结构定义*/{elementtypeelement[MAXLEN];/*存放栈元素的数组*/inttop;/*栈指针*/}SqStack;3.1栈当有新元素进栈时，栈

4、顶指针向上移动，top加1。当有元素出栈时，栈顶指针向下移动，top减1。用数组element［MAXLEN］作为栈的存储空间，element［top］为栈顶元素，当top=-1时栈为空;当top=0时，栈中有一个元素;当top=MAXLEN-1时，表示栈满。当top=-1，即栈为空时，从空栈中再删除一个元素，栈将溢出，称为“下溢”。当top=MAXLEN-1，即栈满时，向栈中再插入一个元素，栈也将溢出，称为“上溢”。3.1栈1.初始化顺序栈SqStackInitStack_sq()/*建立一个

5、空栈s*/{SqStacks;s.top=-1;return(s);}3.1栈2.取栈顶元素intGetTop_sq(SqStack*s,elementtype*x){if(s->top==-1)return(0);/*栈空返回0*/else{*x=s->element[s->top];return(1);}}3.1栈3.进栈操作intPush_sq(SqStack*s,elementtypex){if(s->top==MAXLEN-1)return(0);/*栈满返回0*/s->top++;s

6、->element[s->top]=x;return(1);}3.1栈4.出栈操作intPop_sq(SqStack*s,elementtype*x){if(s->top==-1)return(0);/*栈空返回0*/*x=s->element[s->top];s->top--;return(1);}3.1栈5.判空栈操作intEmpty_sq(SqStack*s){return(s->top==-1);}栈是动态变化的数据结构，顺序栈在某种程度上可以满足这种动态结构所对应动态操作，但是一般数组

7、长度的定义有一定局限性。3.1栈3.1.3栈的链式存储结构及其运算栈的链式存储结构简称为链栈，它是一种特殊的单链表，也是一种动态存储结构，不用预先分配存储空间。typedefstructnode/*定义链栈结点*/{intdata;/*这里以整型数据为例*/structnode*next;/*指针类型,存放下一个结点地址*/}NODE;3.1栈1.进栈当向链栈插入一个新元素时，首先要向系统申请一个结点的存储空间，将新元素的值写入新结点的数据域中，然后修改栈顶指针。NODE*pushstack(N

8、ODE*top,intx)/*进栈操作*/{NODE*p;p=(NODE*)malloc(sizeof(NODE));p->data=x;/*将要插入的数据x存储到结点p的数据域中*/p->next=top;/*将p插入链表头部,即链栈顶部*/top=p;return(top);}3.1栈2.出栈出栈时，先取出栈顶元素的值，再修改栈顶指针，释放原栈顶结点。NODE*popstack(NODE*top,int*p){NODE*q;/*定义q结点*/if(top!=NULL)/*如果栈不空*/{q=