3.2 栈的实现在线视频

同学们大家好，我是云南大学信息学院教师孔兵

这节课我们讨论栈的表示和实现

前面我们提到，就数据结构来说栈就是一个线性表

所以适应于线性表的存储方式

对栈也是适合的

栈也有两种实现方式

顺序映象和非顺序映象

不过由于栈的插入和删除操作受到了限制

栈的插入和删除位置都是在栈顶

为了方便插入和删除操作的实现

我们在作栈的存储设计的时候

也做了相应的考虑

先来看一下，栈的顺序表示和实现

类似于线性表的顺序存储的定义

我们首先定义了栈的初始容量和增量

栈的存储结构被定义为一个结构体

栈的存储空间仍然是通过malloc函数动态申请的

结构体中包含两个指向数据元素的指针

其中base指向分配给栈的存储空间的起始地址

另外一个指针Top，约定指向栈顶元素的下一个存储位置

也就是栈顶元素位置加1的那个存储位置

设计一个top指针指向栈顶

主要是因为栈的插入和删除位置都是在栈顶

有了这个指针，栈的插入和删除就比较方便了

最后一个成员是栈的容量，就是栈中能够存放元素的个数

用typedef给栈的结构体

取一个类型名sqstack

下面我们通过图示看一下栈中最重要的两个操作

入栈和出栈的实现

刚才已经提到过，我们有这样的约定

base这个指针指向分配空间的起始地址

Top这个栈顶指针，指向栈顶元素后的一个存储单元

假设我们定义了一个栈s

那么对栈的初始化主要就是为栈分配存储空间

分配了存储空间以后

栈底指针s.base

指向分配空间的起始

因为初始时栈中还没有元素

栈顶指针s.top也指向分配空间的起始地址

这个时候

栈就是一个空栈

我们注意到这个时候s.top等于s.base

这个条件可以作为栈空的判断条件

假设有a，b，c，d，e，5个元素入栈

入栈后的情况如图②所示

我们注意到现在s.Top

指向的是栈顶元素E后面的一个存储单元

当有一个新的元素入栈的时候

它的存储位置就应该是s.Top所指的这个单元

这个元素入栈以后，s.Top需要后移一个单元

指向新的栈顶元素的后一个位置

所以入栈操作，两条主要的语句是

*S.top=e; 入栈元素存到*S.top所指的这个存储单元

S.Top++，栈顶指针指向下一个存储单元

我们再看一下出栈的情况

前面有过约定

栈顶指针s.Top是指向栈顶元素的下一个单元

出栈的时候，我们先做S.top--;

让s.Top指向栈顶元素

随后e=*S.top; 把栈顶指针所指单元的数据

赋值给引用e

下面看一下具体函数

先看一下，入栈函数的参数

入栈函数涉及到两个参数

一个是要入栈的对象栈s

一个是要入栈的元素e

我们先看IF语句的条件

S.top-S.base>=S.stacksize

如果这个条件成立，那么说明是栈满

类似于线性表的顺序存储，在这种情况下

可以通过realloc函数

申请一块更大的空间

作为栈的存储空间

申请如果失败就返回

申请如果成功那么相应的指针和容量要重新设置

函数中，最后红色的这个语句就是入栈操作

*S.top++=e; 。我们要注意这里是一个后加

意思是先把e赋值给s.Top所指的存储单元

然后s.Top再做一个自加

和前面图②中的两个语句的作用是一样的

入栈成功，就返回，OK

下面看一下出栈操作

出栈操作涉及到的参数也是两个

一个是要出栈的对象栈s.一个是引用e

用来带回出栈的元素

IF语句的条件S.top==S.base

如果成立的话

从前面的图①中已经看到了

这个时候呢，栈为空

出栈操作不可能完成

返回error.

如果栈不空，没有返回

就可以执行出栈操作了

e=*--S.top; 这里减减是一个前减

意思是说，先对S.top做自减

让S.top指向栈顶元素

然后再把自减以后所指的栈顶元素赋值给引用e，带回

这个语句的作用和前面图③中看到的两个句子的作用是等价的

出栈成功以后返回，OK

有一种特殊的顺序栈经常会被提到

就是所谓的双向栈

双向栈是指两个栈共用一块存储空间

如图所示

栈1的栈底设在0号单元这一边段

栈2的栈底设在m-1单元的这一边

当有元素插入到两个栈中的时候

两个栈的栈顶，对向增长

什么时候我们有可能使用到双向栈呢？

如果在一个程序中

我们需要同时使用两个数据元素类型相同的栈

并且两个栈对空间的使用有时间差

这种情况下，双向栈是一个很好的选择

使用双向栈可以节省存储空间

使用双向栈时应该注意两个问题

一是，如果两个栈的入栈和出栈操作使用同样的函数

应该通过参数区分要操作的是那一个栈

两个栈的操作细节并不相同

二是注意栈满的条件

一般以栈顶相遇为栈满

下面我们看一下

栈的非顺序映象，链式栈

栈的链式存储，和普通线性表的链式存储类似

用单链表来实现栈的存储

在链表中，我们还是每个元素存储一个结点

然后通过指针把这些结点串联起来

形成单链表

同样是为了插入和删除的便利

栈的链表和普通线性表的链表还是有些差异的

一是不设头结点

链表指针直接指向首元结点

因入栈和出栈都是在栈顶

操作上没有什么差异

头结点的作用不明显

二是首元结点里边存的是an

就是栈顶这个元素，它的next指针

指向存储an-1的结点

然后依次类推

链表中最后一个结点存的是a1

就是栈底元素

可以看出，在栈的链式存储当中

我们是通过指前驱的方式来描述关系的

也就是每个结点的指针指的是存储它前驱的结点

那么指向链表的s指针

就直接指向首元结点

之所以这样设计

就是为了方便栈的入栈和出栈操作

前面我们说过

入栈和出栈操作都是在栈顶

现在我们的栈顶，是链表的首元结点

这样呢，插入删除操作都是比较容易实现的

我们简单看一下

入栈操作当中

首先申请一个结点,用指针q指向它

把入栈元素赋值给q->data

新结点插入以后

它是新的栈顶元素

成为新的首元结点

。q->next=S->next;

让q的指针指向原来的栈顶元素

S赋值q，让栈指针指向新的首元结点

下面看一下出栈

q=S;让指针q指向首元结点

也就是我们要出栈的这个结点

S=S->next;让栈指针s指向新的栈顶元素

也就是目前栈顶元素的前驱an-1结点

e=q->data; 把出栈元素赋值给引用e

最后，把q所指这个结点的存储空间用Free释放

好，同学们

关于栈的表示和实现

我们就讨论到这儿

下次课再见