一.栈的定义
1.栈的定义
栈(stack)是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一段称为栈顶(top),另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表。
进一步理解栈，栈首先他是一个线性表，所以栈元素具有前驱后继关系。
栈的插入操作，叫做出栈，也叫压栈、入栈。栈的删除操作，叫做出栈，也叫弹栈。
2.进栈出栈变化形式
在进一步了解数据进栈和出栈后，有个问题----最先进栈的元素，是不是就只能是最后出栈呢。
其实不然，举例子来说现在有3个整形数字元素1、2、3依次进栈，会有那些序列呢？
第一种:1、2、3进，再3、2、1出。这是最简单最好理解的一种，出栈次序为3、2、1。
第二种:1进，1出，2进，2出，3进，3出。也就是进一个就出一个，出栈次序为1、2、3。
第三种:1进，2进，2出，1出，3进，3出。出栈次序为2、1、3。
第四种:1进，1出，2进，3进，3出，2出。出栈次序为1、3、2。
第五种:1进，2进，2出，3 进，3出，1出。出栈次序为2、3、1。
有没有可能是3、1、2这样的次序出栈呢?答案是肯定不会。因为3先出栈，就意味着，3曾经进栈，既然3都进栈了，那也就意味着，1和2已经进栈了，此时，2一定是在1的上面，就是更接近栈顶，那么出栈只可能是3、2、1，不然不满足1、2、3依次进栈的要求，所以此时不会发生1比2先出栈的情况。
从这个简单的例子就能看出，只是3个元素，就有5种可能的出栈次序如果元素数这个知识点一定要弄明白。
二.栈的抽象数据类型
对于栈来说，理论上线性表的操作特性他都具备，下面我们来看一下几个需要实现的功能；
typedef int STDataType;
typedef int STDataType;
void InitST(ST* s);//初始化栈
void DestroyST(ST* s);//销毁栈
void Push(ST* s, int x);//压栈
void Pop(ST* s);//出栈
bool STEmpty(ST* s);//判断栈是否为空栈
STDataType STSize(ST* s);//当前栈的元素个数
STDataType STTop(ST* s);//返回栈顶元素
三.栈的顺序储存结构及实现
1.栈的顺序存储结构
栈既然是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。
typedef int STDataType;
typedef struct stack
{
STDataType* a;
STDataType top;//表示当前指向的元素下标
STDataType capacity;//栈的当前容量
}ST;
(1).初始化栈
在初始化栈是指针a需要malloc个初始空间，容量则根据malloc的个数赋值。而top对的初值则有所不同，top的初值有两种情况 一是top代表下一个元素的下标，二是代表当前元素的下标，两种不同的初值，也会影响后面操作的差别。
void InitST(ST* s)
{
assert(s);
s->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (s->a == NULL)
{
perror("malloc fail");
return;
}
s->capacity = 4;
s->top = -1;///top记录指向的当前元素
}
(2).销毁栈
销毁栈则非常简单:
void DestroyST(ST* s)
{
assert(s);
s->capacity = 0;
free(s->a);
s->a = NULL;
s->top = -1;
}
(3).进栈操作
进栈操作也比前面的顺序表链表的插入操作更为简单:文章来源：https://www.toymoban.com/news/detail-404491.html
void Push(ST* s,int x)
{
assert(s);
if (s->top+1 == s->capacity)
{
s->a = (STDataType*)realloc(s->a,sizeof(STDataType)*s->capacity*2);
if (s->a == NULL)
{
perror("malloc fail");
return;
}
s->capacity *= 2;
}
s->a[s->top+1] = x;
s->top++;
}
(4).出栈操作
出栈操作同样简单，知识需要提前检查当前是否为空栈即可：文章来源地址https://www.toymoban.com/news/detail-404491.html
void Pop(ST* s)
{
assert(s);
assert(!STEmpty(s));
s->top--;
}
bool STEmpty(ST* s)
{
assert(s);
if (s->top == -1)
return true;
return false;
}
(5).栈的元素个数和栈顶元素
STDataType STSize(ST* s)
{
assert(s);
return s->top + 1;
}
STDataType STTop(ST* s)
{
assert(s);
return s->a[s->top];
}
到了这里，关于【数据结构与算法】栈的讲解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
