目录

前言

一、栈的概念及结构

二、栈的实现

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]; }

总结

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