首先强调一下,操作系统中也有栈的概念,但那个栈是用来存放变量,涉及到函数栈帧的销毁,与数据结构中的栈是两个不同的概念
一.栈的概念
栈（Stack）是一种抽象数据类型，它遵循后进先出（Last-In, First-Out，LIFO）的原则。栈就像一摞盘子，你只能从最上面取盘子或把盘子放在最上面
栈的基本操作包括入栈（Push）和出栈（Pop）。入栈就是把元素添加到栈的顶部，出栈则是从栈的顶部取出元素。除此之外，常见的栈操作还有查看栈顶元素（Peek）和判断栈是否为空。
栈在很多场景中都有应用，比如函数调用栈、表达式求值、括号匹配、递归等。它的优势在于能够高效地进行入栈和出栈操作，而且不需要事先知道元素的数量。
例如，在编程中，当你调用一个函数时，系统会将函数的参数和返回地址压入栈中。当函数执行完毕后，再从栈中弹出返回地址，从而实现函数的正确返回。
二.栈与递归的关系
递归和栈的关系非常密切 递归是一种通过函数自身调用自身来解决问题的方法。在递归过程中，函数会不断地调用自己，直到达到某个终止条件。
当函数进行递归调用时，系统会自动使用栈来保存函数的调用信息，包括函数参数、局部变量等。每次递归调用都会在栈中创建一个新的帧（Frame），用于保存当前函数的状态。
当递归函数返回时，系统会从栈中弹出对应的帧，恢复函数的状态，并继续执行后续操作。通过栈的机制，递归可以实现函数在不同层次上的正确执行和状态恢复。
例如，计算阶乘的递归函数可以通过不断调用自身来累积阶乘的结果。在这个过程中，栈会记录每次递归调用的状态，确保正确地计算阶乘。
需要注意的是，递归虽然在表达逻辑上比较简洁，但由于栈的深度限制，递归可能会导致栈溢出等问题。在实际应用中，需要合理使用递归，并注意避免过度递归导致的问题。
三.手撕栈
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int StackData; typedef struct Stack { StackData* data; int top; int size; }Stack; //初始化栈 void initStack(Stack* st) { assert(st); st->data = NULL; st->top = 0; st->size = 0; } //销毁栈 void destroyStack(Stack* st) { assert(st); free(st->data); st->data = NULL; st->size = st->top = 0; } //栈是否为空 bool isEmpty(Stack* st) { assert(st); return st->top == 0; } //出栈 void popStack(Stack* st) { assert(st); assert(!isEmpty); st->top--; } //入栈 void pushStack(Stack* st, StackData data) { assert(st); if (st->top == st->size) { int newsize = st->size == 0 ? 4 : 2 * st->size; StackData* temp = (StackData*)realloc(st->data, sizeof(StackData) * newsize); if (temp != NULL) { st->data = temp; st->size = newsize; } } st->data[st->top] = data; st->top++; } //取出栈顶元素 StackData topStack(Stack* st) { assert(st); assert(!isEmpty); return st->data[st->top - 1]; } //栈的大小 int sizeStack(Stack* st) { assert(st); return st->top; } int main() { return 0; }
