栈的核心原理

1 栈的概念及结构

栈是一种特殊的线性表，其特点是只允许在固定的一端进行插入和删除操作。进行操作的一端称为栈顶，另一端称为栈底。

栈中的元素遵循后进先出（LIFO，Last In First Out） 原则。

• 压\\入\\进栈（Push）：在栈顶插入元素的操作
• 出栈（Pop）：从栈顶删除元素的操作

2 栈的实现

栈可以通过数组或链表实现，数组实现更为高效（尾插尾删的时间复杂度为 O (1)）。

2.1 栈的结构定义及声明

#pragma once#include#include#include#includetypedef STDataType;//定义typedef struct Stack{STDataType* a;int top;int capacity;}ST;// 初始化void STInit(ST* pst);// 销毁void STDestroy(ST* pst);// 插入数据（入栈）void STPush(ST* pst, STDataType x);//删除数据（出栈）void StackPop(ST* pst);// 获取栈顶元素STDataType STTop(ST* pst);// 栈的判空bool STEmpty(ST* pst);// 栈的大小(获取栈中数据个数)int STSize(ST* pst);

2.2 核心操作实现

1.初始化

// 初始化void STInit(ST* ps){ assert(ps); ps->a = NULL; ps->top = 0; // 设定初始栈顶为0，表示无元素 ps->capacity = 0;}

2.销毁

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

3.入栈操作

原本栈为空时，top 为-1，为了便于写代码，令为 0

 原本 top 指向栈顶元素的，没有元素时候，指向 -1，不指向 0。

所以对于上述两种情况，

情况一：

top 指向栈顶数据。

情况二：

top 指向栈顶数据的下一个位置。

// 插入数据（入栈）void STPush(ST* ps, STDataType x){ assert(ps); // 检查容量，不足则扩容 if (ps->top == ps->capacity) //相等就扩容 { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity* 2; //最初时候都是0，刚开始开空间开4个 STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror(\"realloc fail\"); return; } ps->a = tmp; ps->capacity = newCapacity; } // 存入数据后栈顶上移 ps->a[ps->top] = x; ps->top++;}

4.出栈操作

void StackPop(ST* ps){ assert(ps); // 栈顶下移即完成出栈 ps->top--;  }

5.获取栈顶元素

// 获取栈顶元素STDataType STTop(ST* ps){ assert(ps); //assert(!STEmpty(ps)); assert(ps->top > 0); //避免空栈 return ps->a[ps->top - 1];}

6.栈的判空

// 栈的判空bool STEmpty(ST* ps){ assert(ps); return ps->top == 0;}

 7.栈的大小

// 栈的大小(获取栈中数据个数)int STSize(ST* ps){ assert(ps); return ps->top;}

2.3 测试一下

#define _CRT_SECURE_NO_WARNINGS 1#include\"Stack.h\"int main(){ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);//访问元素while (!STEmpty(&s)){printf(\"%d \", STTop(&s));STPop(&s);}STDestroy(&s);return 0;}