武汉软件工程职业学院《数据结构讲义》第08讲-栈.docVIP

武汉软件工程职业学院《数据结构讲义》第08讲-栈

第三

第三章栈和队列

第八

第八讲栈

1．掌握栈的定义及其运算。

2．了解俄栈的顺序存储结构。

3.掌握栈的链式存储结构。

教学重点：

栈的链式储表示与实现方法

教学难点：

栈的定义及两种存储结构，尤其注意栈满和栈空的概念

授课内容

第三章栈和队列

栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故称运算受限制的线性表。

3．1栈

３.１.

栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。如图3.1.1所示栈中有三个元素，进栈的顺序是a1、a2、a3，当需要出栈时其顺序为a3、a2、a1，所以栈又称为后进先出的线性表（LastInFirstOut），简称LIFO

入栈出栈

入栈

出栈

a3

a2

a1

top

top

top=-1

top=-1top=0top=4top=2top=-1

(a)空栈(b)一个元素(c)5个元素(d)3个元素(e)空栈

图3.2栈顶指针top与栈中数据元素的关系

⑴置空栈：首先建立栈空间，然后初始化栈顶指针。

SeqStack*Init_SeqStack()

{SeqStack*s;

s=malloc(sizeof(SeqStack));

s-top=-1;returns;

}

⑵判空栈

intEmpty_SeqStack(SeqStack*s)

{if(s-top==-1)return1;

elsereturn0;

}

⑶入栈

intPush_SeqStack(SeqStack*s,datatypex)

{if(s-top==MAXSIZE-1)return0;/*栈满不能入栈*/

else{s-top++;

s-data[s-top]=x;

return1;

}

}

⑷出栈

intPop_SeqStack(SeqStack*s,datatype*x)

{if(Empty_SeqStack(s))return0;/*栈空不能出栈*/

else{*x=s-data[s-top];

s-top--;return1;}/*栈顶元素存入*x，返回*/

}

⑸取栈顶元素

datatypeTop_SeqStack(SeqStack*s)

{if(Empty_SeqStack(s))return0;/*栈空*/

elsereturn(s-data[s-top]);

}

以下几点说明：

1.对于顺序栈，入栈时，首先判栈是否满了，栈满的条件为：s-top==MAXSIZE-1，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。

2.出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。

3.1.3.栈的链式存储结构

用链式存储结构实现的栈称为链栈。通常链栈用单链表表示，因此其结点结构与单链表的结构相同，在此用LinkStack表示，即有：

typedefstructnode

{datatypedata;

structnode*next;

}StackNode，*LinkStack;

说明top为栈顶指针：LinkStacktop;

因为栈中的主要运算是在栈顶插入、删除，显然在链表的头部做栈顶是最方便的，而且没有必要象单链表那样为了运算方便附加一个头结点。通常将链栈表示成图3.3的形式。链栈基本操作的实现如下：

图

图3.3链栈示意图

top

∧

⑴置空栈

LinkStackInit_LinkStack（）

{returnNULL;

}

⑵判栈空

intEmpty_LinkStack（LinkStacktop）

{if（top==-1）return1;

elsereturn0;