C/C++ 棧與隊列實戰應用：進制轉換、表達式求值與舞伴配對

棧的應用場景一：數制轉換

利用除基取餘法配合棧的後進先出特性，將十進制轉為任意進制。餘數先產生為低位，入棧後出棧即為正確順序。

void conversion(int N, int B) {
    stack S;
    while (N) {
        S.push(N % B);
        N /= B;
    }
    while (!S.empty()) {
        printf("%d", S.top());
        S.pop();
    }
}

棧的應用場景二：表達式求值（算符優先法）

維護兩個棧：運算符棧 OPTR 和 操作數棧 OPND。根據運算符優先級關係（<、>、=）決定移入、歸約或脫括號。

優先級表

核心邏輯

• 操作數直接入 OPND
• 運算符與棧頂比較：
  li><：當前運算符優先級高，入 OPTR
  • >：棧頂優先級高，從 OPTR 彈出運算符，從 OPND 彈出兩操作數，計算後結果入 OPND
  • =：匹配括號，彈出 '('
• 直到表達式結束符 '#' 與棧頂均為 '#' 時結束

隊列的應用場景：舞伴配對問題

男女分別排隊，隊頭配對出隊。若人數不等，長隊剩餘者等待下一輪。典型的先進先出（FIFO）場景。

void DancePartner(Person dancer[], int num) {
    queue Mdancers, Fdancers;
    for (int i = 0; i < num; i++) {
        if (dancer[i].sex == 'F') Fdancers.push(dancer[i]);
        else Mdancers.push(dancer[i]);
    }
    while (!Fdancers.empty() && !Mdancers.empty()) {
        Person f = Fdancers.front(); Fdancers.pop();
        Person m = Mdancers.front(); Mdancers.pop();
        printf("%s %s\n", f.name, m.name);
    }
    // 輸出剩餘等待者信息...
}

數據結構選擇指南

棧解決「最後處理最先到達」的問題，隊列解決「最先處理最先到達」的問題，是算法設計中最基礎也最強大的兩種線性結構。