一栈Stack1概念栈是一种特殊的线性表只允许在固定的一端进行插入和删除操作。这一端叫栈顶另一端叫栈底。入栈Push在栈顶放入数据出栈Pop从栈顶取出数据核心规则后进先出LIFOLast In First Out为什么栈用数组实现而不是链表数组顺序栈链表链栈尾插直接赋值a[top] x,O(1)需要malloc新节点内存连续性连续缓存友好分散缓存不友好额外空间无每个节点都多要一个next指针结论栈永远只在尾部操作数组完美避开了自己的弱点头部/中间插入慢所以数组是栈的最优解2栈的实现结构体定义typedef int STDataType; typedef struct Stack { STDataType* a; // 指向动态数组的指针真正的数据存储区在堆上 int top; // 栈顶位置也是当前元素个数指向下一个要存放的位置 int capacity; // 当前已分配的空间大小能容纳多少个元素 } ST;注意top和capacity的类型是int不是STDataType。它们存的是“管理信息”下标/个数不是“业务数据”。初始化void STInit(ST* ps) { assert(ps ! NULL); ps-a NULL; // 一开始不分配内存等第一次Push时再分配 ps-top 0; ps-capacity 0; }销毁void STDestroy(ST* ps) { assert(ps ! NULL); free(ps-a); // 释放堆区的数据内存 ps-a NULL; // 置空防止野指针 ps-top 0; ps-capacity 0; }扩容void CheckIfExpand(ST* ps) { // 容量够用直接返回 if (ps-top ps-capacity) { return; } // 新容量首次分配4个后续翻倍 int new_capacity (ps-capacity 0) ? 4 : ps-capacity * 2; // ⚠️ 关键用临时指针接收 realloc 的返回值 STDataType* tmp (STDataType*)realloc(ps-a, new_capacity * sizeof(STDataType)); if (tmp NULL) { perror(扩容失败); exit(1); } ps-a tmp; ps-capacity new_capacity; }为什么用临时指针如果realloc失败返回NULL直接用ps-a realloc(...)会导致原来的数据丢失ps-a被置为NULL旧内存无法释放也无法访问。用tmp接住失败时原数据还在。realloc传入NULL等价于malloc当ps-a NULL且ps-capacity 0时realloc(NULL, 4 * sizeof(...))等同于malloc。所以扩容函数同时处理了“首次分配”和“后续扩容”。入栈void STPush(ST* ps, STDataType x) { assert(ps ! NULL); CheckIfExpand(ps); // 先确保空间够 ps-a[ps-top] x; // 在栈顶位置放入数据 ps-top; // top 后移 }出栈void STPop(ST* ps) { assert(ps ! NULL); assert(ps-top 0); // 栈不能为空 ps-top--; // 只移动指针不删除数据 }注意我们只是把top减了 1旧数据还在数组里。下次Push时会被覆盖。不需要把旧数据清零那是浪费时间。取栈顶元素STDataType STTop(ST* ps) { assert(ps ! NULL); assert(ps-top 0); return ps-a[ps-top - 1]; // 栈顶元素在 top-1 位置 }判空和元素个数bool STEmpty(ST* ps) { assert(ps ! NULL); return ps-top 0; // 简洁写法 本身返回 bool } int STSize(ST* ps) { assert(ps ! NULL); return ps-top; // top 的值就是元素个数 }二队列Queue1概念队列只允许在一端插入队尾在另一端删除队头。入队Push在队尾插入出队Pop从队头删除核心规则先进先出FIFOFirst In First Out为什么队列用链表实现而不是数组普通队列用数组出队时要把所有元素往前搬O(n)太慢。循环队列用数组虽然解决了搬移问题但需要处理“空/满”判定后面细说逻辑复杂一些。链式队列出队只需要改指针O(1)逻辑自然。代价是每次入队都要malloc。结论链式队列是队列最自然的实现方式适合通用场景。循环队列适合“已知最大容量、追求极致性能”的场景比如嵌入式、音视频缓冲。2队列的实现结构体定义typedef int QDataType; // 队列节点 typedef struct QueueNode { QDataType val; struct QueueNode* next; } QNode; // 队列结构两个指针 一个计数器 typedef struct Queue { QNode* phead; // 队头指针 QNode* ptail; // 队尾指针 int size; // 当前元素个数 } Queue;为什么要有ptail因为入队在队尾如果没有ptail每次入队都要遍历到链表末尾O(n)。有了ptail入队 O(1)。初始化void QueueInit(Queue* pq) { assert(pq ! NULL); pq-phead NULL; pq-ptail NULL; pq-size 0; }创建节点内部函数QNode* CreateNode(QDataType x) { QNode* newnode (QNode*)malloc(sizeof(QNode)); if (newnode NULL) { perror(malloc fail); exit(1); } newnode-val x; newnode-next NULL; return newnode; }入队队尾插入void QueuePush(Queue* pq, QDataType x) { assert(pq ! NULL); QNode* newnode CreateNode(x); if (pq-phead NULL) { // 队列为空头和尾都指向新节点 pq-phead newnode; pq-ptail newnode; } else { // 队列非空挂在尾巴后面 pq-ptail-next newnode; pq-ptail newnode; } pq-size; }出队队头删除void QueuePop(Queue* pq) { assert(pq ! NULL); assert(pq-phead ! NULL); // 队列不能为空 QNode* tmp pq-phead-next; // 记住第二个节点 free(pq-phead); // 释放队头 pq-phead tmp; // 头指针后移 // ⚠️ 关键如果删完队列变空了ptail 也要置 NULL if (pq-phead NULL) { pq-ptail NULL; } pq-size--; }经典错误如果队列只有一个节点出队后phead变成NULL但ptail还指向那个已经被释放的节点。下次Push时访问ptail-next就崩溃了正确做法删完后判断phead是否为空如果为空说明队列空了ptail也要同步置NULL。取队头/队尾QDataType QueueFront(Queue* pq) { assert(pq ! NULL); assert(pq-phead ! NULL); return pq-phead-val; } QDataType QueueBack(Queue* pq) { assert(pq ! NULL); assert(pq-ptail ! NULL); return pq-ptail-val; }判空和元素个数bool QueueEmpty(Queue* pq) { assert(pq ! NULL); return pq-size 0; // 或者 return pq-phead NULL; } int QueueSize(Queue* pq) { assert(pq ! NULL); return pq-size; }销毁队列void QueueDestroy(Queue* pq) { assert(pq ! NULL); QNode* cur pq-phead; while (cur ! NULL) { QNode* next cur-next; // 先记住下一个 free(cur); // 释放当前 cur next; // 移到下一个 } // 所有节点释放完后指针置空 pq-phead NULL; pq-ptail NULL; pq-size 0; }三、经典算法题1 有效的括号LeetCode 20题目给定一个只包含()[]{}的字符串判断括号是否匹配。思路遇到左括号([{就入栈遇到右括号)]}就检查栈顶是否是对应的左括号不匹配直接返回false遍历完后栈必须为空bool isValid(char* s) { ST st; STInit(st); for (int i 0; s[i] ! \0; i) { if (s[i] ( || s[i] [ || s[i] {) { STPush(st, s[i]); } else { if (STEmpty(st)) return false; char top STTop(st); STPop(st); if (!checkthefit(top, s[i])) return false; } } bool result STEmpty(st); STDestroy(st); // ⚠️ 别忘了销毁 return result; }关键函数返回前一定要调用STDestroy释放栈内部动态分配的数组内存。否则每次调用都会泄漏内存。2 用队列实现栈LeetCode 225核心思想两个队列q1主队列和q2辅助队列。Push 操作新元素放入空的那个队列把另一个非空队列的所有元素全部搬过来这样非空队列的队头永远是最新入栈的元素typedef struct { Queue q1; Queue q2; } MyStack; void myStackPush(MyStack* obj, int x) { // 找到空队列 Queue* empty QueueEmpty(obj-q1) ? obj-q2 : obj-q1; Queue* nonEmpty QueueEmpty(obj-q1) ? obj-q1 : obj-q2; QueuePush(empty, x); while (!QueueEmpty(nonEmpty)) { QueuePush(empty, QueueFront(nonEmpty)); QueuePop(nonEmpty); } }3用栈实现队列LeetCode 232核心思想in栈只管入队out栈只管出队。Push直接压入in栈Pop/Peek如果out栈为空把in栈的所有元素搬到out栈然后从out栈弹出/查看typedef struct { ST in; ST out; } MyQueue; int myQueuePop(MyQueue* obj) { // 只有在 out 栈空的时候才搬运 if (obj-out.top 0) { while (obj-in.top ! 0) { STPush(obj-out, STTop(obj-in)); STPop(obj-in); } } int x STTop(obj-out); STPop(obj-out); return x; }4 设计循环队列LeetCode 622核心难点用数组实现队列时如何区分“队空”和“队满”标准做法浪费一个空间判空front rear判满(rear 1) % capacity front缺点永远浪费一个位置最多存capacity - 1个元素我的做法引入size变量判空size 0判满size capacity优点空间全部利用逻辑更直观typedef struct { int* a; int front; int rear; int size; int capacity; } MyCircularQueue; bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (obj-size obj-capacity) return false; obj-a[obj-rear] value; obj-rear (obj-rear 1) % obj-capacity; obj-size; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (obj-size 0) return false; obj-front (obj-front 1) % obj-capacity; obj-size--; return true; }