数据结构界的三大幻神----栈

首先强调一下,���作系统中也有栈的概念,但那个栈是用来存放变量,涉及到函数栈帧的销毁,与数据结构中的栈是两个不同的概念

一.栈的概念

栈（Stack）是一种抽象数据类型，它遵循后进先出（Last-In, First-Out，LIFO）的原则。栈就像一摞盘子，你只能从最上面取盘子或把盘子放在最上面

栈的基本操作包括入栈（Push）和出栈（Pop）。入栈就是把元素添加到栈的顶部，出栈则是从栈的顶部取出元素。除此之外，常见的栈操作还有查看栈顶元素（Peek）和判断栈是否为空。

栈在很多场景中都有应用，比如函数调用栈、表达式求值、括号匹配、递归等。它的优势在于能够高效地进行入栈和出栈操作，而且不需要事先知道元素的数量。

例如，在编程中，当你调用一个函数时，系统会将函数的参数和返回地址压入栈中。当函数执行完毕后，再从栈中弹出返回地址，从而实现函数的正确返回。

二.栈与递归的关系

递归和栈的关系非常密切 递归是一种通过函数自身调用自身来解决问题的方法。在递归过程中，函数会不断地调用自己，直到达到某个终止条件。

当函数进行递归调用时，系统会自动使用栈来保存函数的调用信息，包括函数参数、局部变量等。每次递归调用都会在栈中创建一个新的帧（Frame），用于保存当前函数的状态。

当递归函数返回时，系统会从栈中弹出对应的帧，恢复函数的状态，并继续执行后续操作。通过栈的机制，递归可以实现函数在不同层次上的正确执行和状态恢复。

例如，计算阶乘的递归函数可以通过不断调用自身来累积阶乘的结果。在这个过程中，栈会记录每次递归调用的状态，确保正确地计算阶乘。

需要注意的是，递归虽然在表达逻辑上比较简洁，但由于栈的深度限制，递归可能会导致栈溢出等问题。在实际应用中，需要合理使用递归，并注意避免过度递归导致的问题。

三.手撕栈

#include

#include

#include

#include

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;

}