数据结构（5）线性表-栈

一、栈的概述

栈是一种特殊的线性表，特殊性体现在，它只允许在固定的一段进行插入和删除操作。

可以进行插入和删除操作的一段叫做栈顶，另一端叫做栈底。

如图：

所以栈的数据一般符合“先进后出”或“后进先出”的特点，因为只有栈顶可以进行数据的改写。

栈既然是线性表，逻辑结构上就是线性的，但是物理结构上不一定是线性的，如果底层用数组来实现，那么就是线性的，但是如果用链表来实现的话，那么就又不好说了。

二、栈的相关操作

1.栈的结构

既然底层既可以以数组来实现，又可以用链表来实现，在这里我们就用数组来实现：

栈需要什么属性呢？

如果底层是数组的话，我们先要分清栈顶和栈底，根据我们实现顺序表的经验来看，数组的尾部来做栈顶更合适，因为数组尾部的插入和删除操作更加快捷，时间复杂度均为O（1）。

这样的话就需要一个指针，记录这块地址。

类比顺序表的话，有效数据元素需要size，内存空间大小为capacity。

但是为了区分，我们将有效数据元素用top存储，因为：

没有元素时栈顶和栈底相等，有效元素为0。

而后续的存取等操作，均在栈顶，也就是top位置进行：

所以栈的结构为：

2.栈的初始化

基本不用多说：

测试代码：

3.入栈

栈只有固定的一段可以进行插入删除操作，插入操作一般叫做压栈/进栈/入栈。

我们以数组为底层内存空间，那么就是尾端的插入，当然，在插入之前检测并分配内存空间。

测试代码：

4.出栈

出栈首先栈不能为空：

然后再进行出栈：

测试代码：

assert和正常逻辑均没错。

5.取栈顶元素

测试代码：

验证了后入先出。

6.取栈有效元素个数

测试代码：

7.栈的销毁

测试代码：

栈的实际意义等到具体的题中去体会。