【初阶数据结构】栈

栈的概念及结构

栈：是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素的操作。
栈顶：进行数据插入和删除操作的那一端。
栈底：栈顶的另一端就是栈底。
压栈：栈的插入数据操作就叫压栈，也称进栈，入栈，入数据在栈顶。
出栈：栈的删除数据操作叫做出栈，出数据也在栈顶。
栈不能随机访问，只能在栈顶出入数据或访问数据。
栈数据元素遵守后进先出LIFO(Last In First Out)的原则。
在这里插入图片描述

栈的实现

栈同样有两种存储方式，一种是链式存储，叫做链栈，一种是顺序存储，叫做顺序栈，一般情况下，用顺序栈的方式比较多。是因为用顺序表来实现对栈的操作，一方面顺序表的扩容不会像链表一样要一个个节点去malloc那么频繁，内存空间也比较大，人们也不会特别在意空间浪费的问题，并且利用顺序表尾插尾删数据的代价比链表更小；另一方面顺序表的缓存利用率高，所以我们更倾向使用顺序栈。

栈的结构

顺序表分为了静态顺序表和动态顺序表，但是为了方便扩容，一般都采用动态顺序表，同样的，顺序栈也分为了定长的静态栈和支持动态增长的栈，我们也主要来实现动态增长的栈。
动态增长栈的结构如下：

typedef int STDataType;
typedef struct Stack
{STDataType* a;//顺序栈，即用数组实现，a指向栈底int top;int capacity;
}ST;

这里有一个问题需要注意：
我们定义的top是什么，指向哪里，应该初始化为什么
这是有两种情况：
情况一：
top指向栈顶的那个元素：

由上图可知，当top指向栈顶元素时，它初始化应该为-1，而不是0，因为这样才能使得栈中有一个元素的时候，top等于0且指向那一个元素。
情况二：
top指向栈顶的下一个元素：

如上图，当top指向栈顶的下一个元素时，它的初始化就为0，即top可看做栈中有效元素个数。

栈的初始化

上面我们已经说了top的两种情况，这也对应着top的两种初始化，但其实两种初始化都是正确的，看你选择哪一种，这里我们选择第二种，top为0时栈空，相当于顺序表的size。
初始化如下：

void STInit(ST* pst)//传址调用，才能修改形参中的值，用指针接收，不再多说
{assert(pst);//传参的指针不能为空pst->a = NULL;//可以先初始化为空，后面插入数据时在添加空间pst->top = 0;pst->capacity = 0;
}

栈的销毁

void STDestory(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}

入栈

顺序栈只能在栈顶插入数据，其实也就等于顺序表的尾插，我们已经很清楚了，不清楚的可以再回去看看这个内容：顺序表。
代码实现：

void STPush(ST* pst, STDataType x)
{assert(pst);if(pst->top == pst->capacity)//空间不够，要扩容{int newcapacity = pst->capacity == 0 ? 4 :2 * capacity;STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));if (new == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}

出栈

同样的，出栈相当于顺序表的尾删，代码如下：

void STPop(ST* pst)
{assert(pst);assert(pst->top);//栈不能为空，为空则报错pst->top--;
}

取栈顶元素

取栈顶元素也就等于读取数组中最后一个元素的值，要注意的是，下标是top还是top-1，由于我们定义的top是指向栈顶的下一个元素，所以下标应该为top-1.

STDataType STTop(ST* pst)
{assert(pst);assert(pst->top);return pst->a[pst->top-1];
}

判断栈是否为空

判断栈是否为空，如果为空，则返回true，不为空，则返回false，此时我们用bool类型的函数去定义。我们上面在判断top的初始化时已经提到，当top == 0，则栈为空，代码如下：

bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}

取栈中元素个数

上面说到，当我们初始化top = 0时，top就相当于size，即元素个数，只要返回top即可。

int STSize(ST* pst)
{assert(pst);return pst->top;
}

代码测试

至此，栈的有关操作就结束了，最后也不要忘了调试所写代码是否正确。这里要注意的是，在打印栈的时候，我们不能像顺序表或者链表一样写一个打印函数出来，因为链表是后进先出的，当我们需要打印这个栈时，需要一个个出栈然后打印，代码如下：

while (!STEmpty(&s))//判断栈是否为空
{printf("%d ", STTop(&s));//先读取栈顶元素STPop(&s);//后取出栈顶元素
}

测试代码如下：
在这里插入图片描述

当然，栈也不仅仅只能打印这一种，可以有很多种情况，具体要看是如何出栈和入栈的。

比如说有三个数字1，2，3，进行出栈出栈操作
则三个数既可以先全部入栈再出栈，也可以边入栈边出栈，
则这三个数出栈后全部的可能序列为：
{3,2,1}、{2,3,1}、{2,1,3}、{1,2,3}、{1,3,2}

完整代码

Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//初始化和销毁
void STInit(ST* pst);
void STDestory(ST* pst);//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);//取栈顶元素
STDataType STTop(ST* pst);//判断栈是否为空
bool STEmpty(ST* pst);//获取元素个数
int STSize(ST* pst);

Stack.c

#include"Stack.h"//初始化
void STInit(ST* pst)
{pst->a = NULL;pst->capacity = 0;pst->top = 0;
}//销毁
void STDestory(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}//入栈
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* new = (STDataType*)realloc(pst->a, newcapacity*sizeof(STDataType));if (new == NULL){perror("realloc fail");return;}pst->a = new;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top);pst->top--;
}//取栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top);return pst->a[pst->top - 1];
}//判断栈是否为空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}//获取元素个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}

test.c

#include"Stack.h"void test()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);printf("栈中元素个数为：%d\n", STSize(&s));STPop(&s);STPop(&s);printf("取出栈顶元素：%d\n", STTop(&s));printf("栈中元素个数为：%d\n", STSize(&s));printf("打印栈中元素：");while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}STDestory(&s);
}int main()
{test();return 0;
}