如何用最少栈实现字符串反转？给定输入输出需多少栈及解释？

1. 如何使用最少数量的栈实现字符串反转？ #

最少需要1个栈，利用栈「后进先出（LIFO）」的特性即可实现：

• 步骤1：遍历字符串的每个字符，依次压入栈中。例如字符串"abcd"，压入后栈内从栈底到栈顶的顺序为a → b → c → d。
• 步骤2：依次弹出栈顶元素，直到栈为空。弹出顺序为d → c → b → a，正好是原字符串的反转结果"dcba"。

2. 输入数组转换所需栈的数量及解释 #

给定输入数组：['r', 'a', 't', 'e', 'a', 't', 'c', 'a', 't']，目标数组：['c', 'a', 't', 'e', 'a', 't', 'r', 'a', 't']，实现该转换最少需要2个栈，详细分析如下：

目标转换分析 #

观察输入和目标数组可知：目标是将输入的前3个元素与后3个元素交换位置，中间3个元素（e,a,t）保持原顺序不变。

具体实现步骤（使用2个栈） #

假设两个栈分别为栈A和栈B：

1. 暂存前6个元素：将输入的前6个元素r,a,t,e,a,t依次压入栈A，栈A从栈底到栈顶的顺序为r → a → t → e → a → t。
2. 输出后3个元素（目标前3位）：将输入的后3个元素c,a,t依次压入栈B，此时栈B从栈底到栈顶为c → a → t。直接弹出栈B所有元素，得到c,a,t，作为目标数组的前3位。
3. 输出中间3个元素（目标中间位）：弹出栈A的后3个元素t,a,e，依次压入栈B，此时栈B从栈底到栈顶为t → a → e。弹出栈B所有元素，得到e,a,t，作为目标数组的中间3位。
4. 输出前3个元素（目标后3位）：弹出栈A剩余的3个元素t,a,r，依次压入栈B，此时栈B从栈底到栈顶为t → a → r。弹出栈B所有元素，得到r,a,t，作为目标数组的后3位。

将三部分结果拼接，恰好得到目标数组。

为什么不能用1个栈？ #

栈的「后进先出」特性会反转压入元素的顺序：

• 若仅用1个栈暂存前3个元素，弹出时会得到t,a,r，与目标需要的r,a,t顺序相反；
• 若暂存中间3个元素，弹出时会得到t,a,e，与目标需要的e,a,t顺序相反。
  因此必须用第二个栈将反转后的元素再次反转，还原为原顺序，所以最少需要2个栈。

内容的提问来源于stack exchange，提问作者Sahil Gupta