【初阶数据结构】栈
栈的概念及结构
栈：是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素的操作。
栈顶：进行数据插入和删除操作的那一端。
栈底：栈顶的另一端就是栈底。
压栈：栈的插入数据操作就叫压栈，也称进栈，入栈，入数据在栈顶。
出栈：栈的删除数据操作叫做出栈，出数据也在栈顶。
栈不能随机访问，只能在栈顶出入数据或访问数据。
栈数据元素遵守后进先出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 = realloc(pst->a, newcapacity * sizeof(STDataType));
if (tmp == 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;
}
今天的内容到此结束啦，感谢大家观看，如果大家喜欢，希望大家一键三连支持一下，如有表述不正确，也欢迎大家批评指正。
原文地址：https://blog.csdn.net/2301_77112794/article/details/138565023
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！