C語言棧實現進制轉換：後進先出特性的完美應用

棧實現進制轉換：LIFO特性的教科書級應用

進制轉換中「輸出順序與計算順序相反」的特性，與棧的後進先出(LIFO)結構天然契合。本文提供基於順序棧的完整C語言實現，演示如何將十進制整數轉換為任意進制(2-36)，並深度解析棧在逆序輸出場景中的核心價值。

棧數據結構定義

void ConvertBase(SqStack *stack, unsigned int num, unsigned int base) {
    if (!stack || base < 2 || base > 36) return;
    
    // 特殊情況：0
    if (num == 0) {
        printf("0\n");
        return;
    }
    
    // 核心邏輯：反覆除基取餘，餘數入棧
    while (num > 0) {
        int remainder = num % base;
        Push(stack, remainder);
        num /= base;
    }
    
    // 出棧輸出：自動實現逆序
    printf("十進制 %u 轉 %u 進制結果: ", num, base);
    int digit;
    while (!IsEmpty(stack)) {
        Pop(stack, &digit);
        // 數字0-9輸出字符'0'-'9'，10-35輸出'A'-'Z'
        if (digit < 10) putchar('0' + digit);
        else putchar('A' + digit - 10);
    }
    putchar('\n');
}

完整測試程序

算法複雜度分析

指標
複雜度
說明
時間
O(logbaseN)
每次除基運算減少一位
空間
O(logbaseN)
棧深度等於目標進制位數
棧最大深度
32(32位int二進制)
log₂(2³²) = 32


棧在逆序問題中的通用模式
進制轉換是棧解決「正序處理、逆序輸出」問題的典型代表，同類場景包括：

括號匹配：左括號入棧，遇右括號出棧匹配
表達式求值：中綴轉後綴(逆波蘭表達式)，操作數棧+運算符棧
遞歸模擬：將遞歸調用轉為棧幀管理(如深度優先搜索)
歷史記錄/撤銷功能：操作入棧，撤銷時出棧恢復
瀏覽器前進後退：雙棧實現導航歷史


進階擴展：遞歸版本對比

對比結論：遞歸代碼更簡潔但隱含棧溢出風險(大數轉二進制時)；顯式棧可控性更強，適合嵌入式/受限環境。

實戰優化建議

動態棧：用鏈表實現棧避免固定大小限制
位運算優化：基為2的冪次時用位掩碼和移位替代除模
緩衝區輸出：收集字符到緩衝區一次性輸出，減少I/O調用
錯誤處理：檢查基範圍(2-36)，處理輸入為0的邊界情況


標準庫替代方案

棧實現進制轉換不僅是數據結構教學的經典案例，更展示了「數據結構服務於算法特性」的設計哲學。LIFO特性完美匹配逆序輸出需求，這種「問題特性與結構特性耦合」的思維，是成為優秀程序員的關鍵認知躍遷。