栈和队列栈Stack一、基础概念类前置核心定义栈是后进先出LIFOLast In First Out的受限线性表仅允许在「栈顶」一端进行插入、删除操作另一端为栈底。类比羽毛球筒最后放进去的球最先被拿出来。工程通用约定核心操作仅 4 个push入栈、pop出栈、top取栈顶、empty判空所有操作时间复杂度均为O(1)两种主流实现顺序栈数组底层、链栈链表底层工业界优先用顺序栈性能更优提问顺序栈和链栈有什么区别各自适用什么场景回答两者核心差异在底层存储结构对应性能和适用场景完全不同维度顺序栈数组实现链栈单链表实现内存布局连续内存CPU 缓存命中率高零散内存节点带指针开销缓存不友好扩容成本容量满后需扩容一般 2 倍扩容有数据拷贝开销随用随申请节点无扩容成本性能表现访问速度快常数级开销更小指针操作略慢内存碎片更多溢出风险固定容量有栈溢出风险动态扩容可缓解内存充足则不会溢出适用场景容量可预估、追求极致性能的通用场景容量波动极大、元素数量不确定的场景提问栈的操作都是 O (1)为什么回答因为栈只操作栈顶这一个位置入栈、出栈都只需要修改栈顶指针 / 索引不需要遍历其他元素所以所有核心操作都是常数时间复杂度。二、核心操作1. 顺序栈最简实现class ArrayStack{ private: vectorint arr; int topId; public: ArrayStack(int cap) : arr(cap), topId(-1) {} // 判空 bool empty() { return topId -1; } // 入栈 void push(int v) { if(topId arr.size() - 1) return; arr[topId] v; } // 出栈 void pop() { if(empty()) return; topId -- ; } // 取栈顶 int top() { if(empty()) return -1; return arr[topId]; } }2. 链栈最简实现用单链表头节点作为栈顶头插头删天然适配栈的 LIFO 特性struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ​ class LinkedStack { private: ListNode* topNode; // 栈顶节点链表头 public: LinkedStack() : topNode(nullptr) {} ​ void push(int val) { ListNode* node new ListNode(val); node-next topNode; // 新节点插在栈顶前面 topNode node; // 更新栈顶指针 } ​ void pop() { if (empty()) return; ListNode* del topNode; topNode topNode-next; delete del; } ​ int top() { if (empty()) return -1; return topNode-val; } ​ bool empty() { return topNode nullptr; } };3. 高频算法题最小栈要求push/pop/top/getMin操作均为 O (1)双栈辅助法是标准写法class MinStack { private: stackint dataStack; // 主栈存所有数据 stackint minStack; // 辅助栈同步存当前栈的最小值 public: MinStack() {} void push(int val) { dataStack.push(val); // 辅助栈压入「当前值与栈顶中更小的数」 if(minStack.empty() || val minStack.top()) { minStack.push(val); } else { minStack.push(minStack.top()); } } void pop() { dataStack.pop(); minStack.pop(); // 同步弹出保持栈顶始终是当前最小值 } int top() { return dataStack.top(); } int getMin() { return minStack.top(); } }4. 高频算法题两个栈实现队列class MyQueue { private: stackint inStack; // 入队专用栈 stackint outStack; // 出队专用栈 // 入栈元素全部倒进出栈翻转顺序实现FIFO void in2out() { while(!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } public: MyQueue() {} void push(int x) { inStack.push(x); } int pop() { if(empty()) return -1; if(outStack.empty()) in2out(); int x outStack.top(); outStack.pop(); return x; } int peek() { if(empty()) return -1; if(outStack.empty()) in2out(); return outStack.top(); } bool empty() { return inStack.empty() outStack.empty(); } }三、进阶理解类提问什么是栈溢出哪些场景会触发回答栈溢出就是栈的可用空间被耗尽继续入栈就会越界。分两类场景数据结构层面固定容量的顺序栈满了还继续 push会触发数组越界动态扩容栈可规避这个问题。系统层面函数递归层数过深系统调用栈每个函数对应一个栈帧存参数、局部变量、返回地址被占满会触发栈溢出崩溃比如无限递归、深度过大的树遍历。提问递归和栈是什么关系为什么可以用栈把递归改成迭代回答递归的底层就是操作系统的函数调用栈每次调用函数就把栈帧压入系统栈函数执行完返回就弹出栈帧完全符合 LIFO 特性。手动用栈模拟系统栈的压入弹出过程就能把递归改成迭代写法好处是可以控制栈的大小避免递归深度过大导致的系统栈溢出性能也更可控。提问顺序栈扩容的均摊时间复杂度为什么还是 O (1)回答一般顺序栈扩容为原来的 2 倍只有当栈满时才会触发一次扩容需要拷贝 n 个元素。但前面 n 次入栈都是 O (1)把扩容的开销平摊到 n 次操作上平均每次操作的额外开销是常数级所以均摊时间复杂度依然是 O (1)。四、项目实战场景经典算法落地场景括号匹配编译器语法检查、HTML 标签校验左括号入栈遇到右括号弹栈匹配最后栈空则合法。表达式解析计算器的中缀表达式转后缀逆波兰、逆波兰表达式求值都是栈的经典应用。二叉树遍历前 / 中 / 后序遍历的迭代写法全部用栈模拟递归过程。单调栈进阶算法考点解决接雨水、柱状图最大矩形、下一个更大元素类问题时间复杂度 O (n)。工程落地场景浏览器前进后退用两个栈实现一个栈存已访问页面一个栈存后退的页面点击后退就从主栈弹到辅助栈点击前进就弹回来。编辑器撤销 / 重做和前进后退逻辑一致操作压入撤销栈撤销就弹到重做栈完美匹配 LIFO 特性。函数调用栈所有编程语言、操作系统的底层核心维护函数调用的上下文保证函数返回后能回到正确的执行位置。语法解析编译器的语法分析、JSON/XML 解析嵌套结构的校验全部依赖栈的后进先出特性。队列Queue一、基础概念类前置核心定义队列是先进先出FIFOFirst In First Out的受限线性表仅允许在「队尾」插入、「队头」删除。类比排队买奶茶先排的人先买到后到的人排队尾。工程通用约定核心操作 4 个enqueue入队、dequeue出队、front取队首、empty判空标准实现下均为O(1)主流实现顺序队列数组底层工业界常用循环队列优化、链式队列链表底层提问顺序队列和链式队列的区别为什么工程中优先用循环队列回答普通顺序队列有「假溢出」的先天缺陷出队时队头指针后移前面空出来的位置无法再利用数组没满但没法继续入队浪费空间。循环队列把数组首尾相连成环形用取模操作让指针循环移动复用前面的空闲位置彻底解决假溢出问题空间利用率极高所以工业界顺序队列基本都用循环实现。维度循环队列数组实现链式队列单链表实现内存布局连续内存缓存友好零散内存指针有额外开销空间利用率高循环复用数组空间一般节点带指针冗余性能表现速度快无内存申请释放开销略慢入队出队伴随节点申请释放容量特性固定容量需预估无容量上限动态伸缩适用场景容量可预估、追求性能的通用场景容量波动大、元素数量不确定的场景提问队列的操作都是 O (1) 吗回答标准实现循环队列、带尾指针的链式队列的入队出队都是 O (1)因为只修改队头 / 队尾两个指针不需要遍历。如果是不带尾指针的单链表实现队列入队需要遍历到队尾时间复杂度会退化成 O (n)所以链式队列一定会维护尾指针。二、核心操作1. 循环队列实现用 size 计数器判断空满逻辑清晰避免边界判断错误class MyCircularQueue { private: vectorint arr; int front; // 队首元素的下标 int rear; // 下一个入队元素的位置队尾的下一位 int size; // 当前元素数量 int capacity; // 总容量 public: MyCircularQueue(int k) : arr(k), front(0), rear(0), size(0), capacity(k) {} // 入队 bool enQueue(int value) { if(isFull()) return false; arr[rear] value; rear (rear 1) % capacity; // 循环后移取模实现环形 size ; return true; } // 出队 bool deQueue() { if(isEmpty()) return false; front (front 1) % capacity; // 队首循环后移 size -- ; return true; } // 取队首 int Front() { if(isEmpty()) return -1; return arr[front]; } // 取队尾 int Rear() { if(isEmpty()) return -1; // rear是下一个位置队尾是rear前一位加capacity避免负数 return arr[(rear - 1 capacity) % capacity]; } ​ bool isEmpty() { return size 0; } bool isFull() { return size capacity; } }提醒循环队列判断空满有两种方式计数器法最不容易写错另一种是预留一个空位优先写计数器法。2. 链式队列实现// 带尾指针O (1) 入队出队 struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ​ class LinkedQueue { private: ListNode* frontNode; ListNode* rearNode; int size; public: LinkedQueue() : frontNode(nullptr), rearNode(nullptr), size(0) {} // 入队 void enQueue(int val) { ListNode* node new ListNode(val); if(isEmpty()) { frontNode node; rearNode node; } else { rearNode-next node; rearNode node; } } // 出队 bool deQueue() { if(isEmpty()) return false; ListNode* del frontNode; frontNode frontNode-next; delete del; size -- ; if(isEmpty()) rearNode nullptr; return true; } int Front() { if(isEmpty()) return -1; return frontNode-val; } bool isEmpty() { return size 0; } }; ​3. 两个队列实现栈class MyStack { private: queueint q1; // 主队列队首始终是栈顶 queueint q2; // 辅助队列 public: MyStack() {} ​ void push(int x) { q2.push(x); // 把q1所有元素移到q2让新元素排在队首 while (!q1.empty()) { q2.push(q1.front()); q1.pop(); } swap(q1, q2); // 交换后q1继续作为主队列 } ​ int pop() { int val q1.front(); q1.pop(); return val; } ​ int top() { return q1.front(); } ​ bool empty() { return q1.empty(); } };三、进阶理解类提问双端队列deque是什么有什么优势回答双端队列是两端都可以入队、出队的队列同时具备栈和队列的特性既可以当栈用也可以当队列用。STL 中的 deque 采用分段连续数组实现头尾插入删除都是 O (1)随机访问性能比链表好仅略逊于 vector是非常通用的线性数据结构滑动窗口最大值、BFS 优化等场景都会用到。提问常见的队列变种有哪些分别用在什么场景回答工业界常用的衍生队列有三类阻塞队列队列为空时消费者线程阻塞队列满时生产者线程阻塞是线程池、生产者 - 消费者模型的核心组件。优先队列按优先级出队不遵循 FIFO底层一般是堆实现用于任务调度、TopK 问题。延迟队列元素到了指定过期时间才能出队底层用时间轮或堆实现用于定时任务、超时订单关闭等场景。提问循环队列为什么常用取模实现有没有其他实现方式回答取模是最简单的环形指针实现方式让指针走到数组末尾后自动回到开头逻辑直观。也可以用位运算优化容量为 2 的 n 次幂时(capacity-1)替代取模速度更快本质和取模一致是性能优化手段。四、项目实战场景经典算法落地场景BFS 广度优先搜索二叉树层序遍历、图的最短路径、迷宫问题全部用队列实现层序遍历天然符合 FIFO 特性。滑动窗口用双端队列维护窗口内的有效元素解决滑动窗口最大值、最小值类问题。工程落地场景生产者 - 消费者模型用队列做缓冲层生产者往队尾放任务消费者从队头取任务解耦生产和消费的速度差是后端系统最基础的异步模型。消息队列MQ分布式系统核心组件本质就是持久化的分布式队列实现系统解耦、异步处理、削峰填谷三大核心价值比如 Kafka、RabbitMQ。线程池任务队列线程池的待执行任务全部存在队列里空闲线程从队头取任务执行控制并发数量避免线程频繁创建销毁。操作系统调度进程就绪队列、IO 请求队列都是 FIFO 队列模型时间片轮转调度用的就是循环队列。流量削峰秒杀、大促流量洪峰时用队列排队请求超过容量直接拒绝保护后端服务不被冲垮。