本題源自左神《程序員面試代碼指南》“用一個棧實現另一個棧的排序”題目。

題目

在一個棧中元素的類型為整型，現在想將該棧從棧頂到棧底按從大到小的順序排序，只許申請一個棧，除此之外，可以申請其他變量，但是不能申請額外的數據結構。

解答

將待排序的棧記為 stack， 輔助棧記為 help。 在 stack 上執行 pop 操作，彈出的元素記為 cur。

• 如果 cur 小于等于 help 的棧頂元素，則將 cur 直接壓入 help
• 如果 cur 大于 help 的棧頂元素，則將 help 的元素逐一彈出，逐一壓入 stack，直到 cur 小于或等于 help 的棧頂元素，再將 cur 壓入 help

一直執行以上操作，直到 stack 中的全部元素都壓入到 help 棧中（此時從棧頂到棧底：有小到大），最后將help棧中的元素逐一壓入stack，即可完成排序。

代碼

import java.util.Stack;public class Main {public static void sortStackByStack(Stack<Integer> stack) {Stack<Integer> help = new Stack<Integer>();while (!stack.isEmpty()) {int cur = stack.pop();while (!help.isEmpty() && help.peek() < cur) {stack.push(help.pop());}help.push(cur);}while (!help.isEmpty()) {stack.push(help.pop());}}public static void main(String[] args) {Stack<Integer> stack = new Stack<Integer>();stack.push(3);stack.push(1);stack.push(6);stack.push(2);stack.push(5);stack.push(4);sortStackByStack(stack);System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());} }

輸出：

6 5 4 3 2 1

總結

以上是生活随笔為你收集整理的左神算法：用一个栈实现另一个栈的排序（Java版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。