数据结构 第3章 栈与队列

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

1、第3章栈与队列本章导读栈和队列是两种特殊的线性结构，是线性表特例。一般，在线性表上的插入、删除运算等操作不受限制，而栈和队列上的插入、删除操作会受某种限制，对它们来说，插入和删除运算均是对首尾两个元素进行的。本章主要介绍栈和队列的逻辑特征及其在计算机中的存储表示、栈和队列的基本运算的算法描述以及栈和队列的应用。教学目标通过本章学习，要求掌握以下内容：1．栈的基本概念和栈的基本运算。2．栈的应用。3．队列的基本概念和队列的基本运算。4．队列的应用。3.1栈3.1.1栈的定义栈（Stack）是限定仅在表的一端进行插入或删除操作的线性表。在表中允许进

2、行插入或删除操作的一端称为栈项（Top），而另一端称为栈底（Bottom）。不含元素的栈称为空栈。栈的插入和删除操作分别称为进栈和出栈。进栈是将一个数据元素存放栈顶，出栈是将栈顶元素取出。若给定栈S=（a1，a2，…，an），如图3-1所示的栈中，a1是栈底元素，an是栈顶元素。由于只允许在栈顶进行插入和删除，所以栈的操作是按“后进先出”的原则进行的。因此栈又称为后进先出表，即LIFO（LastInFirstOut）线性表。图3-1线结构示意图在日常生活中，有许多类似栈的例子，如刷洗盘子时，把洗净的盘子一个接一个地向上放（相当于进栈），取盘子时

3、，则从上面一个接一个地向下拿（相当于出栈）。栈的基本运算有五种：1．初始化栈：将栈置为空栈，不含任何元素，只建立起栈顶指针。2．进栈：向栈顶插入一个新的元素。3．出栈：删除栈顶元素。4．判栈空：判断一个栈是否为空栈。3.1.2栈的顺序存储及其基本操作的实现栈的顺序存储结构，简称顺序栈。它是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。与顺序表的数据类型描述类似，栈的C语言描述如下：#defineMAX50/*定义MAX为栈的最大容量，例如设为10*/ints[MAX］;/*定义数组s，用来存储栈的元素，以整数为例*/inttop;/

4、*定义栈顶指针为top*/在这个描述中，假设栈中数据元素的类型是整型，数组s存放栈中数据元素，数组最大容量为MAX，栈顶指针为top。由于栈顶的位置经常变动，所以要设一个栈顶指针top。栈顶指针top指向下一次进栈的数据元素存放位置。当栈中没有数据元素时，栈是空栈，这时top=0。当栈中放满元素时，top=MAX，表示栈满。若再有数据元素进栈，栈将溢出，称为“上溢（overflow）。这是一个错误状态。反之，当top=0时，再要进行出栈操作时，则发生“下溢“（underflow）。在应用中通常作为控制程序转移的条件。下面以一个例子来说明栈的操作

5、。设有一栈s=（a，b，c，d，e），则MAX为5，它的顺序存储结构如图3-2所示。其中图3-2（a）是空栈状况；图3-2（b）是进栈一个元素“a”之后的栈状况；图3-2（c）是在图3-2（b）基础上连续将元素“b、c、d、e”进栈之后的栈状况，此时是栈满状况，不允许有元素进栈；图3-2（d）是在图3-2（c）基础上出栈一个元素后的栈状况。由此可见，非空栈中的栈顶指针top始终指向栈顶元素的下一个位置。图3-2栈的顺序存储结构顺序栈的基本运算有初始化栈、进栈、出栈和判栈空。下面分别介绍栈的几种基本运算。1．初始化栈初始化栈算法描述如下：void

6、initstack（inttop）{/*建立一个空栈s*/top=0;/*设置栈顶指针top为0，表示栈空*/}2．进栈进栈是在栈顶插入新的元素。由于进栈时可能会遇到栈满，导致操作不能进行，此时进行溢出处理，返回函数值0;如果栈未满，则栈顶指针加1，插入新元素，返回函数值1。进栈算法描述如下：#defineMAX10inttop;/*定义栈顶指针为top*/intpush（ints[]，intx）｛/*x为要插入的新元素*/if（top==MAX）｛printf（″stackoverflow″）;/*栈满信息*/return(0);｝else｛

7、s[top］=x;/*数据入栈*/top=top+1;/*当栈不满时，栈顶加1*/printf（″ok″）;return(1);｝｝main（）/*主程序*/｛inta［MAX］=｛1，2，3，4，5｝;intx=56,i;top=5;if(push（a,x）)for(i=0;i

8、0;如果栈不空，则使栈顶指针减1，然后将栈顶元素取出，返回函数值1。出栈算法描述如下:#defineMAX10inttop;intpop（ints[]