阅读量:0
目录
前言
在计算机科学中，栈（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]; }总结
在了解了栈如何实现后，还需要多做相关题目才可以理解栈的用法，可以在网上多找一些题目练练手哟！
