《《数据结构实用教程(C语言版)》第3章栈和队列》-精选课件（公开PPT）》由会员分享，可在线阅读，更多相关《《数据结构实用教程(C语言版)》第3章栈和队列》-精选课件（公开PPT）（81页珍藏版）》请在金锄头文库上搜索。
1、,数据结构实用教程（C语言版）中国水利水电出版社,第3章栈和队列,本章主要介绍下列内容栈的概念、存储结构及其基本操作队列的概念、存储结构及其基本操作栈与队列的应用举例,本章目录,结束,3.1栈,3.1.1栈的概念3.1.2栈的基本操作3.1.3顺序栈3.1.4链栈,返回到总目录,3.1.1栈的概念,例如，在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取，这种后进先出的线性结构称为栈（stack），栈又称为后进先出（lastinfirstout）的线性表，简称LIFO表。栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。插入元
2、素又称为进栈，删除元素又称为出栈。允许进行插入和删除操作的一端称为栈顶（top），另一端称为栈底（bottom）。处于栈顶位置的数据元素称为栈顶元素，处于栈底位置的数据元素称为栈底元素。不含任何数据元素的栈称为空栈。,返回到本节目录,假设有一个栈S=（a1，a2，an），栈中元素按a1，a2，an的次序进栈后，进栈的第一个元素a1为栈底元素，出栈的第一个元素an为栈顶元素，也就是出栈的操作是按后进先出的原则进行的，其结构如图3-1所示。图3-1栈结构示意图,3.1.1栈的概念,返回到本节目录,3.1.2栈的基本操作,栈除了在栈顶进行进栈与出栈外，还有初始化、判空等操作，常用的基本操作有：（1）
3、初始化栈InitStack(S)。其作用是构造一个空栈S。（2）判断栈空EmptyStack(S)。其作用是判断是否是空栈，若栈S为空，则返回1；否则返回0。（3）进栈Push(S,x)。其作用是当栈不为满时，将数据元素x插入栈S中，使其为栈S的栈顶元素。（4）出栈Pop(S,x)。其作用是当栈S不为空时，将栈顶元素赋给x，并从栈S中删除当前栈顶元素。（5）取栈顶元素GetTop(S,x)。其作用是当栈S不为空时，将栈顶元素赋给x并返回，操作结果只是读取栈顶元素，栈S不发生变化。,返回到本节目录,3.1.3顺序栈,由于栈是操作受限制的线性表，因此与线性表类似，栈也有两种存储结构，即顺序存储结构
4、和链式存储结构。1.顺序栈的定义栈的顺序存储结构称为顺序栈。类似于顺序表的类型定义，顺序栈是用一个预设的足够长度的一维数组和一个记录栈顶元素位置的变量来实现。顺序栈中栈顶指针与栈中数据元素的关系如图3-2所示。图3-2顺序栈中栈顶指针与栈中数据元素的关系图,返回到本节目录,2.顺序栈的类型定义#defineMAXLEN100/*顺序栈存储空间的总分配量*/typedefcharElemType;/*定义ElemType为char类型*/typedefstruct/*顺序栈存储类型*/ElemTypedataMAXLEN;/*存放顺序栈的数组*/inttop;/*记录栈顶元素位置的变量*/Seq
5、Stack;顺序栈被定义为一个结构体类型，其中ElemType为栈元素的数据类型，可以根据需要而指定某种具体的类型。data为一个一维数组，用于存储栈中的数据元素，top为int类型，用于记录栈顶元素所在的位置。注：顺序栈的程序是由C语言描述，C语言的数组下标从0开始。,3.1.3顺序栈,返回到本节目录,3.顺序栈的基本操作实现（1）初始化栈操作首先创建一个空栈，并将栈顶下标top初始化为-1，算法描述见算法3.1。算法3.1voidInitStack(SeqStack*S)S-top=-1;/*初始化的顺序栈为空*/,3.1.3顺序栈,返回到本节目录,3.顺序栈的基本操作实现（2）判断栈空操
6、作判断是否是空栈（即S-top=-1），若栈S为空，则返回1；否则返回0，算法描述见算法3.2。算法3.2intEmptyStack(SeqStack*S)if(S-top=-1)/*栈为空*/return1;elsereturn0;,3.1.3顺序栈,返回到本节目录,3.顺序栈的基本操作实现（3）进栈操作进栈操作的过程如图3-3所示。先判断栈S如图3-3（a）是否为满，若不满再将记录栈顶的下标变量top加1如图3-3（b），最后将进栈元素放进栈顶位置上如图3-3（c）所示，算法描述见算法3.3。图3-3进栈操作过程图,3.1.3顺序栈,返回到本节目录,3.顺序栈的基本操作实现（3）进栈操作算
7、法3.3intPush(SeqStack*S,ElemTypex)if(S-top=MAXLEN-1)/*栈为满*/printf(栈满!);return0;/*栈满不能进栈*/else/*栈不为满*/S-top+;S-dataS-top=x;return1;,3.1.3顺序栈,返回到本节目录,3.顺序栈的基本操作实现（4）出栈操作出栈操作的过程如图3-4所示。先判断栈S如图3-4（a）是否为空，若不空将栈顶元素取出赋给指针变量*x，如图3-4（b）所示，然后将记录栈顶的下标变量top减1如图3-4（c）所示，算法描述见算法3.4。图3-4出栈操作过程图,3.1.3顺序栈,返回到本节目录,3.顺
8、序栈的基本操作实现（4）出栈操作intPop(SeqStack*S,ElemType*x)if(EmptyStack(S)/*调用判空函数EmptyStack(S)，判断栈是否为空*/printf(栈空!);return0;/*栈空不能出栈*/else/*栈不为空*/*x=S-dataS-top;S-top-;return1;,3.1.3顺序栈,返回到本节目录,3.顺序栈的基本操作实现（5）取栈顶元素将栈顶元素赋给指针变量*x，操作结果只是读取栈顶元素，栈S不发生变化，算法描述见算法3.5。算法3.5intGetTop(SeqStack*S,ElemType*x)if(EmptyStack(S
9、)/*调用判空函数EmptyStack(S)，判断栈是否为空*/printf(栈空!);return0;else/*栈不为空*/*x=S-dataS-top;return1;,3.1.3顺序栈,返回到本节目录,3.顺序栈的基本操作实现上述算法3.1-3.5为顺序栈的基本操作函数，读者可以对照执行主函数调用后的结果分析，进一步了解顺序栈的各种操作的过程实现。（6）设计主函数如下：main()SeqStackS;ElemTypex;InitStack(,3.1.3顺序栈,返回到本节目录,3.顺序栈的基本操作实现（6）设计主函数如下：printf(c元素进栈n);Push(,3.1.3顺序栈,上述程
10、序的执行结果如下：依次进栈元素为：r元素进栈a元素进栈h元素进栈c元素进栈栈顶元素为：c出栈序列为：char,返回到本节目录,1.链栈的定义用链式存储结构实现的栈称为链栈，链栈与不带头结点单链表组织形式相似，因为栈的主要操作是在栈顶进行插入与删除操作，显然将链表的第一个结点作为栈顶是最方便的，因此，没有必要如单链表那样为了操作方便附加一个头结点，通常链栈表示如图3-5所示。图3-5链栈结构示意图,3.1.4链栈,返回到本节目录,2.链栈的类型定义与单链表的类型定义相同，在此用LinkStack命名。链栈的类型定义如下：typedefcharElemType;/*定义ElemType为char类
11、型*/typedefstructnode/*链栈存储类型*/ElemTypedata;/*定义结点的数据域*/structnode*next;/*定义结点的指针域*/LinkStack;,3.1.4链栈,返回到本节目录,3.链栈的基本操作实现（1）初始化栈操作首先创建一个空栈，将链栈类型的变量S=NULL标识为空栈，算法描述见算法3.6。算法3.6LinkStack*InitStack()LinkStack*S;S=NULL;/*初始化栈为空*/returnS;,3.1.4链栈,返回到本节目录,3.链栈的基本操作实现（2）判断栈空操作判断是否是空栈（即S=NULL），若栈S为空，则返回1；否则
12、返回0，算法描述见算法3.7。算法3.7intEmptyStack(LinkStack*S)if(S=NULL)/*栈为空*/return1;elsereturn0;,3.1.4链栈,返回到本节目录,3.链栈的基本操作实现（3）进栈操作先创建一个以x为值的新结点p，其data域值为x则进栈操作步骤如下：将新结点p的指针域指向原栈顶S（执行语句p-next=S）。将栈顶S指向新结点p（执行语句S=p）。进栈操作的过程如图3-6所示，算法描述见算法3.8。注：进栈操作的与语句执行顺序不能颠倒，否则原S指针其后的链表将丢失。图3-6进栈操作过程图,3.1.4链栈,返回到本节目录,3.链栈的基本操作实
13、现（3）进栈操作算法3.8LinkStack*Push(LinkStack*S,ElemTypex)LinkStack*p;p=(LinkStack*)malloc(sizeof(LinkStack);/*生成新结点*/p-data=x;/*将x放入新结点的数据域*/p-next=S;/*将新结点插入链表表头之前*/S=p;/*新结点作为栈顶*/returnS;/*返回栈顶S*/,3.1.4链栈,返回到本节目录,3.链栈的基本操作实现（4）出栈操作先将结点栈顶S数据域中的值赋给指针变量*x，则删除操作步骤如下：结点p指针域指向原栈顶S（执行语句p=S）。栈顶S指向其的下一个结点（执行语句S=S
14、-next）释放p结点空间（执行语句free(p)）。出栈的过程如图3-7所示，算法描述见算法3.9。图3-7出栈操作过程图,3.1.4链栈,返回到本节目录,3.链栈的基本操作实现（4）出栈操作LinkStack*Pop(LinkStack*S,ElemType*x)LinkStack*p;if(EmptyStack(S)/*调用判空函数EmptyStack(S)，判断栈是否为空*/printf(栈空!);returnNULL;/*栈空不能出栈*/else/*栈不为空*/*x=S-data;/*栈顶元素取出赋给x*/p=S;/*p结点指向原栈顶S*/S=S-next;/*原栈顶S指向其下一个结
15、点*/free(p);/*释放原栈顶空间*/returnS;/*返回栈顶S*/,3.1.4链栈,返回到本节目录,3.链栈的基本操作实现（5）取栈顶元素将栈顶元素赋给指针变量*x，操作结果只是读取栈顶元素，栈S不发生变化，算法描述见算法3.10。intGetTop(LinkStack*S,ElemType*x)if(EmptyStack(S)/*调用判空函数EmptyStack(S)，判断栈是否为空*/printf(栈空!);return0;else/*栈不为空*/*x=S-data;/*栈顶元素赋给变量x*/return1;,3.1.4链栈,返回到本节目录,3.链栈的基本操作实现上述算法3.6
16、-3.10为链栈的基本操作函数，读者可以对照执行主函数调用后的结果分析，进一步了解链栈的各种操作的过程实现。（6）设计主函数如下：main()LinkStack*S;ElemTypex;S=InitStack();printf(依次进栈元素为：n);printf(r元素进栈n);S=Push(S,r);printf(a元素进栈n);S=Push(S,a);printf(h元素进栈n);S=Push(S,h);,3.1.4链栈,返回到本节目录,3.链栈的基本操作实现（6）设计主函数如下：printf(c元素进栈n);S=Push(S,c);GetTop(S,上述程序的执行结果与顺序栈对应程序的执行结果相同。,3.1.4链栈,返回到本节目录,3.2队列,3.2.1队列的概念3.2.2队列的基本操作3.2.3顺序队列3.2.4循环队列3.2.5链队列,返回到总目录,例如，在日常生活中的排队上车，排队的规则是不允许“插队”。后来的人需站在队尾，每次总是队头先上车。这种先进先出的规则应用在数据结构中称为队列（queue），队列又称为先进先出（firstinfirsto
