数据结构界的三大幻神----栈
首先强调一下,操作系统中也有栈的概念,但那个栈是用来存放变量,涉及到函数栈帧的销毁,与数据结构中的栈是两个不同的概念
一.栈的概念
栈（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;
}