题目
使用两个栈（一个无序栈和一个空栈）将无序栈中的元素转移到空栈，使其有序，不允许使用其他数据结构。
示例：输入：[3, 1, 6, 4, 2, 5]，输出：[6, 5, 4, 3, 2, 1]
思路与代码
如果不限制使用其他数据结构，大可以直接全部输出到数组里面然后快速排序(bushi)
但是这道题目不允许使用其他数据结构，那么只能用原来的无序栈保存不能压入有序栈的元素。
-
从
stack1弹出元素temp，并将stack2中所有比temp小的元素移回stack1。 -
将
temp压入stack2，确保stack2始终降序。 -
此时，被移回stack1中的元素一定小于temp，不满足判断条件，所以将依次执行temp = stack1.pop()和stack2.append(temp)
读者可以模拟插入排序的过程来理解本题，下面的代码展示的是降序排列的过程：
def sort_stack(stack1):stack2 = []# 将stack1中的元素按降序插入stack2（从栈底到栈顶）while stack1:temp = stack1.pop()# 将stack2中比temp小的元素移回stack1while stack2 and stack2[-1] < temp: # 当栈2不为空且栈2的栈顶元素小于tempstack1.append(stack2.pop())stack2.append(temp)print(stack2)return stack2sort_stack([3, 1, 6, 4, 2, 5])
# [6, 5, 4, 3, 2, 1]若要改为升序排列，只需将判断条件改为stack2[-1] > temp：
def sort_stack(stack1):stack2 = []# 将stack1中的元素按升序插入stack2（从栈底到栈顶）while stack1:temp = stack1.pop()# 将stack2中比temp大的元素移回stack1while stack2 and stack2[-1] > temp: # 当栈2不为空且栈2的栈顶元素大于tempstack1.append(stack2.pop())stack2.append(temp)print(stack2)return stack2sort_stack([3, 1, 6, 4, 2, 5])
# [1, 2, 3, 4, 5, 6]
