数据结构与算法（六）——栈结构
一、限定性数据结构——栈与队列
栈和队列属于逻辑结构中的线性结构，也就是说，栈和队列在本质上就是属于线性表。但是栈和队列与一般的线性表相比，其特殊性就在于它们在元素读取的基本操作上面是不一样的：
一般的线性表是可以读取和操作任意位置上的元素的；
栈的特点是先进后出，只能将新元素插入到表尾，也只可以读取到表尾的那个元素；
队列的特点是先进先出，只能将新元素插入到表尾，只可以读取到表头的那个元素。
也正是因为栈和队列有上述这些限定性条件，因此，我们说，栈和队列属于线性结构中的限定性结构。
二、顺序栈
顺序栈指的是利用顺序存储来实现的栈的结构。所有的顺序存储都是在内存中开辟一段连续的存储空间，顺序栈就是在这段连续的内存空间中依次进行栈底、…、栈顶的元素存储。
如上图所示，这是一个空间容量为5的顺序栈的三种状态。top是一个指针，它指向了当前的栈顶，在顺序栈中，我们可以直接使用位置下标来表示top。
- 最左边的是，栈中有两个元素的时候的顺序栈，此时top=1。
- 中间的是，栈中没有元素（即栈为空）时候的顺序栈，此时top=-1。我们这里是使用top==-1来表示一个栈是空栈，在内存中是没有-1这个位置的，这里的-1只是一个标记，它标记着该栈是一个空栈。
- 最右边的是，满栈的时候的顺序栈，此时top=4。
栈的定义如下：
#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>
#define StackSize 10 // 栈的容量
// 栈操作的状态
typedef enum : int {
Success,
Error,
} Status;
// 栈中元素的类型
typedef int ElementType;
// 栈的结构
typedef struct Stack {
ElementType datas[StackSize]; // 栈的存储空间
int top; // 栈顶指针
} Stack;注意，在设计一个栈结构的时候，需要考虑三个要素：栈顶指针、当前栈的长度、栈的数据域。在上述顺序栈的结构中，栈顶指针top就能够包含栈的长度的作用了。
接下来看一下如何构建一个空栈：
// 1，构建一个空栈
Status initStack(Stack *stack) {
stack->top = -1;
return Success;
}可以看到，这里只是将栈的栈顶指针指向-1，并没有进行开辟内存空间的操作，这是为啥呢？这是因为在Stack结构体的创建的时候，就已经将数组datas的内存空间开辟出来了。
接下来看一下如何将栈置空：
// 2，将栈置空
/*
这里需要注意的是，在清空栈的时候是不需要将栈中的元素也给清空的，只需要将栈顶指针置空即可。
*/
Status clearStack(Stack *stack) {
stack->top = -1;
return Success;
}可以看到，将栈置空的时候只需要将栈顶指针指向-1即可，并不需要将栈的内存空间也给清空。因为栈的内存空间是一开始就开辟好的，它会一直存在，我们后面再压栈的时候，直接将该位置原来的值给覆盖掉就可以了~
接下来看一下如何对栈进行判空，以及如何获取栈的长度：
// 3，判断栈是否为空
bool isStackEmpty(Stack stack) {
return stack.top == -1;
}
// 4，获取栈的长度
int stackLength(Stack stack) {
return stack.top + 1;
}
我们这里是将栈顶指针指向-1作为判定栈是否为空的一个标识，你也可以将栈顶指针指向-2或者-3或者其他的值作为判定栈是否为空的标识，这要根据你自己的喜好，但是一般而言，我们都是通过-1来判空。
当栈为空的时候将栈顶指针指向-1还有一个好处就是，这样就可以直接通过栈顶指针的值来获取栈的长度了。栈顶指针为-1的时候，栈为空，栈的长度就是-1+1=0。
获取栈顶、入栈、出栈、栈的打印如下：
// 5，获取栈顶
Status getTop(Stack stack, ElementType *topElement) {
if (stack.top == -1) {
return Error;
}
*topElement = stack.datas[stack.top];
return Success;
}
// 6，压栈（入栈）
Status push(Stack *stack, ElementType element) {
// 如果已经满栈，则直接报错
if (stack->top >= StackSize - 1) {
return Error;
}
// 如果栈中还有空间，则入栈
stack->datas[++stack->top] = element;
return Success;
}
// 7，出栈
Status pop(Stack *stack, ElementType *element) {
// 如果已经是空栈了，那么就报错
if (stack->top == -1) {
return Error;
}
// 如果栈中还有元素，则执行出栈操作，并将出栈的元素记录下来
*element = stack->datas[stack->top--];
return Success;
}
// 8，打印栈
Status printStack(Stack stack) {
if (stack.top == -1) {
printf("栈为空\n");
return Error;
}
printf("当前栈中元素如下:\n");
for (int i = 0; i <= stack.top; i++) {
printf("%d\n", stack.datas[i]);
}
return Success;
}三、链式栈
链式栈指的是利用链式存储来实现的栈的结构。
链式栈和顺序栈的逻辑都一模一样的，只是他们的物理存储方式不一样。
首先来看一下链式栈的结构：
#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>
// 操作的状态
typedef enum : int {
Success,
Error,
} Status;
// 值的类型
typedef int ElementType;
// 节点类型
typedef struct Node {
ElementType data; // 数据域
struct Node *next; // 指针域
} Node;
// 链式栈的结构
typedef struct Stack {
struct Node *top; // 栈顶指针
int length; // 栈的长度
} Stack;我上面提到，设计一个栈结构，需要考虑三个要素：栈的长度、栈顶指针和栈的元素内容。
在顺序栈中，top指针可以将栈的长度和栈顶指针这两项要素给覆盖，因此在顺序栈的结构中只需要一个top指针和一个datas数组即可。
在链式栈结构中，通过top指针指向栈顶节点，然后通过各个节点的next就可以依次获取到每一个节点，所以top指针是可以将栈的元素内容和栈顶指针这两项要素给覆盖的，因此在链式栈的结构中只需要一个top指针和一个栈的长度变量即可。
创建一个空栈的代码如下：
// 1，创建一个空栈
Status initStack(Stack *stack) {
stack->length = 0;
stack->top = NULL;
return Success;
}将链式栈置空的代码如下：
// 2，将栈置空
/*
将顺序栈置空的时候，只需要将栈顶指针指向-1即可，不需要进行内存空间的释放，因为顺序栈的内存在创建的时候就开辟好了，所以在清空栈（并非销毁栈）的时候无需处理内存。
而将链式栈置空的时候，不但要更改长度、更改栈顶指针的指向，还要将原来的各个元素给一一销毁。
*/
Status clearStack(Stack *stack) {
// 释放栈中各节点
struct Node *top = stack->top;
struct Node *tempNode;
while (top) {
tempNode = top;
top = top->next;
free(tempNode);
}
stack->top = NULL;
stack->length = 0;
return Success;
}将顺序栈置空的时候，只需要将栈顶指针指向-1即可，不需要进行内存空间的释放，因为顺序栈的内存在创建的时候就开辟好了，所以在清空栈（并非销毁栈）的时候无需处理内存。
而将链式栈置空的时候，不但要更改长度、更改栈顶指针的指向，还要将原来的各个元素给一一销毁。
获取栈的长度、栈的判空的代码如下：
// 3，栈的判空
bool isStackEmpty(Stack stack) {
return stack.top == NULL && stack.length == 0;
}
// 4，栈的长度
int stackLength(Stack stack) {
return stack.length;
}获取栈顶元素的代码如下：
// 5，获取栈顶元素
Status getTopElement(Stack stack, ElementType *topElement) {
if (stack.top == NULL) {
return Error;
}
*topElement = stack.top->data;
return Success;
}压栈代码如下：
// 6，压栈
Status push(Stack *stack, ElementType element) {
// 如果栈不存在，则报错
if (!stack) {
return Error;
}
// 新建节点，并将其设置为栈顶节点
struct Node *node = malloc(sizeof(Node));
node->data = element;
node->next = stack->top;
stack->top = node;
// count加1
stack->length++;
return Success;
}在顺序栈中，压栈的时候需要判断是否栈满；在链式栈中，是不需要在压栈的时候判断是否栈满的。
接下来看出栈代码：
// 7，出栈
Status pop(Stack *stack, ElementType *popElement) {
// 如果栈不存在，则报错
if (!stack) {
return Error;
}
// 如果是空栈，则直接返回
if (stack->top == NULL) {
return Success;
}
// 栈顶指针下移一位
struct Node *tempNode = stack->top;
stack->top = tempNode->next;
*popElement = tempNode->data; // 记录出栈的元素
free(tempNode);
// 栈的长度减1
stack->length--;
return Success;
}链式栈的出栈跟顺序栈的出栈一样，都需要首先判断一下该栈是否为空，只有非空的时候才可以出栈。
栈的遍历打印如下：
// 8，打印栈
Status printStack(Stack stack) {
struct Node *top = stack.top;
if (!top) {
printf("该链栈为空\n");
return Success;
}
printf("该链栈的信息如下：\n");
while (top) {
printf("%d\n", top->data);
top = top->next;
}
return Success;
}四、栈与递归的关系
1，递归和迭代的区别
递归，recursion，简而言之就是，应用程序调用自身。在使用递归算法的时候，必须要有明确的结束条件，即递归出口。
迭代，又称为循环迭代，就是我们理解的常规意义上的循环算法。
2，什么情况下需要使用递归来解决问题
（1）定义是递归的
阶乘、斐波那契数列这些问题在数学定义上是递归的，此时就需要用递归去解决。
接下来我们来分析一下阶乘和斐波那契数列：
// Fact(n)
(1) n=0, 1;
(2) n > 1, n*Fact(n-1);
// Fib(n)
(1) n=1 n=2, 1;
(2) n > 2, Fib(n-1) + Fib(n-2); 代码如下：
long Fact(Long n){
if(n=0)
return -1;
else
return n * Fact(n-1);
}
long Fib(Long n){
if(n == 1 || n == 2)
return 1;
else
return Fib(n-1)+Fib(n-2);
}（2）数据结构是递归的
比如链表结构，每一个节点都是由数据域和指针域两部分构成，而指针域又指向了另外一个节点，也就是说，在链表节点的定义当中是用到了其自身的，因此，链表这种结构就是一种递归结构，在打印的时候就可以使用递归算法。
如下：
void TraverseList(LinkList p){
if(p == NULL) // 递归终止条件
return;
else {
// 输出当前节点的数据域
printf("%d",p->data);
// p指向后继节点继续递归
TraverseList(p->next);
}
}以上可以简化为：
void TraverseList(LinkList p) {
if(p) {
printf("%d",p->data);
TraverseList(p->next);
}
}（3）问题的解法是递归的
有一类问题，虽然问题本身并没有明显的递归结构，但是采用递归求解比迭代求解会更简单，比如汉罗塔问题。八皇后问题、迷宫问题等。
3，分治法
我们知道，任何的递归，都是可以写成循环迭代的，因此我们可以将递归理解成是一种特殊的迭代。也就是说，部分循环迭代其实是可以写成递归的。那么，如何将循环迭代改写成递归呢？此时就可以采用分治法。分治法其实就是分析解决递归问题的一种技术。
要使用分治法，需要满足三个条件：
（1）所有的大问题都可以拆解成小问题，并且大问题与小问题的解法是高度雷同的。
比如斐波那契数列、阶乘、汉罗塔问题等，都可以将大的问题拆解成小的问题，并且它们的解法相同或类似。
（2）通过上述转化可以使问题得以简化。
如果通过上述转化，之后并没有使得问题得以简化，甚至更加复杂了，那么就不要使用分治法。
（3）必须要有一个明确的递归出口。
4，递归工作栈
一个递归函数，在函数的执行过程中，是需要多次循环调用的。接下来我们就思考一下，一个递归函数是如何执行的呢？
在了解一个递归函数是如何执行的之前，我们先来了解一下任意两个函数之间的调用是如何进行的。
在高级语言的程序中，调用函数和被调用函数之间的链接与信息交换都是通过栈来进行的。
通常而言，当在一个函数的运行期间去调用另一个函数的时候，在运行被调用函数之前，系统需要先完成三件事情:
（1）将被调用函数中使用到的实参、被调用函数返回地址信息这两项内容，传递到被调用函数中进行保存；
（2）为被调用函数中的局部变量分配存储空间
（3）将计算机的底层控制转移到被调用函数的入口处
而从被调用函数返回到调用函数之前，系统同样需要完成三件事情：
（1）保存被调用函数的计算结果
（2）释放被调用函数的数据区
（3）依照被调用函数中保存的返回地址，将系统的底层控制转移到上一层的调用函数中
当多个函数构成嵌套调用的时候，按照“先调用后返回”的原则，上述函数之间的信息传递和控制转移必须通过“栈”来实现。也就是说，系统会将整个程序运行时所需要的数据空间都安排在一个栈中，每当调用一个函数时，就在它的栈顶分配一个存储区；每当这个函数退出的时候，就释放它的存储区。而当前正在运行的函数的数据区肯定是在栈顶。
来看下面这段代码：
int second(int d){
int x,y;
//...
}
int first(int s ,int t){
int i;
//...
second(i);//2.⼊栈
//...
}
void main( ){
int m,n;
first(m ,n);//1.入栈
//...
}在这段代码中，首先，在主函数main中，调用first函数；而在first函数中，又调用了second函数。
当执行first函数的时候，栈空间里保存的信息如下：
当执行second函数的时候，栈空间里保存的信息如下：
一个递归函数的运行过程，与上面👆讲的这个多函数的嵌套调用过程是很类似的，而二者不同的点在于，递归函数的调用函数和被调用函数都是同一个函数。
正因为递归函数的调用函数和被调用函数是同一个函数，因此，和每一次函数调用相关的一个重要概念就是，递归函数运行的“层次”：
假设调用该递归函数的主函数在第0层，则从主函数调用递归函数进入第1层，从第1层递归函数调用自身，就会进入到第2层，……，从第i层递归函数调用自身，就会进入到第i+1层；而退出第i层递归时，应该返回到上一层，即第i-1层。
为了保证递归函数的正确执行，我们系统会设立一个“递归工作栈”，这个“递归工作栈”就是整个递归函数在运行期间所使用到的数据存储区。每一层递归所需要的信息都会构成一个工作记录，其中包括所有的实参、所有的局部变量、以及上一层的返回地址。每进入一层递归，都会产生一个新的工作记录压入栈顶；每退出一个递归，都会从栈顶弹出一个工作记录。当前执行层的工作记录，必须是处于递归工作栈栈顶的工作记录，我们称之为“活动记录”。
以上。