数据结构栈和队列经典习题解析

数据结构栈和队列经典习题解析在计算机科学的广阔领域中，数据结构是构建高效算法的基石。栈与队列作为两种基础且应用广泛的线性数据结构，其“先进后出”与“先进先出”的特性，为解决许多实际问题提供了清晰而高效的思路。深入理解并灵活运用栈与队列，不仅能够提升代码的质量与效率，更能培养我们抽象建模和解决复杂问题的能力。本文将围绕栈和队列的经典习题展开，通过对具体问题的剖析，阐述其内在的解题思想与方法，希望能为读者提供有益的参考。栈的经典习题解析栈，以其独特的“先进后出”（LIFO）特性，在解决诸如括号匹配、表达式求值、函数调用等问题时展现出得天独厚的优势。1.有效的括号题目描述：给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。思路解析：这道题是栈应用的入门经典。我们可以这样思考：遍历字符串中的每个字符，当遇到左括号（如'(','{','['）时，我们将其压入栈中。这是因为我们需要记住这些左括号，以便后续出现的右括号能够与之匹配。当遇到右括号时，我们需要检查栈顶元素是否为对应的左括号。如果是，则将栈顶元素弹出，表示匹配成功；如果不是，或者栈已经为空（意味着没有对应的左括号），则该字符串无效。遍历结束后，如果栈为空，说明所有左括号都找到了匹配的右括号，字符串有效；否则，无效。示例分析：考虑字符串"()[]{}"。遍历过程如下：'('入栈，栈：['(']')'出现，栈顶为'(',匹配，出栈，栈为空。'['入栈，栈：['[']']'出现，栈顶为'[',匹配，出栈，栈为空。'{'入栈，栈：['{']'}'出现，栈顶为'{',匹配，出栈，栈为空。遍历结束，栈为空，故有效。再如字符串"([)]"：'('入栈，栈：['(']'['入栈，栈：['(','[']')'出现，栈顶为'[',不匹配，故无效。代码实现思路：可以使用一个哈希表来存储右括号与对应左括号的映射关系，如`{')':'(',']':'[','}':'{'}`。然后初始化一个栈。遍历字符串，对每个字符：若为左括号，则入栈。若为右括号，则检查栈是否为空或栈顶元素是否为其对应的左括号。若否，返回false。若是，弹出栈顶元素。遍历结束后，返回栈是否为空的判断结果。思考与拓展：该问题的变种可能包括包含其他类型的括号，或者在括号之间夹杂其他字符。解决思路类似，只需在遍历时分清哪些是括号字符，并对括号字符进行相应处理即可。2.用栈实现队列题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。思路解析：队列的特性是“先进先出”，而栈是“先进后出”。要想用栈实现队列，关键在于如何将栈的“先进后出”特性转换为队列的“先进先出”。我们可以使用两个栈，一个作为“输入栈”（stackIn），专门用于接收新元素；另一个作为“输出栈”（stackOut），专门用于提供元素（pop和peek操作）。push操作：直接将元素压入stackIn。pop/peek操作：如果stackOut为空，则将stackIn中的所有元素依次弹出并压入stackOut。此时，stackOut的栈顶元素就是最早进入队列的元素，可以直接弹出（pop）或查看（peek）。如果stackOut不为空，则直接操作stackOut的栈顶元素。empty操作：当两个栈都为空时，队列才为空。示例分析：假设我们依次push1,2,3。push(1):stackIn=[1]push(2):stackIn=[1,2]push(3):stackIn=[1,2,3]此时执行pop():stackOut为空，将stackIn中所有元素弹出并压入stackOut。stackIn变为空，stackOut=[3,2,1]。弹出stackOut栈顶元素1，stackOut=[3,2]。这就是队列的第一个元素。再执行peek()，返回stackOut栈顶元素2。再执行push(4):stackIn=[4]。执行pop():直接弹出stackOut栈顶元素2，stackOut=[3]。代码实现思路：定义两个栈stackIn和stackOut。push(x)：将x压入stackIn。pop()：若stackOut为空，则将stackIn所有元素弹出并压入stackOut。然后弹出stackOut的栈顶元素并返回。peek()：类似pop()，但只返回stackOut的栈顶元素，不弹出。empty()：返回stackIn和stackOut是否都为空。思考与拓展：这个问题考察了对栈和队列特性的深刻理解和灵活运用。类似地，也可以用两个队列实现一个栈。思考一下，如何用两个队列实现栈呢？（提示：始终保持一个队列为空，入队时加入非空队列；出队时，将非空队列的n-1个元素移到另一个空队列，然后弹出剩下的那个元素。）3.逆波兰表达式求值题目描述：根据逆波兰表示法，求表达式的值。有效的算符包括+、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。注意，两个整数之间的除法只保留整数部分。思路解析：逆波兰表达式（后缀表达式）的特点是运算符位于操作数之后。这种表达式的求值非常适合用栈来实现。其基本思路是：遍历逆波兰表达式的每个元素：如果当前元素是数字，则将其入栈。如果当前元素是运算符，则从栈中弹出两个元素，第一个弹出的是右操作数，第二个弹出的是左操作数，然后进行相应的运算，并将运算结果压入栈中。遍历结束后，栈中只剩下一个元素，即为该逆波兰表达式的值。示例分析：例如，逆波兰表达式["2","1","+","3","*"]对应的中缀表达式为((2+1)*3)=9。求值过程："2"入栈，栈：[2]"1"入栈，栈：[2,1]"+"出栈1和2，计算2+1=3，结果3入栈，栈：[3]"3"入栈，栈：[3,3]"*"出栈3和3，计算3*3=9，结果9入栈，栈：[9]遍历结束，栈顶元素9即为结果。再如["4","13","5","/","+"]，对应中缀表达式(4+(13/5))=4+2=6。求值过程："4"入栈，[4]"13"入栈，[4,13]"5"入栈，[4,13,5]"/"出栈5和13，计算13/5=2（整数除法），入栈[4,2]"+"出栈2和4，计算4+2=6，入栈[6]。结果为6。代码实现思路：初始化一个栈。遍历tokens数组：对于每个token，判断其是否为运算符。若是数字（可以通过是否为运算符来反推，或者尝试转换为整数），则将其转换为整数后入栈。若是运算符，则弹出栈顶的两个元素（注意顺序，后弹出的是左操作数），进行运算，并将结果入栈。遍历结束后，栈顶元素即为结果。需要注意除法的方向和整数除法的取整规则（通常是向零取整）。思考与拓展：逆波兰表达式的优势在于它不需要括号来标识运算的优先级，计算机可以直接利用栈进行高效求值。这个问题的核心在于理解逆波兰表达式的求值规则，并正确运用栈来管理操作数和中间结果。队列的经典习题解析队列的“先进先出”特性使其在处理顺序相关的问题时非常有用，例如广度优先搜索、任务调度、缓存等场景。1.用队列实现栈题目描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop、empty）。思路解析：与用栈实现队列类似，用队列实现栈的关键在于如何模拟栈的“后入先出”特性。我们可以使用两个队列（queue1和queue2），或者甚至可以只使用一个队列来实现。方法一（双队列）：push操作：将元素加入到非空的那个队列中（如果都为空，则加入queue1）。pop操作：假设queue1是非空队列，我们将queue1中除了最后一个元素之外的所有元素都移动到queue2中。然后弹出并返回queue1中剩下的那个元素。之后，交换queue1和queue2的角色，使得下一次操作时queue1仍然是非空队列（如果有的话）。top操作：与pop操作类似，只是在获取到最后一个元素后，不是弹出它，而是将它也移动到queue2中，并返回该元素的值。或者，可以直接返回非空队列的队尾元素（如果队列支持查看队尾元素的操作）。empty操作：判断两个队列是否都为空。方法二（单队列）：push操作：将元素直接加入队列。pop操作：获取当前队列的长度size。然后将队列中前size-1个元素依次出队并重新入队。此时，队列的front元素就是原来的队尾元素（即栈顶元素），将其出队并返回。这种方法更为巧妙，利用了队列自身的循环特性。示例分析（单队列方法）：push(1):queue=[1]push(2):queue=[1,2]pop():size=2。将前1个元素（1）出队并重新入队，queue变为[2,1]。然后出队front元素2，返回。此时queue=[1]。push(3):queue=[1,3]pop():size=2。将前1个元素（1）出队并重新入队，queue变为[3,1]。出队front元素3，返回。此时queue=[1]。代码实现思路（单队列方法）：初始化一个队列。push(x)：将x加入队列。pop()：获取队列长度size。循环size-1次：将队首元素出队并立即入队。出队并返回队首元素。top()：可以直接返回队列的队尾元素（如果API支持，如Java的LinkedList的getLast()）。或者，执行一次pop()操作，得到结果后，再将该结果push回去。empty()：返回队列是否为空。思考与拓展：比较用栈实现队列和用队列实现栈，能更深刻地理解两种数据结构的本质区别和联系。在资源受限的情况下，如何选择最优的实现方式，是一个值得思考的问题。2.滑动窗口最大值题目描述：给你一个整数数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。请你找出所有滑动窗口里的最大值。思路解析：这是一道非常经典的队列应用题，通常使用双端队列（deque）来高效解决。双端队列允许在队列的两端进行插入和删除操作。我们的目标是维护一个双端队列，使得队列中的元素始终是当前滑动窗口中的最大值候选，并且它们的相对顺序是按照在数组中的位置排列的。具体规则如下：队列中存储的是元素的索引，而不是元素值本身，这样便于判断元素是否已经滑出当前窗口。对于新进入窗口的元素nums[i]：从队列的尾部开始，移除所有小于nums[i]的元素的索引（因为这些元素在当前窗口中，不可能成为最大值，它们会被nums[i]遮挡）。将当前元素的索引i加入队列尾部。同时，检查队列头部的元素索引是否已经小于当前窗口的左边界（i-k+1）。如果是，则将其从队列头部移除，因为它已经不在当前窗口内了。当窗口大小达到k时（即i>=k-1），队列头部的元素索引所对应的nums值就是当前滑动窗口的最大值。示例分析：nums=[1,3,-1,-3,5,3,6,7],k=3。我们逐步分析窗口移动过程中deque的变化和最大值：i=0(nums[0]=1):deque为空，加入0。deque:[0]。窗口未形成。i=1(nums[1]=3):3>nums[0]=1，移除0，加入1。deque:[1]。窗口未形成。i=2(nums[2]=-1):-1<nums[1]=3，直接加入2。deque:[1,2]。窗口形成（[1,3,-1]），max为nums[1]=3。i=3(nums[3]=-3):检查头部：1>=3-3+1=1，有效。-3<nums[2]=-1，加入3。deque:[1,2,3]。窗口[3,-1,-3]，max为nums[1]=3。i=4(nums[4]=5):检查头部：1<4-3+1=2，移除头部1。deque:[2,3]。nums[4]=5>nums[3]=-3，移除3。5>nums[2]=-1，移除2。deque为空，加入4。deque:[4]。窗口[-1,-3,5]，max为nums[4]=5。i=5(nums[5]=3):3<nums[4]=5，加入5。deque:[4,5]。窗口[-3