当前课程知识点：数据结构 > 第3章 栈和队列 > 3.2 栈的顺序实现——顺序栈 > 讲解
现在，我们来学习栈的顺序实现，也就是顺序栈，先看右边这个图
我们为栈分配了连续的存储空间
容量是size，起始地址
是base，栈顶指针是top
有些同学看到这个图，可能会感到奇怪
为什么我们刚才见到的图
top是在上面，base(bottom)是在下面
而这个图恰好相反呢
是这样的
刚才那个图
我们描述的是栈的逻辑结构，跟计算机是没有关系的
而这里给出的图
是栈在内存当中的结构
我们之前讲过
在画内存的时候
我们通常是把小地址画在上面
大地址画在下面，也就是上小下大
所以，首地址应该是连续的存储空间中最小的
而top指针都是大于等于base的
所以，top在base下面
再来看
左边的代码
我们定义了一个宏，叫STACK_INIT_SIZE
栈的初始容量是100
也就是说
我们为栈分配存储空间的时候
分配了100个元素所占的存储空间
紧接着，我们定义了一个STACK_INCREMENT，用来表示栈空间不够的时候
为栈追加的元素个数所占的存储空间
紧接着
我们定义了个别名ElemType
用来作为栈中元素的类型名
我们再来看这个结构体
第一个成员base，代表连续存储空间的首地址
它就是我们刚才说的栈底，第二个成员top
它也是一个指针
它指向栈顶，需要跟大家说明的是
我们这门课程约定
top指向栈顶元素的下一个位置
也就是说
在我们这门课当中
约定top并不指向真正的栈顶元素
而是指向栈顶元素的下一个位置
或者说是下一个入栈的位置
我们看右边这个图，在这个时刻，栈当中有n个元素
我们发现，top指针并没有指向an
也就是栈顶元素
而是指向
an这个元素的下一个单元
如果这时候入栈
应该是直接放到top指向的位置
然后，top再加1，后面我们会讲到。第三个成员
是size，代表着栈的当前容量
然后，我们用typedef
给这样一个结构体，起了一个别名，叫SqStack，Sq就是顺序的意思
我们再来看几个表达式
第一个，SqStack S
我们声明了一个类型为SqStack的变量
这里的S，就是一个结构体
然后，我们取它的base成员
然后用取值运算符*
取出base指向的内容
这个应该是栈底元素
注意是栈底元素
实际上，我们很少去操纵栈底元素
因为，在栈当中
无论是插入也好
还是删除也好
都是在top这一端进行的
S.top是栈顶
元素的下一个位置的指针
刚才我已经说过了
如果这时候入栈
应该是直接放到top指向的位置
现在，第四个表达式，S.top-1
然后取内容
这时候，取出来的才是栈顶元素
也就是右边图当中的an
注意，它只是计算减1的值
并没有将top自减，top的值是没有变化的
S.top-S.base
这个表达式
实际上是取出栈中元素的个数，也就是栈长
因为，top指向的这个存储单元
它里面的值，并不属于栈的一部分
所以，我们在计算栈长的时候，只用计算top-base，不需要加1了
再下一个表达式，S.top==S.base
如果top和base这两个指针是重合的
我们后面会看到，这时候的栈
实际上是空栈
因为，我们已经约定了，top指向的元素
它并不是属于栈的
所以，top和base重合的时候
a1并不属于栈，这时候，栈是一个空栈。最后一个表达式，S.top-S.base==S.size
那么，由于top减去base
是等于栈中元素个数的
现在，栈中元素个数等于size，说明栈已经满了。这些表达式
我们在后面，都会详细地看到
我们先来看第一个算法实现
初始化
初始化要做的事情，无非就是为栈S分配内存
然后，为它的成员赋以合适的初值
首先
我们用malloc函数，为栈分配一段连续的存储单元
这是初始容量乘上每个元素所占的字节数
强制转换成ElemType类型
以标识这一段连续的存储空间
将来只能存放ElemType类型
然后，把malloc的返回值赋值给base
让base指向栈底
一般在调用完malloc之后
都会有一个if语句
以满足算法的健壮性
如果空间不够
我们直接退出。正常情况下，空间是够的
那我们继续往后执行
将base赋值给top
也就是我们刚才讲的，初始情况下
在初始化一个栈的时候
top和base是重合的
用来表示一个空栈。最后一行语句，将size修改成STACK_INIT_SIZE
这个是用来修改栈的容量的
我们再来看下一个算法，得到栈顶元素，注意，仅仅是得到栈顶元素
把它放到e里面
并不会修改top指针
极端情况下
栈可能为空
所以，算法要先判断一下栈是否为空
另外
要注意一下刚才讲的对top的约定
比如，在图当中，top指向的这个字节或者若干个字节
它里面的值是3
但这个3，并不是栈顶
而是栈顶的下一个位置
这时候的栈顶，实际上是2
首先，我们判断栈是否为空
top和base重合
说明栈是空的
如果不空
我们直接计算top减1，也就是top的上一个位置
然后，用*运算符，取出
它上一个位置
里面的内容，赋值给e
现在，我们来看入栈的算法
将元素e入到栈S当中
如果栈已经满了
我们要追加存储空间
然后，将元素e入栈
并且修改相应的成员
现在，来看算法实现。首先，有一个if语句
它判断top减去
base是否等于size，top减base
刚才我们已经说了，是计算栈中元素个数
如果等于容量size
说明栈已经满了
这时候，我们要调用realloc函数，来为栈重新分配存储空间
它的第一个参数，是旧空间的首地址；第二个参数
是新空间的总字节数
我们为栈追加了STACK_INCREMENT这么多个新的元素所占的空间
由于realloc
可能是在全新的空间上
去分配内存
不一定是在原来的基础之上追加空间
新空间的首地址很有可能发生了变化
所以，我们要将realloc的返回值，重新赋值给base
紧接着的if语句，是空间不足的时候
我们直接退出。正常情况下，我们应该去修改top
因为，这时候，新的top应该是新的base
再加上原来的size，注意
这时候，我们还没有
执行入栈的操作，只是重新划分了空间
要重新修改base和top
然后，再将size自增STACK_INCREMENT
因为，我们这里为栈追加了这么多的空间
这个if语句结束之后，才是正常的入栈操作
入栈
刚才我们已经说过了，top指向栈顶的下一个位置
所以，应该直接将参数e放到top指向的位置
然后，再将top向下加1
在这里
我们合并成了一个表达式，注意
我们采用的是后置的自增
意味着，先将e放到top指向的位置
然后，top再自增1
当然，你也可以把它改成等价的两行语句
比如，先将e赋值到top指向的位置
然后，再去自增top
那么，这两行语句跟这一行语句是等价的
再来看出栈的算法
现在，我们要将栈S当中的栈顶元素，把它弹出到元素e当中，用第二个参数来接收栈顶
极端情况下，栈可能为空
所以，我们首先要判断一下，栈是否为空
然后，去修改top指针
来看算法实现
如果top和base相等
说明栈是空的
没有元素可出栈
这时候，我们直接返回
然后
正常情况下
我们直接将--S.top指向的内容
赋值给e，注意
这里使用了前置的自减
这是因为，还是我们前面的约定，top指向的并不是栈顶
而是栈顶元素的下一个位置
比如，top在这儿的时候
真正的栈顶元素是3
所以，我们先要计算减1
然后，再取内容
把它赋值给e，再将top减1
同样，这个表达式
我们可以写成两行等价的表达式
我们先将top自减
然后
再将top的内容取出来
赋值给e
它等价于
这个表达式
现在我们再来看，栈的链式实现
刚才我们讲了顺序栈
每一种数据结构，实际上，都可以采用顺序或者链式的方式实现
接着
我们来看，栈的链式实现，称为链栈
这个图
实际上并不是内存
刚才，我们已经见到过
它仅仅表示，有一个栈，里面有4个元素
栈顶是a4
现在，我们把它建立成链表
top指向一个头结点
这时候，top指针指向头结点，头结点的后继
指向的是真正的栈顶元素
链表的最后一个结点，实际上是栈底元素
结点的结构
跟前面的单链表，是一模一样的
top指针指向是头结点
注意，不是栈顶元素，是头结点
因为，一般来说，我们都要为单链表增设一个头结点
以方便操作
真正的栈顶元素，实际上是top->next
top->next是这个指针
它指向的是a4
然后，我们取出a4的data成员
就是
栈顶元素本身的值
我们来总结一下
栈这种数据结构
我们会发现，由于栈只能在top端进行插入、删除
导致后入栈的元素总是要先出栈
无论顺序栈，还是链栈
前面的各个算法
它们的时间复杂度都是O(1)
因为，不可能在栈的中间做插入
删除，都是在一端做插入、删除
这时候，无论是链式还是顺序存储
它们的时间复杂度都是O(1)
实际上
计算机的底层
硬件就涉及到栈
比如，在CPU当中
有一个SP寄存器
叫做Stack Pointer
栈顶指针寄存器
它是用来描述栈顶的位置
在CPU当中，还有入栈和出栈的指令
比如，PUSH和POP，对于高级语言
实际上，我们调用一个函数的时候
这个函数调用编译成机器码之后
在这些机器码当中
一定会有一条PUSH指令
它会将当前调用语句的地址，把它压入到栈当中
高级语言当中的return语句
结束被调函数的运行，返回到主调函数
它对应的机器码，会有一条POP指令
从栈当中取出相应的值和地址
我们后面讲栈和递归的时候
会详细讲到
在内存当中
会划分有堆栈段
Stack Segment
如果学习过汇编的同学，对堆栈段应该有所了解
栈是一种应用非常广泛的数据结构
接下来，我们就来看几个栈的应用例子
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
