Java 棧與隊列排序算法實作

前言

受限於「僅能使用一個輔助棧/隊列及少量變數」的條件下對棧/隊列排序，是經典面試題。本文提供兩種基於 LinkedList 的實作：雙棧選擇排序與單隊列選擇排序，並分析時間複雜度。

一、棧排序：雙棧交替選擇排序

算法邏輯

1. 初始數據全在 stackOne，stackTwo 為空。
2. 輪流從當前「源棧」彈出所有待排元素，找出最大值 max，其餘推入「目標棧」。
3. 將 max 推回源棧（此為已排序區域底部）。
4. 角色互換：目標棧變源棧，繼續找次大值。
5. 直到某棧待排元素剩 1 個（另棧為 0），排序完成。
6. 輸出時，兩棧交替彈出（大→小→次大→次小...）。

代碼實作

public class StackSort {
    private IntStack stackOne, stackTwo;
    private int size;
    private static final int START_ONE=1, START_TWO=2;

    public StackSort(int[] arr) {
        stackOne=new IntStack(); stackTwo=new IntStack();
        for(int v:arr){ stackOne.push(v); size++; }
    }

    public int sort() {
        int sizeOne=size, sizeTwo=0;
        while (sizeOne!=1 && sizeTwo!=1) {
            // 從 stackOne 找最大
            int max = stackOne.pop(); sizeOne--;
            while (sizeOne>0) {
                int v = stackOne.pop();
                if (v>max){ stackTwo.push(max); max=v; }
                else stackTwo.push(v);
                sizeOne--; sizeTwo++;
            }
            stackOne.push(max); // 最大值歸位
            if (sizeTwo==1) return START_TWO;

            // 從 stackTwo 找次大
            max = stackTwo.pop(); sizeTwo--;
            while (sizeTwo>0) {
                int v = stackTwo.pop();
                if (v>max){ stackOne.push(max); max=v; }
                else stackOne.push(v);
                sizeTwo--; sizeOne++;
            }
            stackTwo.push(max);
        }
        return (sizeOne>sizeTwo)? START_ONE : START_TWO;
    }

    public void printResult(int start) {
        IntStack first = (start==START_ONE)?stackOne:stackTwo;
        IntStack second = (start==START_ONE)?stackTwo:stackOne;
        while (!first.empty() && !second.empty()) {
            System.out.print(first.pop()+" "+second.pop()+" ");
        }
        if (!first.empty()) System.out.print(first.pop());
        System.out.println();
    }
}

複雜度分析

• 時間：O(n²) — 每輪掃描剩餘元素，共 n 輪。
• 空間：O(n) — 兩棧共存 n 元素。
• 穩定性：不穩定（相等元素相對序可能改變）。

二、隊列排序：單輔助隊列選擇排序

算法邏輯

1. 源隊列 queueOne 存放待排數據，目標隊列 queueTwo 為空。
2. 每輪從 queueOne 依序 poll() 所有元素，記錄最大值 max，其餘 offer() 回 queueOne。
3. 將 max offer() 到 queueTwo（隊尾）。
4. 重複直到 queueOne 為空。
5. queueTwo 內元素由大到小排列（先進先出輸出即為降序）。

代碼實作

public class QueueSort {
    private IntQueue queueOne, queueTwo;
    private int size;

    public QueueSort(int[] arr) {
        queueOne=new IntQueue(); queueTwo=new IntQueue();
        for(int v:arr){ queueOne.offer(v); size++; }
    }

    public void sort() {
        int remaining = size;
        while (remaining > 0) {
            int max = queueOne.poll();
            int turn = remaining - 1;
            while (turn > 0) {
                int v = queueOne.poll();
                if (v > max) { queueOne.offer(max); max = v; }
                else queueOne.offer(v);
                turn--;
            }
            queueTwo.offer(max);
            remaining--;
        }
    }

    public void printResult() {
        while (!queueTwo.empty()) System.out.print(queueTwo.poll()+" ");
        System.out.println();
    }
}

複雜度分析

• 時間：O(n²) — 每輪掃描剩餘元素。
• 空間：O(n) — 兩隊列共存 n 元素。
• 適用性：邏輯簡單，適合約瑟夫環類問題（循環隊列特性）。

輔助數據結構

// IntStack 同前
// IntQueue 基於 LinkedList 實作 Queue 介面
public class IntQueue {
    private Queue<Integer> q = new LinkedList<>();
    public void offer(int v) { q.offer(v); }
    public int poll() { return q.poll(); }
    public boolean empty() { return q.isEmpty(); }
}

總結

棧排序利用「雙棧倒騰」模擬選擇排序，隊列排序利用「循環掃描+輔助隊列」同樣實現選擇排序。兩者皆為 O(n²)，教學意義大於實用。實際開發中，將數據倒入 List 呼叫 Collections.sort() (TimSort, O(n log n)) 才是正道。