栈与队列：原理、实现及面试高频应用场景

大家好欢迎继续学习《算法面试60讲2026最新版·全真题带解析》专栏上一篇我们系统学习了数组与链表这两个最基础的数据结构吃透了它们的定义、底层原理和面试真题今天这一篇我们将学习另外两个高频基础数据结构——栈与队列。栈与队列和数组、链表一样是算法面试中基础且高频的考点尤其在后端、算法岗的面试中出场率极高。它们本质上都是线性数据结构但其核心特性“先进后出”“先进先出”决定了它们的独特应用场景也是面试考察的重点。值得注意的是栈和队列的底层实现大多基于我们上一篇学过的数组或链表吃透数组与链表学习栈和队列会非常轻松。今天这篇内容我们依然聚焦面试考点从定义、底层实现、核心特性到面试高频真题和应用场景一步步讲透让你看完就能应对面试中的相关问题。一、栈Stack先进后出面试高频1. 栈的定义与核心特性面试必背栈是一种遵循“先进后出”LIFOLast In First Out规则的线性数据结构。简单来说就是“先放进去的元素最后才能取出来”就像我们平时叠盘子先叠的盘子在最下面后叠的盘子在最上面取盘子时只能先取最上面的再取下面的。面试重点记住“先进后出”这个核心特性这是栈与队列最本质的区别也是面试官常考的基础知识点。栈的两个核心操作面试必记入栈push将元素添加到栈的顶部栈顶时间复杂度O(1)。出栈pop将栈顶部的元素删除并返回该元素时间复杂度O(1)。补充栈还有一个常用操作—— peek查看栈顶元素只查看栈顶元素不删除时间复杂度同样为O(1)栈不支持随机访问只能访问栈顶元素这一点和数组、链表有明显区别。2. 栈的底层实现面试高频追问栈的底层实现有两种方式分别基于数组和链表两种实现各有优劣面试时可能会被追问“栈的底层怎么实现”两种方式都要掌握实现方式1基于数组实现顺序栈用数组作为底层存储容器定义一个“栈顶指针”指向栈顶元素的位置初始时栈为空栈顶指针为-1。入栈栈顶指针加1将元素存入数组对应下标位置。出栈取出栈顶指针指向的元素栈顶指针减1。优点访问速度快基于数组连续内存入栈、出栈操作简单缺点数组容量固定需要手动扩容扩容时需要复制元素时间复杂度为O(n)。实现方式2基于链表实现链式栈用单链表作为底层存储容器通常以链表的头节点作为栈顶方便入栈、出栈操作不需要额外维护栈顶指针。入栈将新节点作为头节点插入相当于栈顶添加元素时间复杂度O(1)。出栈删除头节点并返回头节点的值相当于删除栈顶元素时间复杂度O(1)。优点容量动态不需要扩容插入、删除效率高缺点访问速度比顺序栈慢链表非连续内存无下标访问。面试补充实际开发中顺序栈数组实现更常用因为大部分场景下栈的容量可以提前预估扩容频率较低且访问速度更快。3. 栈的面试高频真题必练校招/社招通用栈的面试题核心考察“先进后出”特性的应用以下3道真题是高频考点覆盖基础题和中档题建议动手写代码实现真题1有效的括号LeetCode 20简单必练题目给定一个只包括 (){}[] 的字符串 s判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合。核心思路栈的经典应用利用“先进后出”特性遍历字符串遇到左括号(、{、[入栈。遇到右括号)、}、]判断栈是否为空或栈顶元素是否与当前右括号匹配不匹配则返回false匹配则出栈。遍历结束后若栈为空则字符串有效否则无效。代码示例Javapublic boolean isValid(String s) { // 用栈存储左括号 StackCharacter stack new Stack(); for (char c : s.toCharArray()) { // 遇到左括号入栈 if (c ( || c { || c [) { stack.push(c); } else { // 遇到右括号判断栈是否为空或匹配 if (stack.isEmpty()) { return false; } char top stack.pop(); // 判断括号是否匹配 if ((c ) top ! () || (c } top ! {) || (c ] top ! [)) { return false; } } } // 遍历结束栈为空则有效 return stack.isEmpty(); }真题2最小栈LeetCode 155简单高频题目设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。核心思路用两个栈实现一个主栈存储所有元素一个辅助栈存储当前栈中的最小元素push主栈正常入栈辅助栈入栈“当前最小元素”若辅助栈为空或新元素小于等于辅助栈顶元素入栈新元素否则入栈辅助栈顶元素。pop主栈和辅助栈同时出栈保证辅助栈顶始终是当前主栈的最小元素。getMin直接返回辅助栈顶元素时间复杂度O(1)。真题3栈的压入、弹出序列剑指Offer 31中等题目输入两个整数序列第一个序列表示栈的压入顺序请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。核心思路用一个辅助栈模拟压入、弹出过程遍历压入序列依次入栈每次入栈后判断栈顶元素是否与弹出序列当前元素一致一致则出栈直到不匹配遍历结束后若栈为空则弹出序列有效。二、队列Queue先进先出面试高频1. 队列的定义与核心特性面试必背队列是一种遵循“先进先出”FIFOFirst In First Out规则的线性数据结构。简单来说就是“先放进去的元素先取出来”就像我们平时排队买票先排队的人先买票后排队的人后买票不能插队。面试重点记住“先进先出”这个核心特性与栈的“先进后出”形成对比这是面试中常考的区别题。队列的两个核心操作面试必记入队offer/enqueue将元素添加到队列的尾部队尾时间复杂度O(1)。出队poll/dequeue将队列头部队头的元素删除并返回该元素时间复杂度O(1)。补充队列的常用操作还有 peek查看队头元素不删除时间复杂度O(1)队列同样不支持随机访问只能访问队头元素。2. 队列的底层实现面试高频追问队列的底层实现也有两种方式基于数组和链表其中基于链表的实现更常用面试时需重点掌握实现方式1基于数组实现顺序队列用数组作为底层存储容器定义两个指针队头指针指向队头元素、队尾指针指向队尾元素的下一个位置初始时两者都为0。入队将元素存入队尾指针指向的位置队尾指针加1。出队取出队头指针指向的元素队头指针加1。问题数组容量固定当队尾指针达到数组长度时即使数组前面有空闲空间也无法入队假溢出。解决方法采用“循环队列”将数组首尾相连当队尾指针达到数组长度时判断队头是否有空闲空间若有则队尾指针归零解决假溢出问题。实现方式2基于链表实现链式队列用单链表作为底层存储容器定义两个指针队头指针指向链表头节点、队尾指针指向链表尾节点初始时两者都为null。入队将新节点作为尾节点插入链表队尾指针指向新节点若队列为空队头指针也指向新节点。出队删除头节点队头指针指向头节点的下一个节点若出队后队列为空队尾指针也置为null。优点容量动态无溢出问题入队、出队操作简单缺点访问速度比顺序队列慢但实际开发中更常用无需考虑扩容和假溢出。3. 队列的面试高频真题必练校招/社招通用队列的面试题核心考察“先进先出”特性的应用常与栈结合考察以下3道真题覆盖高频考点建议重点掌握真题1用栈实现队列LeetCode 232简单必练题目请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty。核心思路用两个栈入栈和出栈实现利用栈“先进后出”的特性将入栈的元素反转实现“先进先出”push将元素压入入栈。pop/peek若出栈为空将入栈的所有元素弹出并压入出栈此时出栈的栈顶就是队列的队头再从出栈弹出或查看元素。empty入栈和出栈都为空则队列为空。代码示例Javaclass MyQueue { // 入栈存储待入队的元素 private StackInteger inStack; // 出栈存储待出队的元素反转后的元素 private StackInteger outStack; public MyQueue() { inStack new Stack(); outStack new Stack(); } // 入队 public void push(int x) { inStack.push(x); } // 出队 public int pop() { // 若出栈为空将入栈元素全部转入出栈 if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.pop(); } // 查看队头元素 public int peek() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.peek(); } // 判断队列是否为空 public boolean empty() { return inStack.isEmpty() outStack.isEmpty(); } }真题2用队列实现栈LeetCode 225简单题目请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop、empty。核心思路用两个队列主队列和辅助队列实现每次入队后将主队列的前n-1个元素转入辅助队列让新入队的元素成为主队列的队头模拟栈顶出队时直接取出主队列的队头元素。真题3滑动窗口最大值LeetCode 239困难社招高频题目给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。核心思路用“单调队列”队列内元素单调递减实现队列存储的是元素的下标而非元素本身保证队列头始终是当前滑动窗口的最大值下标时间复杂度O(n)。三、栈与队列核心区别面试必问背会直接用栈和队列的区别是算法面试中基础且常考的题目结合我们上一篇学的数组、链表对比掌握面试时直接应答对比维度栈Stack队列Queue核心特性先进后出LIFO先进先出FIFO核心操作入栈push、出栈pop、peek栈顶入队offer、出队poll、peek队头底层实现数组顺序栈、链表链式栈数组循环队列、链表链式队列访问方式只能访问栈顶元素只能访问队头元素应用场景括号匹配、表达式求值、递归调用排队场景、滑动窗口、广度优先搜索BFS以上就是栈与队列的核心知识点涵盖定义、底层实现、面试真题和核心区别都是面试必考点。需要重点注意的是栈和队列的底层实现依赖数组和链表一定要结合上一篇的内容融会贯通这样才能更好地理解它们的特性和应用。另外栈和队列常结合考察如用栈实现队列、用队列实现栈这类题目是面试中的基础题一定要动手写代码掌握实现逻辑。下一篇我们将学习《哈希表底层实现哈希函数、冲突解决 真题解析》继续夯实基础数据结构敬请期待