1.掌握栈的定义及其运算。
2.了解俄栈的顺序存储结构。
3. 掌握栈的链式存储结构。
教学重点:栈的链式储表示与实现方法。
教学难点:栈的定义及两种存储结构,尤其注意栈满和栈空的概念。
授课内容。栈和队列是在软件设计中常用的两种数据结构,它们的逻辑结构和线性表相同。其特点在于运算受到了限制:
栈按“后进先出”的规则进行操作,队按“先进先出”的规则进行操作,故称运算受限制的线性表。
栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶,另一个固定端称为栈底。当表中没有元素时称为空栈。
如图3.1.1所示栈中有三个元素,进栈的顺序是a1、a2、a3,当需要出栈时其顺序为a3、a2、a1,所以栈又称为后进先出的线性表(last in first out),简称 lifo表。
图3.1 栈示意图。
1、栈的主要算法。
在日常生活中,有很多后进先出的例子,读者可以列举。在程序设计中,常常需要栈这样的数据结构,使得与保存数据时相反顺序来使用这些数据,这时就需要用一个栈来实现。对于栈,常做的基本运算有:
栈初始化:init_stack(s)
初始条件:栈s不存在。
操作结果:构造了一个空栈。
判栈空:empty_stack(s)
初始条件:栈s已存在。
操作结果:若s为空栈返回为1,否则返回为0。
入栈: push_stack(s,x)
初始条件:栈s已存在。
操作结果:在栈s的顶部插入一个新元素x, x成为新的栈顶元素。栈发生变化。
出栈:pop_stack(s)
初始条件:栈s存在且非空。
操作结果:栈s的顶部元素从栈中删除,栈中少了一个元素。栈发生变化。
读栈顶元素:top_stack(s)
初始条件:栈s存在且非空。
操作结果:栈顶元素作为结果返回,栈不变化。
2、 顺序栈的存储实现和运算实现。
由于栈是运算受限的线性表,因此线性表的存储结构对栈也是适用的,只是操作不同而已。
利用顺序存储方式实现的栈称为顺序栈。类似于顺序表的定义,栈中的数据元素用一个预设的足够长度的一维数组来实现:datatype data[maxsize],栈底位置可以设置在数组的任一个端点,而栈顶是随着插入和删除而变化的,用一个int top 来作为栈顶的指针,指明当前栈顶的位置,同样将data和top封装在一个结构中,顺序栈的类型描述如下:
#define maxsize 1024
typedef struct
seqstack
定义一个指向顺序栈的指针:
seqstack *s;
通常0下标端设为栈底,这样空栈时栈顶指针top=-1; 入栈时,栈顶指针加1,即s->top++;出栈时,栈顶指针减1,即s->top--。栈操作的示意图如图3.2所示。
图(a)是空栈,图(c)是a、b、c、d、e 5个元素依次入栈之后,图(d)是在图(c)之后e、d相继出栈,此时栈中还有3个元素,或许最近出栈的元素d、e仍然在原先的单元存储着,但top指针已经指向了新的栈顶,则元素d、e已不在栈中了,通过这个示意图要深刻理解栈顶指针的作用。
在上述存储结构上基本操作的实现如下:
置空栈:首先建立栈空间,然后初始化栈顶指针。
seqstack *init_seqstack()
seqstack *s;
s=malloc(sizeof(seqstack));
s->top= -1; return s;
判空栈。int empty_seqstack(seqstack *s)
⑷ 出栈。int pop_seqstack(seqstack *s, datatype *x)
⑸ 取栈顶元素。
datatype top_seqstack(seqstack *s)
以下几点说明:
1. 对于顺序栈,入栈时,首先判栈是否满了,栈满的条件为:s->top= =maxsize-1,栈满时,不能入栈; 否则出现空间溢出,引起错误,这种现象称为上溢。
2. 出栈和读栈顶元素操作,先判栈是否为空,为空时不能操作,否则产生错误。通常栈空时常作为一种控制转移的条件。
用链式存储结构实现的栈称为链栈。通常链栈用单链表表示,因此其结点结构与单链表的结构相同,在此用linkstack表示,即有:
typedef struct node
datatype data;
struct node *next;
stacknode,* linkstack;
说明top为栈顶指针: linkstack top ;
因为栈中的主要运算是在栈顶插入、删除,显然在链表的头部做栈顶是最方便的,而且没有必要象单链表那样为了运算方便附加一个头结点。通常将链栈表示成图3.3的形式。
链栈基本操作的实现如下:
置空栈 linkstack init_linkstack()
return null;
判栈空。int empty_linkstack(linkstack top )
if(top==-1) return 1;
else return 0;
入栈 linkstack push_linkstack(linkstack top, datatype x
stacknode *s;
s=malloc(sizeof(stacknode));
s->data=x;
s->next=top;
top=s;
return top;
⑷ 出栈。linkstack pop_linkstack (linkstack top, datatype *x)