目录

前言

一、栈的概念及结构

二、栈的实现

1. 栈的声明

2.初始化栈 

3. 栈的销毁

4.判断是否为空栈

 5.入栈（只能插入栈顶元素）

6. 出栈（只能从栈顶删除）

 7.栈的大小

8.获取栈顶元素

总结

---

前言

        在计算机科学中，栈（Stack）是一种常见的数据结构，它遵循“后进先出”（LIFO）原则。栈可以被看作是一种特殊的线性表，它只允许在表的一端进行插入和删除操作，这一端被称为栈顶。
栈的操作相对简单，只有两种基本操作：入栈（Push）和出栈（Pop）。入栈将一个元素放入栈顶，出栈将栈顶元素弹出，也就是从栈中删除一个元素。
        栈的应用非常广泛，特别是在计算机编程中。它常常作为一种临时存储空间来管理函数调用、表达式求值等操作。栈也常被用来处理递归算法、深度优先搜索、括号匹配等问题。
        通过构建一个栈，我们可以非常方便地实现后进先出的数据结构，使得我们能够高效地处理一些具有类似特性的问题。因此，了解和掌握栈的概念和操作是很重要的。在接下来的内容中，我们将详细介绍栈的基本原理、以及常见实现方式。希望通过本文的学习，读者能够深入理解栈，并能够在实际编程中熟练运用。

一、栈的概念及结构

        栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

        压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

        出栈：栈的删除操作叫做出栈。出数据也在栈顶。

二、栈的实现

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

1. 栈的声明

typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;

记录栈顶和容量 

2.初始化栈 

void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = -1;//栈顶元素位置
}

top记录栈顶元素位置，或者下一位都可以，但是要注意之后的使用。

3. 栈的销毁

void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = -1;ps->capacity = 0;
}

4.判断是否为空栈

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

 5.入栈（只能插入栈顶元素）

void STPush(ST* ps, STDataType x)
{assert(ps);if ((ps->top +1) == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity*2);if (tmp == NULL){perror("malloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top + 1] = x;ps->top++;
} 

这里在判断容量够不够时只在入栈时使用，所以可以不用封装函数；

在容量不够时需要扩容。

6. 出栈（只能从栈顶删除）

void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}

 7.栈的大小

int STSize(ST* ps)
{assert(ps);return ps->top + 1;
}

8.获取栈顶元素

STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top];
}

总结

        在了解了栈如何实现后，还需要多做相关题目才可以理解栈的用法，可以在网上多找一些题目练练手哟！