目录

大家好，今天为大家带来C语言初阶数据结构中关于栈的相关知识

1.栈的实现方法

2.栈的具体实现(用数组实现)

2.1栈的定义声明

2.2栈的初始化

2.3入栈

2.4出栈

2.5判断是否为空栈

2.6获取栈顶元素

2.7栈的销毁

3.栈的实际运用

---

大家好，今天为大家带来C语言初阶数据结构中关于栈的相关知识

栈（stack）：一种特殊的线性表结构，其结构只允许在固定的一端存储和删除数据，在只允许存储和删除数据的一端称之为栈顶，其另一端称为栈底。栈中数据严格遵循后进先出LIFO的原则。

入栈:又称进栈或压栈,将数据存放在栈顶

出栈:将栈顶第一个元素拿出删除

我们可以把栈想象为弹匣：后装上的子弹先打出来

1.栈的实现方法

栈的实现一般可以用数组或链表来实现，但数组与链表相比，在数组尾部插入数据可以直接插入，相比于链表的遍历，用数组就更优一点(当然如果要用链表实现，可以让第一个节点为栈顶，这样更方便)

2.栈的具体实现(用数组实现)

栈的具体实现与顺序表十分类似，在此不多赘述

C语言数据结构——顺序表，及通讯录项目的模拟实现-CSDN博客https://blog.csdn.net/lunar_coder/article/details/157655927?spm=1011.2415.3001.5331

//具体功能实现目录
//初始化与销毁
void STInit(pst ps);
void STDestroy(pst ps);

//入栈与出栈
void STPush(pst ps, STdataType n);
void STPop(pst ps);

//判断是否为空栈
bool STEmpty(pst ps);

//获取栈顶元素
STdataType STTop(pst ps);

// 获取栈中有效元素个数 
int STSize(pst ps);

2.1栈的定义声明

//需要的头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//定义栈
typedef int STdataType;//存放数据类型

typedef struct Stack
{
	STdataType* data;//储存的数据
	int top;//栈中数据个数
	int capacity;//栈的总空间大小
}Stack, *pst;

2.2栈的初始化

//初始化
void STInit(pst ps)
{
	assert(ps);
	ps->data = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

2.3入栈

//入栈
void STPush(pst ps, STdataType n)
{
	//判断空间
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//三目操作符判断总空间大小
		STdataType* tmp = (STdataType*)realloc(ps->data, sizeof(STdataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc()::");
			exit(1);
		}
		ps->data = tmp;
		tmp = NULL;
		ps->capacity = newcapacity;
	}
	ps->data[ps->top++] = n;//存放数据
}

2.4出栈

//出栈
void STPop(pst ps)
{
    assert(ps && ps->top > 0);//断言:栈中有效元素个数
    ps->top--;
}

2.5判断是否为空栈

//判断是否为空栈
bool STEmpty(pst ps)
{
	if (ps->top == 0)
	{
		return false;
	}
	return true;
}

2.6获取栈顶元素

//获取栈顶元素
STdataType STTop(pst ps)
{
	return ps->data[ps->top - 1];
}

2.7栈的销毁

//销毁
void STDestroy(pst ps)
{
	assert(ps);
	free(ps);
	ps = NULL;
}

3.栈的实际运用

在掌握栈的定义及实现后，我们就可以运用到实际运用场景中了

20. 有效的括号 - 力扣（LeetCode）https://leetcode.cn/problems/valid-parentheses/description/用栈解法:

//定义栈
typedef char STdataType;

typedef struct Stack
{
	STdataType* data;
	int top;
	int capacity;
}Stack, *pst;
//初始化与销毁
void STInit(pst ps)
{
	ps->data = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
void STDestroy(pst ps)
{
	assert(ps);
	free(ps);
	ps = NULL;
}

//入栈与出栈
void STPush(pst ps, STdataType n)
{
	//判断空间
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STdataType* tmp = (STdataType*)realloc(ps->data, sizeof(STdataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc()::");
			exit(1);
		}
		ps->data = tmp;
		tmp = NULL;
		ps->capacity = newcapacity;
	}
	ps->data[ps->top++] = n;
}
void STPop(pst ps)
{
	assert(ps && ps->top > 0);
	ps->top--;
}

//判断是否为空栈
bool STEmpty(pst ps)
{
	if (ps->top == 0)
	{
		return false;
	}
	return true;
}

//获取栈顶元素
STdataType STTop(pst ps)
{
	return ps->data[ps->top - 1];
}

// 获取栈中有效元素个数 
int STSize(pst ps)
{
	return ps->top;
}

bool isValid(char* s) 
{
    pst ps = (pst)malloc(sizeof(Stack));//创建栈
    STInit(ps);//初始化
    while (*s)//遍历字符串
    {
        if (*s == '(' || *s == '[' || *s == '{')//字符为左括号就入栈
        {
            STPush(ps, *s);
        }
        else//字符是右括号
        {
            if (STSize(ps) == 0)//栈中无数据匹配
            {
                return false;
            }
            char top = STTop(ps);
            if ((*s == ')' && top != '(') || 
            (*s == ']' && top != '[') || 
            (*s == '}' && top != '{'))//判断括号匹配情况
            {
                return false;
            }
            STPop(ps);//上述条件都通过代表括号与栈顶元素匹配,出栈
        }
        s++;
    }
    if (STSize(ps))//遍历完毕但栈中仍有数据
    {
        return false;
    }
    return true;
}

我们在学习栈的时候，都会觉得它只是一个“先进后出”的抽象数据结构，其实栈在计算机里最真实、最核心的应用，就是支撑函数调用。我们平时写的每一个函数调用、每一次递归，底层全靠栈在默默工作。

在函数的调用下，我们可能会想函数是怎么传递参数，将值返回时又是怎样......这背后其实都有运用到栈

当程序调用一个函数时，系统会在栈上为这次函数调用开辟一块空间，这块空间通常被称为栈帧（Stack Frame）。
栈帧里会保存这些关键信息：
 
- 函数的返回地址（执行完要回到哪里）
​
- 函数的参数
​
- 函数内部的局部变量
​
- 调用前的寄存器现场
 
这一切都完美符合栈后进先出（LIFO）的特性

整个过程就是一次次的  push  和  pop 。
我们平时遇到的栈溢出（Stack Overflow），大多就是因为无限递归或局部变量过大，把栈空间撑爆了。

可以说没有栈，函数就无法调用，程序就无法正常运行。
栈不只是数据结构，更是程序运行的基石。

感谢阅读，希望能够帮到你，也欢迎大家指错及补充