栈到底是什么

一、栈到底是个啥说白了栈就是一种操作受限的线性表。 普通的数组、链表想在哪插在哪删都行但栈不行它只开放一端给你操作这一端叫栈顶另一端封死叫栈底。所有的插入、删除都只能在栈顶做。这种限制催生出了栈最核心的特性后进先出LIFO, Last In First Out。 举个最生活化的例子摞书。 你往桌上放书一本本往上叠最后放的那本在最上面你要拿书只能先拿最上面那本。最后放上去的第一个被拿下来 —— 这就是标准的栈逻辑。往栈里加数据叫入栈压栈从栈里删数据叫出栈弹栈俩操作都只碰栈顶不碰栈底。二、栈为什么偏爱数组实现理论上数组和链表都能实现栈但实际写代码的时候几乎所有人都会选数组。 原因非常实在栈的所有操作都在尾部而数组的尾插、尾删天然就是 O (1)完全对上了再加上数组是连续内存缓存命中率高比链表省空间还跑得快没理由不用。栈的结构长什么样一个动态数组实现的栈结构体里就三样东西typedef int STDataType; typedef struct Stack { STDataType* a; // 存数据的动态数组 int top; // 栈顶标记指向下一个可插入的位置 int capacity; // 数组总共能存多少数据 } ST;这里说下top的约定一般我们让它指向 “栈顶元素的下一个空位”。比如空栈的时候top0入栈一个元素后top1这样top的值刚好等于栈里元素的个数省得单独维护 size。初始化和销毁初始化就是把栈置成空状态销毁就是把申请的数组释放掉避免内存泄漏。// 初始化栈 void STInit(ST* ps) { assert(ps); ps-a NULL; ps-top 0; ps-capacity 0; } // 销毁栈 void STDestroy(ST* ps) { assert(ps); free(ps-a); ps-a NULL; ps-top 0; ps-capacity 0; }入栈先看容量够不够入栈是最常写的操作核心就两步先检查容量满了就扩容再把数据放到栈顶top往后挪一位。扩容这里有个细节不用直接改结构体里的capacity先用局部变量newcap算好新容量申请成功了再正式赋值。万一realloc失败了原栈的数据和容量都不会乱这是写动态结构的基本防御性写法。// 入栈 void STPush(ST* ps, STDataType x) { assert(ps); // 容量满了先扩容 if (ps-top ps-capacity) { int newcap ps-capacity 0 ? 4 : 2 * ps-capacity; STDataType* tmp (STDataType*)realloc(ps-a, newcap * sizeof(STDataType)); if (tmp NULL) { perror(realloc 申请失败); exit(1); } ps-a tmp; ps-capacity newcap; } // 栈顶放入数据top后移 ps-a[ps-top] x; }出栈和取栈顶出栈特别简单只要栈不是空的把top减 1 就完事了。 不用特意把原位置的数据清掉因为下次入栈会直接覆盖。数据还在那里但只要top不认可它它就不算栈里的元素了。// 出栈 void STPop(ST* ps) { assert(ps); assert(ps-top 0); // 空栈不能弹 ps-top--; } // 取栈顶元素 STDataType STTop(ST* ps) { assert(ps); assert(ps-top 0); return ps-a[ps-top - 1]; }几个实用的小接口判空、取元素个数都是一行代码的事// 栈里有多少个元素 int STSize(ST* ps) { assert(ps); return ps-top; } // 栈是不是空的 bool STEmpty(ST* ps) { assert(ps); return ps-top 0; }三、栈的特点和适用场景栈的几个关键特点操作单一只在栈顶增删逻辑简单不容易出 bug效率极高入栈、出栈、取栈顶全是 O (1)几乎没有额外开销不支持随机访问想拿栈底的元素必须把上面的全弹出去内存连续数组实现的缓存友好访问速度快