【数据结构】栈的实现

💯💯💯

©Ⅰ.栈的概念及结构

栈：是一种特殊的线性表，其只允许在固定的一端进行插入与删除操作。
进行数据的插入和删除的一端称为栈顶，另一端称为栈底。
栈遵循先进后出，后进先出的原则。

压栈：栈的插入操作叫做压栈/入栈/进栈，在栈顶实现
出栈：栈的删除操作叫做出栈。也在栈顶实现。

入栈
出栈

©Ⅱ.栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小。

//下面是定长的静态栈的结构，实际中一般不用，因为不能扩大容量，所以我们主要实现下面的支持动态增长的栈
#define N 10
typedef int STData;
struct stack1
{int arr[N];//静态数组int top;//栈顶
}ST;//支持动态增长的栈结构
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int STData;//重定义栈使用的数据，如果栈使用的数据不是int类型那么可以通过修改这里从而修改栈的使用数据类型
typedef struct Stack
{int* a;//指向一个数组的指针int top;//栈顶int capicty;//数组容量
}ST;//重命名为ST
//初始化栈表
void STInit(ST*ps);
//销毁栈表
void STDestroy(ST* ps);
//压栈，在栈顶压入一个元素
void STpush(ST* ps,STData x);
//出栈，在栈顶弹出一个元素。
void STpop(ST* ps);
//访问栈顶元素
//获取栈有效数据的大小
int STSize(ST* ps);
STData STTop(ST* ps);
//检查栈是否为空，如果为空返回值为非0，如果是假则返回0；
int STSize(ST* ps);

2.1栈的初始化

因为该数组是动态数组，可以增容，一开始我们可以给数组一定的容量，当数组元素个数等于容量时再进行扩容即可。

不过要注意的是top值应该初始化为几呢？
如果初始化为0，那a[top]表示的是有元素还是没有元素呢？
如果初始化为0的化，那top就表示指向栈顶元素下一个位置的地方。

而如果初始化为-1，那才表示的是栈顶元素的位置。一开始没有元素，top为-1，当有元素压栈进来后，top++，变成0，a[top]上就存在元素了。
两中表示方法都可以，但 要注意表示一种就要一种按照该逻辑进行。

void STInit(ST* ps)//初始化栈表
{assert(ps);//判断结构体指针不为NULL；//一上来可以给栈表初始化容量ps->a = (STData*)malloc(sizeof(STData) * 4);if (ps->a == NULL)//判断是否开辟成功{perror("malloc");}//初始话容量为4ps->capicty = 4;ps->top = 0;//top=0 表示的是指向栈顶元素的下一个位置//top如果为-1，则表示栈顶元素的位置
}

2.2压栈

在元素入栈之前我们需要考虑是否栈空间已满，而需要进行扩容。
所以一开始我们就需要将扩容操作写下。
每次扩容两倍。容量的大小随之改变。
还要注意的是，当入栈后，top是要进行++，然后top就是指向栈顶元素下一个位置的地方了。

void STpush(ST* ps, STData x)//压栈，在栈顶压入一个元素--在压入之前也要考虑是否需要增容
{assert(ps);//断言判断if (ps->top == ps->capicty)//当数组元素等于容量时{//增容STData* tmp = (STData*)realloc(ps->a, sizeof(STData) * ps->capicty * 2);if (tmp == NULL){perror("realloc");}ps->a = tmp;//将扩容的空间赋给aps->capicty *= 2;//数组的容量也随之变大}ps->a[ps->top] = x;//将元素压入栈顶，一开始top是0，当元素进去后，再让top指向该栈顶元素后一个位置ps->top++;
}

2.3出栈

在删除数据之前我们需要考虑栈空间里还有没有数据可以删除，当栈空间里没有数据可删，那就立刻停止。

所以我们首先需要对栈进行检查是否为空。
当栈为空时返回非0，不为空时返回0；

int STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

而删除数据的操作我们只要让top–即可，不需要释放空间。

void STpop(ST* ps)//出栈，在栈顶弹出一个元素。
{assert(ps);//删除元素之前要检查栈表是否还有元素可删assert(!STEmpty(ps));//当栈表为NULL是断言ps->top--;}

2.4获取栈顶元素

获取栈顶元素也就是top所指向的元素，但要注意每次压入一个数据后top都会++，所以最后top是多加了一次，要想访问最后一个元素也就是栈顶元素需要top-1；

STData STTop(ST* ps)//访问栈顶元素
{assert(ps);//断言判断return ps->a[ps->top - 1];//top-1的位置才是栈顶元素
}

2.5获取栈中有效元素的个数

其实top的数值大小就是栈中有效元素的个数，
一开始top为0，表中没有元素，当有元素时，top就进行++，有一个加一次，有一个加一次，所以最后栈中有效元素的个数就是top的数值

int STSize(ST* ps)//计算栈表长度
{assert(ps);//断言判断return ps->top;//top的长度就是栈表的长度
}

2.6销毁栈

将栈销毁掉也就是让数据都归还操作系统。
开辟的空间需要释放，定义的变量需要置0；

void STDestroy(ST* ps)//销毁栈表
{assert(ps);//断言判断free(ps->a);//释放数值空间ps->a = NULL;//并手动置NULLps->capicty = 0;//置0ps->top = 0;}

2.7栈的"打印"

栈是不能进行打印的，因为栈要求数据后入的要先出，而打印的顺序是先入先出。
想要让栈的数据展现出来，那就要按照它的特点，我们先打印栈顶元素，打印完再将栈顶元素出栈，再打印新的栈顶元素，再出栈，知道栈变成空为止。

void test()
{ST p;STInit(&p);STpush(&p, 1);STpush(&p, 2);STpush(&p, 3);STpush(&p, 4);STpush(&p, 5);printf("%d\n", STSize(&p));//获得栈中有效元素的个数while (!STEmpty(&p)){printf("%d ", STTop(&p));//将栈的数据展现出现，要求先进后出，后进先出STpop(&p);}STDestroy(&p);
}