企业官网建设流程全解析

栈：

1. 栈(stack)是限定仅在⼀端进⾏插⼊或删除操作的线性表。因此，对栈来说进⾏插⼊删除数据的这⼀ 端称为栈顶(top)，另⼀端称为栈底(bottom)，不含元素的空表称为空栈。栈中的数据元素遵循后 进先出(LIFOLastInFirstOut)的特性。

2.栈插⼊和删除数据都在栈顶端，插⼊数据⼀般叫做入栈/进栈，删除数据⼀般叫做出栈。

出栈顺序组合数组是一个卡特兰数：

，其中2n个数中选n个数的组合。

栈的基本操作：

只允许在一端进行插入和删除的线性表，栈插入（入栈）和删除（出栈）数据都在栈顶端。

栈的顺序存储

#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* _a; int _top; // 栈顶 int _capacity; // 容量 }Stack; // 初始化栈 void StackInit(Stack* ps) { assert(ps); ps->_a = (STDataType*)malloc(4 * sizeof(STDataType)); if (ps->_a == NULL) { printf("申请空间失败"); exit(-1); } ps->_top = -1; ps->_capacity = 4; } // 入栈 void StackPush(Stack* ps, STDataType data) { assert(ps);//为什么这里需要断言 //栈满了 if (ps->_capacity-1 == ps->_top) { STDataType *temp =(STDataType*)realloc(ps->_a,sizeof(STDataType)*ps->_capacity*2); if (temp == NULL) { printf("扩容失败\n"); exit(-1); } ps->_a = temp; ps->_capacity = ps->_capacity * 2; } ps->_top++; ps->_a[ps->_top] = data; } //检测栈是否为空 int StackEmpty(Stack* ps){ return ps->_top == -1; } // 出栈 void StackPop(Stack* ps) { assert(ps);//为什么这里需要断言，因为栈为空时，不能出栈，所以需要断言， //栈为空时，不能出栈 if (StackEmpty(ps)) { printf("栈空了"); return; } ps->_top--;//这里只是需要将指针指向栈顶元素的前一个位置 } // 获取栈顶元素 STDataType StackTop(Stack* ps){ assert(ps); if (StackEmpty(ps)) { printf("栈空了"); return 0; } return ps->_a[ps->_top]; } // 获取栈中有效元素个数 int StackSize(Stack* ps){ return ps->_top + 1; } // 销毁栈 void StackDestroy(Stack* ps){ assert(ps); free(ps->_a); ps->_a = NULL; ps->_top = -1; ps->_capacity = 0; } int main(){ Stack s; StackInit(&s); StackPush(&s, 1); StackPush(&s, 2); StackPush(&s, 3); StackPush(&s, 4); StackPush(&s, 5); printf("栈顶元素为: % d\n", StackTop(&s)); printf("栈中有效元素个数为: % d\n", StackSize(&s)); printf("栈是否为空: % d\n", StackEmpty(&s)); StackDestroy(&s); printf("栈已销毁\n"); printf("栈是否为空: % d\n", StackEmpty(&s)); printf("栈中有效元素个数为: % d\n", StackSize(&s)); return 0; }

栈的链式存储

在单链表中，使用头部中作为栈顶（头插和头删都是o(1)。

写的时候注意这里是否需要二级指针。

链式存储和顺序存储对比：

1.顺序存储比链式储存效率更高，出栈和入栈的时间复杂度可以做到O（1）。

2.顺序存储的唯一问题是入栈时的空间不够，扩容需要有一定的消耗，但是这个消耗可以忽略不计，只有插入到一定数量的时候才会扩容。

3.栈的顺序存储相比于链式存储cpu高速运转缓存命中率较高（认为是存放在缓存中的数据，顺序存储的数据会全部出现在缓存中，但是链式存储的可能性就很小），且没有内存碎片（认为是因为链式存储会随机占用空间，然后将大块的空间划分中小块的碎片）。

相关题目：

有效括号

思路：使用栈的方式，创建一个新的数组，左括号进栈，然后右括号与栈中的左括号对比

判断时：情况：1.左括号多余右括号。

2.右括号多余左括号。

3.栈为空。

方法1.直接创建一个大的新数组，这样在c语言中就不需要重新写一个栈出来。

遇到的问题：括号需要用单引号引起；当左右括号能对上的时候，存在栈的括号就会出去。

bool isValid(char* s) { char stack[10000]; int topstack = 0; while(*s){ if (*s == '(' || *s == '[' || *s == '{') { stack[topstack] = *s; topstack++; } else { if (topstack==0) {// //栈为空，右括号多 return false; } // char topE = stack[topstack-1];// topstack--; if (topE == '(' && *s != ')' || topE == '[' && *s != ']' || topE == '{' && *s != '}') { return false; } } s++; } //栈不为空，左括号多 return topstack == 0;//这里是用来判断结果成立的，如果成立就是1，如果不成立就是0 }

方法二：先有栈，再进行比较

方法二使用自定义的栈结构来解决问题。与方法一直接使用大数组不同，方法二先定义一个栈结构，再通过栈的入栈、出栈等操作来判断括号是否匹配。这样做的好处是代码结构更清晰、可复用性更强，也便于扩展到其他需要栈的场景。

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> // 定义栈结构 typedef struct Stack { char* data; // 栈的存储空间 int top; // 栈顶指针，指向栈顶元素的位置 int capacity; // 栈的容量 } Stack; // 初始化栈 void StackInit(Stack* ps, int capacity) { ps->data = (char*)malloc(capacity * sizeof(char)); if (ps->data == NULL) { printf("内存分配失败\n"); exit(-1); } ps->top = -1; // 栈为空时，top 指向 -1 ps->capacity = capacity; } // 判断栈是否为空 bool StackEmpty(Stack* ps) { return ps->top == -1; // top 为 -1 表示栈空 } // 入栈操作 void StackPush(Stack* ps, char val) { // 如果栈已满，则扩容 if (ps->top == ps->capacity - 1) { ps->capacity *= 2; // 容量翻倍 ps->data = (char*)realloc(ps->data, ps->capacity * sizeof(char)); if (ps->data == NULL) { printf("扩容失败\n"); exit(-1); } } ps->top++; // 栈顶指针上移 ps->data[ps->top] = val; // 将元素放入栈顶 } // 出栈操作 void StackPop(Stack* ps) { if (StackEmpty(ps)) { return; // 栈为空时不能出栈 } ps->top--; // 栈顶指针下移，逻辑上删除栈顶元素 } // 获取栈顶元素 char StackTop(Stack* ps) { if (StackEmpty(ps)) { return '\0'; // 栈为空时返回空字符 } return ps->data[ps->top]; } // 销毁栈，释放内存 void StackDestroy(Stack* ps) { free(ps->data); ps->data = NULL; ps->top = -1; ps->capacity = 0; } // 判断括号是否有效 bool isValid(char* s) { Stack st; StackInit(&st, 100); // 初始化栈，初始容量为 100 while (*s) { // 如果是左括号，则入栈 if (*s == '(' || *s == '[' || *s == '{') { StackPush(&st, *s); } else { // 如果是右括号，先检查栈是否为空 if (StackEmpty(&st)) { StackDestroy(&st); return false; // 栈为空说明右括号多余，匹配失败 } // 取出栈顶元素并出栈 char topE = StackTop(&st); StackPop(&st); // 检查栈顶左括号是否与当前右括号匹配 if ((topE == '(' && *s != ')') || (topE == '[' && *s != ']') || (topE == '{' && *s != '}')) { StackDestroy(&st); return false; // 括号类型不匹配 } } s++; // 移动到下一个字符 } // 遍历结束后，栈为空说明所有括号都匹配成功 bool result = StackEmpty(&st); StackDestroy(&st); return result; } int main() { // 测试用例 char* test1 = "()[]{}"; char* test2 = "([)]"; char* test3 = "(]"; printf("test1: %s -> %s\n", test1, isValid(test1) ? "true" : "false"); printf("test2: %s -> %s\n", test2, isValid(test2) ? "true" : "false"); printf("test3: %s -> %s\n", test3, isValid(test3) ? "true" : "false"); return 0; }

方法一与方法二对比：

• 代码结构：方法一直接在函数内部使用大数组模拟栈，代码简洁但耦合度高；方法二将栈封装为独立结构，代码更模块化，便于复用和维护。
• 空间利用：方法一固定分配 10000 个字符的空间，无论输入多短都会占用固定内存；方法二采用动态扩容机制，初始容量小，按需增长，更节省内存。
• 可扩展性：方法一的栈逻辑与题目耦合，难以复用；方法二的栈结构是通用的，可以用于其他需要栈的场景（如表达式求值、括号匹配等）。
• 性能：方法一省去了函数调用开销，性能略高；方法二虽然多了一些函数调用，但时间复杂度同样是 O(n)，在大多数场景下性能差异可以忽略。
• 健壮性：方法二对栈空、栈满等情况有更完善的检查，代码更健壮；方法一依赖固定数组，存在越界风险。

验证栈序列：

思路：两个栈：一个入栈序列、一个出栈序列。入栈序列从开始一直入栈直到与出栈序列中的栈顶匹配或者入空为止，如果入栈与出栈中的数匹配，则开始出栈，直到不匹配为止。

具体步骤：

• 准备一个辅助栈，用于模拟入栈和出栈的过程。
• 用指针 i 指向出栈序列 popped 的当前待匹配位置。
• 遍历入栈序列 pushed，将每个元素依次压入辅助栈。
• 每次压入后，检查辅助栈栈顶元素是否等于 popped[i]：如果相等，则弹出栈顶元素，i 后移，继续检查，直到栈顶不匹配或栈为空为止。
• 遍历结束后，如果辅助栈为空，说明出栈序列是合法的，返回 true；否则返回 false。

代码实现（C语言）：

#include <stdio.h> #include <stdbool.h> // 验证栈序列：pushed 是入栈序列，popped 是出栈序列 bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize) { // 辅助栈，用数组模拟 int stack[10000]; int top = -1; // 栈顶指针，初始为空 int i = 0; // 指向出栈序列 popped 的当前待匹配位置 // 遍历入栈序列 for (int j = 0; j < pushedSize; j++) { // 入栈 stack[++top] = pushed[j]; // 当栈不为空且栈顶元素等于出栈序列当前元素时，出栈 while (top != -1 && stack[top] == popped[i]) { top--; // 出栈 i++; // 出栈序列指针后移 } } // 如果栈为空，说明所有元素都成功匹配出栈，序列合法 return top == -1; } int main() { // 测试用例 1：合法序列 int pushed1[] = {1, 2, 3, 4, 5}; int popped1[] = {4, 5, 3, 2, 1}; printf("用例1: %s\n", validateStackSequences(pushed1, 5, popped1, 5) ? "true" : "false"); // 测试用例 2：非法序列 int pushed2[] = {1, 2, 3, 4, 5}; int popped2[] = {4, 3, 5, 1, 2}; printf("用例2: %s\n", validateStackSequences(pushed2, 5, popped2, 5) ? "true" : "false"); return 0; }

表达式求值

任何的表达式是由操作数、运算符以及界限符组成的，操作数可以是常数、变量等，运算符可以是算术运算符、关系运算符和逻辑运算符，界限符有左右括号和表达式结束符等。

表达式：1.前缀表达式，操作符在操作数的前面。（是操作符在对应的操作数前）

2.中缀表达式，就是我们常见的运算式。

3，后缀表达式：操作数在操作符的前面。（是操作符在对应的操作数后）

如何将中缀表达式转化成后缀/前缀表达式：将操作数按顺序写下来，然后按照优先级将操作符插入操作数中。

后续补充（机算将中缀表达式转化成后缀表达式）

逆波兰表达式求值-力扣

栈和递归

递归（Recursion）是一种通过函数自身调用自身来解决问题的编程技巧。递归与栈有着密切的联系：每一次函数调用，系统都会在内存中为该函数分配一段独立的栈帧（Stack Frame），用于保存局部变量、参数以及返回地址。当函数递归调用自身时，新的栈帧会压入调用栈；当函数返回时，对应的栈帧会从调用栈中弹出。因此，递归本质上就是借助系统调用栈（Call Stack）来保存每一层调用的状态。

递归通常包含两个关键部分：

• 递归出口（终止条件）：当满足某个条件时，递归不再继续，直接返回结果，避免无限递归导致栈溢出。
• 递归体（递推关系）：将原问题拆解为规模更小的同类子问题，并调用自身去解决。

栈和递归的关系可以总结为以下几点：

• 递归依赖系统调用栈保存每一层调用的状态，栈的后进先出特性与递归的「先调用后返回」顺序完全一致。
• 递归代码简洁、易于理解，但深度过大时可能导致栈溢出（因为递归会不停的建立栈帧，导致溢出，这里就可以将递归改为非递归，这里基本上是由循环实现）。
• 通过显式栈可以将递归改写为迭代，从而突破系统栈的深度限制，提升程序的健壮性。
• 理解栈与递归的关系，有助于深入理解函数调用机制、回溯算法以及树和图的深度优先遍历等经典问题。