尧图网页设计 
Hello 算法 栈与队列练习精讲从 LIFO/FIFO 心智模型到环形数组与双向队列的源码级验证【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本文围绕《Hello 算法》“栈与队列”一章的配套练习练习文档展开完整讲解三道知识巩固题栈队列出元素顺序、环形数组取余、双向队列两端操作和一道括号合法性编程题。结合仓库中 基于环形数组的队列实现、基于环形数组的双向队列实现 等源码将每道练习题的关键公式逐一落到真实代码行帮助读者在动手刷题前建立可验证的数据结构直觉。练习题全貌与学习路径练习文档将本章练习分为两部分知识巩固通过纸面推演建立栈、队列、双向队列的操作心智模型共 3 题编程练习用栈实现经典的括号序列合法性判断共 1 题。建议的学习路径是先独立推演前 3 题再对照本文的逐步解析与源码验证最后动手完成编程题。本章的概念基础分别来自 栈、队列、双向队列 三篇文档文末的 小结 还附有 Q A 可作为延伸阅读。练习一栈和队列会先取出谁题目准备一个空栈S和一个空队列Q分别对它们执行同一组操作加入A加入B移除一个元素并记录加入C不断移除并记录直到容器为空。请分别写出S和Q中元素被移除的顺序并用“先入后出”或“先入先出”解释差异。参考答案与逐步推演栈S的移除顺序是B、C、A。逐步状态如下步骤操作栈的状态底 → 顶移除的元素1push A[A]-2push B[A, B]-3pop[A]B4push C[A, C]-5清空[]C然后A加入A、B后先弹出最近加入的B再加入C此后依次弹出C、A体现“先入后出”LIFO。队列Q的移除顺序是A、B、C。逐步状态如下步骤操作队列的状态首 → 尾移除的元素1push A[A]-2push B[A, B]-3pop[B]A4push C[B, C]-5清空[]B然后C加入A、B后先移除最早加入的A再加入C此后依次移除B、C体现“先入先出”FIFO。源码验证这道题的本质是确认“栈只从一端进出、队列从两端分别进出”。仓库中的 数组栈实现 正好体现了这一点push调用self._stack.append(item)pop调用self._stack.pop()两者都只作用于数组尾部这一个位置见 array_stack.py L23-L37因此后进的元素必然先出。而 链表栈 采用头插法实现效果等价。用栈类语言如 Java 的Stack.push()/pop()、C 的std::stack复现这组操作得到的顺序与上表完全一致。练习二队尾越过数组末尾怎么办题目用长度为 5 的环形数组实现队列数组索引为04。当前front 3、size 2队列中的A、B分别位于索引 3、4。执行“C入队”时C应放在哪个索引入队后size是多少接着执行一次出队弹出哪个元素新的front和size分别是多少此时从队首到队尾的逻辑顺序是什么出队时是否需要移动数组中的其他元素为什么参考答案新元素的位置为(front size) % 5 (3 2) % 5 0所以C放在索引 0。入队后size 3。出队弹出当前队首A。新的队首索引为(3 1) % 5 4因此front 4、size 2。有效元素的逻辑顺序为B、C其中B位于索引 4C位于索引 0。出队时只需移动front并修改size环形数组用取余让索引回到开头因此无须把其他元素整体向前移动。源码验证环形数组取余的真实代码这正是 queue.md 中“基于数组的队列实现”的核心设计以front指向队首、size记录长度定义rear front size越过尾部后回绕有效元素区间为[front, rear - 1]。仓库中 array_queue.py 的push与pop逐行对应了题目中的两个公式def push(self, num: int): 入队 if self._size self.capacity(): raise IndexError(队列已满) # 计算队尾指针指向队尾索引 1 # 通过取余操作实现 rear 越过数组尾部后回到头部 rear: int (self._front self._size) % self.capacity() # 将 num 添加至队尾 self._nums[rear] num self._size 1 def pop(self) - int: 出队 num: int self.peek() # 队首指针向后移动一位若越过尾部则返回到数组头部 self._front (self._front 1) % self.capacity() self._size - 1 return num入队公式rear (front size) % capacityarray_queue.py L35与题目中的(3 2) % 5 0完全一致出队公式front (front 1) % capacityarray_queue.py L44与题目中的(3 1) % 5 4完全一致全程只改指针和计数器没有任何元素搬移印证了第 3 小问的结论。此外该文件末尾的 Driver Code 还专门用一轮循环验证了环形回绕行为array_queue.py L94-L98连续执行 10 次“入队 出队”front会在取余作用下不断从索引 4 绕回 0可直接运行观察。需要注意的边界当size capacity时push抛出“队列已满”异常即本实现是固定容量队列文档中也指出若需容量可增长可将定长数组替换为动态数组并引入扩容机制。练习三双向队列的两端操作题目这里规定push_first表示从队首加入push_last表示从队尾加入pop_first表示从队首弹出pop_last表示从队尾弹出。对一个空的双向队列deq依次执行push_last(A)push_last(B)push_first(C)pop_last()push_last(D)pop_first()两次弹出的元素分别是什么全部操作完成后从队首到队尾还剩哪些元素检查这 6 步操作只允许从队尾加入、从队首删除的队列能否全部完成如果不能请指出无法完成的操作再说明双向队列能否完成及其原因。参考答案前三步后双向队列从队首到队尾为[C, A, B]。pop_last()弹出B加入D后队列为[C, A, D]pop_first()再弹出C。最后剩下[A, D]。只允许在队尾添加、在队首删除的队列不能完成全部操作第 3 步push_first(C)要求从队首加入第 4 步pop_last()要求从队尾删除都超出了这种队列的操作范围。双向队列的两端都可以添加和删除因此能够完成这 6 步操作。完整推演表如下步骤操作队列状态首 → 尾弹出值1push_last(A)[A]-2push_last(B)[A, B]-3push_first(C)[C, A, B]-4pop_last()[C, A]B5push_last(D)[C, A, D]-6pop_first()[A, D]C源码验证环形数组如何支持两端操作这道题的四个操作在 array_deque.py 中都有对应实现。与队列实现的关键差异是双向队列需要一个能处理负数索引的取余函数def index(self, i: int) - int: 计算环形数组索引 # 通过取余操作实现数组首尾相连 # 当 i 越过数组尾部后回到头部 # 当 i 越过数组头部后回到尾部 return (i self.capacity()) % self.capacity()array_deque.py L29-L34 self.capacity()保证当push_first使front越过数组头部front - 1变成负数时取余结果仍能回到尾部。四个操作的指针变化分别是push_first先执行self._front self.index(self._front - 1)再写入元素L36-L46——对应题目第 3 步C被插入到A之前push_lastrear self.index(self._front self._size)后写入L48-L57pop_firstself._front self.index(self._front 1)L59-L65pop_last仅将size减 1因为队尾元素索引恒为index(front size - 1)L67-L71。仓库还提供了基于双向链表的另一种实现 linkedlist_deque.pypush(num, is_front)与pop(is_front)两个统一方法通过布尔参数区分端点队首入队时维护node.next / front.prev队尾入队时维护rear.next / node.prevL35-L53与 deque.md 中“双向链表两端增删”的图示流程一致。两种实现的对比结论与队列相同数组实现缓存局部性好、扩容可能触发O(n)的一次性开销链表实现效率更稳定但节点携带额外指针。编程练习检查括号序列题目给定一个只包含()、[]、{}这三类括号的字符串s请使用栈判断它是否合法。合法序列须同时满足每个右括号都必须与最近一个尚未配对的左括号类型匹配并且遍历结束后没有未配对的左括号。返回布尔值表示判断结果。解题提示可以建立“右括号到对应左括号”的映射遇到右括号时先检查栈是否为空再检查栈顶是否匹配遍历结束后栈也必须为空。本题对应 LeetCode 的“Valid Parentheses”有效的括号题目原文档附有线上平台与题目解析的入口链接。参考实现结合本章知识用 ArrayStack 即可实现。核心逻辑与仓库栈实现一一对应遇到左括号push入栈遇到右括号用peek检查栈顶类型后pop配对def is_valid(s: str) - bool: 判断括号序列是否合法 # 右括号 - 对应左括号 的映射提示 1 pairs {): (, ]: [, }: {} stack: list[str] [] for ch in s: if ch in pairs.values(): # 左括号入栈 stack.append(ch) else: # 右括号出栈配对 # 提示 2先判空再判栈顶是否匹配 if not stack or stack.pop() ! pairs[ch]: return False # 提示 3遍历结束后栈必须为空 return len(stack) 0三个边界情况各对应一条判据缺一不可右括号无左括号可配如)(中第一个字符就是右括号此时栈为空若直接访问栈顶会越界因此必须先判空类型不匹配如(]栈顶是(却遇到了]pop后比较不相等即返回False遍历后仍有剩余如(((所有右括号都配平了但栈中残留左括号最终len(stack) ! 0返回False。时间复杂度 $O(n)$每个字符最多一次入栈、一次出栈栈操作均为 $O(1)$空间复杂度 $O(n)$最坏情况全为左括号。也可以改用各语言内置容器——如 Python 的list、C 的std::stack、Java 的Stack——替代自建栈效果等价这正是 stack.md 中“把数组/内置类当作栈使用”的推荐做法。延伸本章练习可对照的仓库源码完成练习后建议通读以下多语言实现观察同一逻辑在不同语言中的表达差异栈Python 数组栈、Python 链表栈队列Python 环形数组队列、Python 链表队列双向队列Python 环形数组双向队列、Python 双向链表双向队列概念与图示文档栈、队列、双向队列章节要点回顾与 Q A小结。另外deque.md 末尾的“撤销步数上限”案例值得结合练习三理解当撤销栈长度超过上限时需要从栈底删除元素普通栈无法完成这正是双向队列pop_first的用途——linkedlist_deque.py 的pop_first方法可直接复用在该场景中。小结本章练习以三道纸面推演题加一道编程题覆盖了“栈与队列”一章的三个关键认知点顺序差异源于端点规则栈两端合一顶队列两端分离首、尾LIFO 与 FIFO 的顺序差异可直接从操作序列推演得出环形数组用取余代替搬移(front size) % capacity决定了入队位置(front 1) % capacity完成出队全程 $O(1)$ 且不移动任何元素双向队列补齐两端对称操作push_first需要“负方向”取余(i capacity) % capacity这是环形数组实现双向队列比实现普通队列多出的唯一难点栈的经典应用括号匹配是“最近未配对项优先”问题的标准解法判空、判类型、判剩余三条判据对应三种非法形态。按“先推演、再对代码、后写程序”的顺序完成这套练习即可把本章的概念性知识固化为可直接落地的实现能力。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello 算法 栈与队列练习精讲：从 LIFO/FIFO 心智模型到环形数组与双向队列的源码级验证
Hello 算法 栈与队列练习精讲从 LIFO/FIFO 心智模型到环形数组与双向队列的源码级验证【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本文围绕《Hello 算法》“栈与队列”一章的配套练习练习文档展开完整讲解三道知识巩固题栈队列出元素顺序、环形数组取余、双向队列两端操作和一道括号合法性编程题。结合仓库中 基于环形数组的队列实现、基于环形数组的双向队列实现 等源码将每道练习题的关键公式逐一落到真实代码行帮助读者在动手刷题前建立可验证的数据结构直觉。练习题全貌与学习路径练习文档将本章练习分为两部分知识巩固通过纸面推演建立栈、队列、双向队列的操作心智模型共 3 题编程练习用栈实现经典的括号序列合法性判断共 1 题。建议的学习路径是先独立推演前 3 题再对照本文的逐步解析与源码验证最后动手完成编程题。本章的概念基础分别来自 栈、队列、双向队列 三篇文档文末的 小结 还附有 Q A 可作为延伸阅读。练习一栈和队列会先取出谁题目准备一个空栈S和一个空队列Q分别对它们执行同一组操作加入A加入B移除一个元素并记录加入C不断移除并记录直到容器为空。请分别写出S和Q中元素被移除的顺序并用“先入后出”或“先入先出”解释差异。参考答案与逐步推演栈S的移除顺序是B、C、A。逐步状态如下步骤操作栈的状态底 → 顶移除的元素1push A[A]-2push B[A, B]-3pop[A]B4push C[A, C]-5清空[]C然后A加入A、B后先弹出最近加入的B再加入C此后依次弹出C、A体现“先入后出”LIFO。队列Q的移除顺序是A、B、C。逐步状态如下步骤操作队列的状态首 → 尾移除的元素1push A[A]-2push B[A, B]-3pop[B]A4push C[B, C]-5清空[]B然后C加入A、B后先移除最早加入的A再加入C此后依次移除B、C体现“先入先出”FIFO。源码验证这道题的本质是确认“栈只从一端进出、队列从两端分别进出”。仓库中的 数组栈实现 正好体现了这一点push调用self._stack.append(item)pop调用self._stack.pop()两者都只作用于数组尾部这一个位置见 array_stack.py L23-L37因此后进的元素必然先出。而 链表栈 采用头插法实现效果等价。用栈类语言如 Java 的Stack.push()/pop()、C 的std::stack复现这组操作得到的顺序与上表完全一致。练习二队尾越过数组末尾怎么办题目用长度为 5 的环形数组实现队列数组索引为04。当前front 3、size 2队列中的A、B分别位于索引 3、4。执行“C入队”时C应放在哪个索引入队后size是多少接着执行一次出队弹出哪个元素新的front和size分别是多少此时从队首到队尾的逻辑顺序是什么出队时是否需要移动数组中的其他元素为什么参考答案新元素的位置为(front size) % 5 (3 2) % 5 0所以C放在索引 0。入队后size 3。出队弹出当前队首A。新的队首索引为(3 1) % 5 4因此front 4、size 2。有效元素的逻辑顺序为B、C其中B位于索引 4C位于索引 0。出队时只需移动front并修改size环形数组用取余让索引回到开头因此无须把其他元素整体向前移动。源码验证环形数组取余的真实代码这正是 queue.md 中“基于数组的队列实现”的核心设计以front指向队首、size记录长度定义rear front size越过尾部后回绕有效元素区间为[front, rear - 1]。仓库中 array_queue.py 的push与pop逐行对应了题目中的两个公式def push(self, num: int): 入队 if self._size self.capacity(): raise IndexError(队列已满) # 计算队尾指针指向队尾索引 1 # 通过取余操作实现 rear 越过数组尾部后回到头部 rear: int (self._front self._size) % self.capacity() # 将 num 添加至队尾 self._nums[rear] num self._size 1 def pop(self) - int: 出队 num: int self.peek() # 队首指针向后移动一位若越过尾部则返回到数组头部 self._front (self._front 1) % self.capacity() self._size - 1 return num入队公式rear (front size) % capacityarray_queue.py L35与题目中的(3 2) % 5 0完全一致出队公式front (front 1) % capacityarray_queue.py L44与题目中的(3 1) % 5 4完全一致全程只改指针和计数器没有任何元素搬移印证了第 3 小问的结论。此外该文件末尾的 Driver Code 还专门用一轮循环验证了环形回绕行为array_queue.py L94-L98连续执行 10 次“入队 出队”front会在取余作用下不断从索引 4 绕回 0可直接运行观察。需要注意的边界当size capacity时push抛出“队列已满”异常即本实现是固定容量队列文档中也指出若需容量可增长可将定长数组替换为动态数组并引入扩容机制。练习三双向队列的两端操作题目这里规定push_first表示从队首加入push_last表示从队尾加入pop_first表示从队首弹出pop_last表示从队尾弹出。对一个空的双向队列deq依次执行push_last(A)push_last(B)push_first(C)pop_last()push_last(D)pop_first()两次弹出的元素分别是什么全部操作完成后从队首到队尾还剩哪些元素检查这 6 步操作只允许从队尾加入、从队首删除的队列能否全部完成如果不能请指出无法完成的操作再说明双向队列能否完成及其原因。参考答案前三步后双向队列从队首到队尾为[C, A, B]。pop_last()弹出B加入D后队列为[C, A, D]pop_first()再弹出C。最后剩下[A, D]。只允许在队尾添加、在队首删除的队列不能完成全部操作第 3 步push_first(C)要求从队首加入第 4 步pop_last()要求从队尾删除都超出了这种队列的操作范围。双向队列的两端都可以添加和删除因此能够完成这 6 步操作。完整推演表如下步骤操作队列状态首 → 尾弹出值1push_last(A)[A]-2push_last(B)[A, B]-3push_first(C)[C, A, B]-4pop_last()[C, A]B5push_last(D)[C, A, D]-6pop_first()[A, D]C源码验证环形数组如何支持两端操作这道题的四个操作在 array_deque.py 中都有对应实现。与队列实现的关键差异是双向队列需要一个能处理负数索引的取余函数def index(self, i: int) - int: 计算环形数组索引 # 通过取余操作实现数组首尾相连 # 当 i 越过数组尾部后回到头部 # 当 i 越过数组头部后回到尾部 return (i self.capacity()) % self.capacity()array_deque.py L29-L34 self.capacity()保证当push_first使front越过数组头部front - 1变成负数时取余结果仍能回到尾部。四个操作的指针变化分别是push_first先执行self._front self.index(self._front - 1)再写入元素L36-L46——对应题目第 3 步C被插入到A之前push_lastrear self.index(self._front self._size)后写入L48-L57pop_firstself._front self.index(self._front 1)L59-L65pop_last仅将size减 1因为队尾元素索引恒为index(front size - 1)L67-L71。仓库还提供了基于双向链表的另一种实现 linkedlist_deque.pypush(num, is_front)与pop(is_front)两个统一方法通过布尔参数区分端点队首入队时维护node.next / front.prev队尾入队时维护rear.next / node.prevL35-L53与 deque.md 中“双向链表两端增删”的图示流程一致。两种实现的对比结论与队列相同数组实现缓存局部性好、扩容可能触发O(n)的一次性开销链表实现效率更稳定但节点携带额外指针。编程练习检查括号序列题目给定一个只包含()、[]、{}这三类括号的字符串s请使用栈判断它是否合法。合法序列须同时满足每个右括号都必须与最近一个尚未配对的左括号类型匹配并且遍历结束后没有未配对的左括号。返回布尔值表示判断结果。解题提示可以建立“右括号到对应左括号”的映射遇到右括号时先检查栈是否为空再检查栈顶是否匹配遍历结束后栈也必须为空。本题对应 LeetCode 的“Valid Parentheses”有效的括号题目原文档附有线上平台与题目解析的入口链接。参考实现结合本章知识用 ArrayStack 即可实现。核心逻辑与仓库栈实现一一对应遇到左括号push入栈遇到右括号用peek检查栈顶类型后pop配对def is_valid(s: str) - bool: 判断括号序列是否合法 # 右括号 - 对应左括号 的映射提示 1 pairs {): (, ]: [, }: {} stack: list[str] [] for ch in s: if ch in pairs.values(): # 左括号入栈 stack.append(ch) else: # 右括号出栈配对 # 提示 2先判空再判栈顶是否匹配 if not stack or stack.pop() ! pairs[ch]: return False # 提示 3遍历结束后栈必须为空 return len(stack) 0三个边界情况各对应一条判据缺一不可右括号无左括号可配如)(中第一个字符就是右括号此时栈为空若直接访问栈顶会越界因此必须先判空类型不匹配如(]栈顶是(却遇到了]pop后比较不相等即返回False遍历后仍有剩余如(((所有右括号都配平了但栈中残留左括号最终len(stack) ! 0返回False。时间复杂度 $O(n)$每个字符最多一次入栈、一次出栈栈操作均为 $O(1)$空间复杂度 $O(n)$最坏情况全为左括号。也可以改用各语言内置容器——如 Python 的list、C 的std::stack、Java 的Stack——替代自建栈效果等价这正是 stack.md 中“把数组/内置类当作栈使用”的推荐做法。延伸本章练习可对照的仓库源码完成练习后建议通读以下多语言实现观察同一逻辑在不同语言中的表达差异栈Python 数组栈、Python 链表栈队列Python 环形数组队列、Python 链表队列双向队列Python 环形数组双向队列、Python 双向链表双向队列概念与图示文档栈、队列、双向队列章节要点回顾与 Q A小结。另外deque.md 末尾的“撤销步数上限”案例值得结合练习三理解当撤销栈长度超过上限时需要从栈底删除元素普通栈无法完成这正是双向队列pop_first的用途——linkedlist_deque.py 的pop_first方法可直接复用在该场景中。小结本章练习以三道纸面推演题加一道编程题覆盖了“栈与队列”一章的三个关键认知点顺序差异源于端点规则栈两端合一顶队列两端分离首、尾LIFO 与 FIFO 的顺序差异可直接从操作序列推演得出环形数组用取余代替搬移(front size) % capacity决定了入队位置(front 1) % capacity完成出队全程 $O(1)$ 且不移动任何元素双向队列补齐两端对称操作push_first需要“负方向”取余(i capacity) % capacity这是环形数组实现双向队列比实现普通队列多出的唯一难点栈的经典应用括号匹配是“最近未配对项优先”问题的标准解法判空、判类型、判剩余三条判据对应三种非法形态。按“先推演、再对代码、后写程序”的顺序完成这套练习即可把本章的概念性知识固化为可直接落地的实现能力。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考