題目

使用兩個棧（一個無序棧和一個空棧）將無序棧中的元素轉移到空棧，使其有序，不允許使用其他數據結構。

示例：輸入：[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]