栈(C语言版).ppt

《栈(C语言版).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章栈和队列本章主要介绍下列内容栈的概念、存储结构及其基本操作队列的概念、存储结构及其基本操作栈与队列的应用举例本章目录3.1栈13.2队列23.3栈和队列的应用举例33.4本章小结4结束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、，即构造一个空战S。（2）判栈空。若栈S为空，则返回1；否则返回0。（3）判栈满。若栈S已满，则返回1，否则返回0，该运算只适用于栈的顺序存储结构。（4）进栈。若栈S未满，将数据元素x插入栈S中，使其为栈S的栈顶元素。（5）出栈。若栈非空，从栈S中删除当前栈顶元素。（6）取栈顶元素。若栈S非空，取栈顶元素，操作结果只是读取栈顶元素，栈S不发生变化。返回到本节目录3.1.3顺序栈由于栈是操作受限制的线性表，因此与线性表类似，栈也有两种存储结构，即顺序存储结构和链式存储结构。1.顺序栈的定义栈的顺序存储结构称为顺序栈。类似于顺序表的类型定义，顺序栈是用一个预设的足够长度的一维数组和一个记录栈顶元素

4、位置的变量来实现。顺序栈中栈顶指针与栈中数据元素的关系如图3-2所示。图3-2顺序栈中栈顶指针与栈中数据元素的关系图返回到本节目录2.顺序栈的类型定义#defineStackSize100/*顺序栈存储空间的总分配量*/typedefstruct/*顺序栈存储类型*/{DataTypedata[StackSize];/*存放顺序栈的数组*/inttop;/*记录栈顶元素位置的变量*/}SeqStack;顺序栈被定义为一个结构体类型，其中DataType为栈元素的数据类型，可以根据需要而指定某种具体的类型。data为一个一维数组，用于存储栈中的数据元素，top为int类型，用于记录栈顶元素所在的

5、位置。注：顺序栈的程序是由C语言描述，C语言的数组下标从0开始。3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现（1）初始化栈操作首先创建一个空栈，并将栈顶下标top初始化为-1，voidInitStack(SeqStack*S){S->top=-1;/*初始化的顺序栈为空*/}3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现（2）判断栈空操作判断是否是空栈（即S->top==-1），若栈S为空，则返回1；否则返回0。#defineTRUE1#defineFALSE0intStackEmpty(SeqStack*S){if(S->top==-1)/*栈为空*/returnTRUE;

6、elsereturnFALSE;}3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现（3）判栈满操作intStackFull(SeqStack*S){if(S->top==StackSize-1)returnTRUE;elsereturnFALSE;}3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现（4）进栈操作进栈操作的过程如图3-3所示。先判断栈S如图3-3（a）是否为满，若不满再将记录栈顶的下标变量top加1如图3-3（b），最后将进栈元素放进栈顶位置上如图3-3（c）所示，算法描述见算法3.4。图3-3进栈操作过程图3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现（4）

7、进栈操作intPush(SeqStack*S,DataTypex){if(StackFull(S))/*栈为满*/{printf("栈满!");returnFALSE;}/*栈满不能进栈*/else/*栈不为满*/{S->top++;S->data[S->top]=x;returnTRUE;}}3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现（5）出栈操作出栈操作的过程如图3-4所示。先判断