数据结构与算法栈和队列

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

1、数据结构与算法栈和队列赵颖zhaoying511@126.com中南大学，思考：栈和队列是线性结构吗？它俩各有什么特点？举例说明实际生活中有哪些使用栈和队列来思考和解决现实问题的？栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按“后进先出”的规则进行操作，而队列必须按“先进先出”的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。目录栈的定义栈的存储实现与基本操作（顺序栈与链栈）栈的应用举例队列的定义队列的存储实现与基本操作队列的应用举例目录教

2、学重点：栈的定义及逻辑特点，栈的基本运算；栈的顺序存储结构及运算实现；栈的链式存储结构及运算实现；队列的定义及逻辑特点，队列的基本运算；队列的顺序存储结构及其上的运算实现；队列的链式存储结构及运算实现。教学难点顺序栈的溢出、栈满的判断；循环队列的队空、队满判断条件；循环队列上的插入、删除操作目录栈的定义栈的存储实现与基本操作（顺序栈与链栈）栈的应用举例栈的定义栈的定义栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。通常称往栈顶插入元素的操作为“入栈”称删除栈顶元素

3、的操作为“出栈”a1topbottoman....进栈出栈栈的定义栈的特点因为后入栈的元素先于先入栈的元素出栈，故被称为是一种“后进先出”的结构，因此又称LIFO（LastInFirstOut的缩写）表。很多书上都以如右图所示的铁路调度站形象地表示栈的这个特点。右图所示栈中有三个元素，进栈的顺序是a1、a2、a3，当需要出栈时其顺序为a3、a2、a1退栈示例（kedcba）进栈示例（abcdekl）栈的定义栈的举例举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出

4、最下面的那只碗。举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。栈的定义栈的抽象数据类型ADT与基本操作列表目录栈的定义栈的存储实现与基本操作（顺序栈与链栈）栈的应用举例顺序栈的存储结构与基本操作栈的顺序存储栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素。顺序栈的程序定义有典型的2种：用指针实现、用数组实现。用指针实现比较灵活，用数组实现比较简单。下面我们以用指针来实现的栈作为课堂讲解然后我们以用数组来实现的栈作为课堂练习顺序栈的存储结构与基本操作顺序栈类型定义（指针实现）如

5、下所示：#defineSTACK_INIT_SIZE100;//栈的初始数据元素数目#defineSTACKINCREMENT10;//增量typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//栈当前可使用的最大容量}SqStack;顺序栈的存储结构与基本操作Top与base指针的关系：空栈a进栈b进栈aabtopbasetopbasetopbasetoptopabcdee进栈abcdef进栈溢出abde出栈cbasebasebasetop顺序栈的存储

6、结构与基本操作顺序栈（指针实现）-----初始化栈SStatusInitStack(SqStack&S){S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(Elemtype));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}顺序栈的存储结构与基本操作顺序栈（指针实现）-----入栈StatusPush(SqStack&S,SElemTypee){//插入元素e为新的栈顶元素if(S.t

7、op–S.base>=S.stacksize){//栈满，追加存储空间S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)exit(overflow);//存储空间分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}//Push顺序栈的存储结构与基本操作顺序栈（指针实现）-----出栈StatusPop(

8、SqStack&S,SElemType&e){//若栈不空，则删除栈顶元素，用e返回其值，并返回OK；否则返回RRORif(S.top==S.base)returnERROR;e=*--S.top;retu