Day27-【13003】短文，什么是栈？栈为何用在递归调用中？顺序栈和链式栈是什么？

文章目录

第三章栈和队列总览
- 第一节栈概览
- - 栈的定义及其基本操作
  - 如何定义栈和栈的操作？合理的出栈序列个数如何计算？
  - 栈的两种存储方式及其实现？
  - - - 顺序栈及其实现，还有对应时间复杂度
      - *、清空栈，初始化栈
        5、栈空，6、栈满
        1、入栈，2、出栈
        7、获取栈顶元素
      - 链式栈及其实现，还有对应时间复杂度
      - *、初始化栈
        2、出栈
        *清空栈
        1、入栈
        5、栈空
  - 顺序栈和链式栈的比较
  - 函数调用中的递归调用，为什么最适合采用栈来保存信息？

第三章栈和队列总览

在这里插入图片描述

第一节栈概览

在这里插入图片描述

栈的定义及其基本操作

栈是一种特殊的线性表，

它的特殊性体现在操作的位置上。

在含n个元素的线性表中进行插入或删除时，操作位詈可以有n+1 个或n个。

n+1是因为带头节点的单链表是不是
当将操作位詈限定在线注表的同一端时，得到的数据结构就是栈。

它是— 种受限的线性表。

定义3-1 栈是限定仅在一端进行插入和删除的线性表。

能进行插入和删除的一端称为栈顶，

在栈顶插入一个元素称为入栈，也称为进栈或压栈；

从栈顶删除一个元素称为出栈，也称为退栈。

另一端称为栈底。

栈中最多能保存的元素个数称为栈的容量；

怎么和用顺序方式，也就是数组存储的线性表有点像呢，还有容量

确实如此，顺序栈，就是用数组来存储的，所以数组大小，就是栈的容量

可以沿用线性表的表示方法，将栈S表示为：
$(a_0, a_1, \cdots, a_{n - 1})\\ 在这个表示中，将哪— 端规定为栈顶都是可以的，\\ 通常指定an_1一端为栈顶\\ a_0一端是栈底。因为是a_0先进入，先开始，肯定是栈底了\\ 栈中元素个数 n 称为栈的长度\\ 当n=0时，称为空栈\\$

栈及入栈和出栈操作的示意图如图3-1所示

入栈橾作及出栈橾作只能在栈顶进行，实际上，只能看到栈顶元素，栈顶之下的所有元素都是不可见的，

即不允许访问非栈顶元素。

在这里插入图片描述

如何定义栈和栈的操作？合理的出栈序列个数如何计算？

栈中每个元素的类型都是ELEMType，定义如下。

typedef int ELEMType ;

栈的抽象数据类型为Stack，为简单起见，仅列出栈的基本操作如下：

int initStack(Stack * mys);// 初始化栈, 创建一个空栈mys
int clear(Stack * mys);// *、将栈mys清空
int pop(Stack * mys, ELEMTType * x);// 2、将栈顶元素出栈
int push(Stack * mys, ELEMTType x);// 1、将元素x入栈
int gettop(SeqStack * mys, ELEMTType * x);// 7、获取栈顶元素 (不出栈)
int isEmpty(Stack * mys);// 5、如果栈mys为空, 则返回1, 否则返回0
int isFull(Stack * mys);// 6、如果栈mys为满, 则返回1, 否则返回0

设有栈S，元素a0，a.，…，an-1依次入栈，然后依次出。

入时，首先a0入栈，然后a1入栈……最后an-1入栈。

出栈时，首先an-1出栈，然后an-2出栈……最后a0出栈。

得到的出栈次序刚好与入栈次序相反，最先入栈的元素最后出栈。

所以栈具有后进先出的特性。

对于栈，给定了入栈序列，是不是只能得到唯一的出栈序列?

一般来说，只要栈不空，就允许出栈;

只要栈不满，就允许入栈。

当没有其他的特殊限制时，对于同一个入栈序列，可能会得到很多个正确合理的出栈序列。

从另一方面来说，对于含n (n≥3) 个元素的入栈序列，它的**全排列共有n!**个。
这些序列不全是合理的出栈序列，实际上，合理的出栈序列个数为

$（3-1）：\\ \\ C_n = \frac{C_{2n}^n}{n + 1}$

栈的两种存储方式及其实现？

和线性表一样，栈也有两种主要的存储方式，分别是顺序存储和链式存储。

顺序存储方式使用数组保存栈元素，得到的是顺序栈。

链式存储方式使用单链表保存栈元素，得到的是链式栈。

注意，是单链表，而不是什么双，循环之类的，应该会带头节点

顺序栈及其实现，还有对应时间复杂度

在顺序栈中，栈中的元素保存在一维数组中，为方便起见，将栈底定义在数组下标为0的位置。

同时还需要一个变量来标记栈顶的位置，即栈顶位置。

习惯上，栈顶位置也称为栈顶指针，

不过它只是数组中的一个下标，并不是真正意义上的一个指针。

顺序栈的定义如下

typedef int ELEMTType;  		 //以int类型为例
typedef struct {ELEMTType element[maxSize];  //maxSize是数组最大容量, 已定义的常量int top;  					 //栈顶位置
} SeqStack;  					 //顺序栈

顺序栈的基本操作如下。

int initStack(SeqStack * mys);// 初始化栈
int clear(SeqStack * mys);// *、将栈mys清空
int pop(SeqStack * mys, ELEMTType * x);// 2、将栈顶元素出栈
int push(SeqStack * mys, ELEMTType x);// 1、将元素x入栈
int gettop(SeqStack * mys, ELEMTType * x);// 7、获取栈顶元素 (不出栈)
int isEmpty(SeqStack * mys);// 5、如果栈mys为空, 则返回1, 否则返回0
int isFull(SeqStack * mys);// 6、如果栈mys为满, 则返回1, 否则返回0