如何在C++中按字母顺序对栈进行排序 新手入门实现问题

现有代码问题说明 #

• 数据未绑定：姓名、姓氏、分数分属三个独立数组/栈，排序时无法保证三者对应关系不会错位，建议先定义结构体封装单条用户数据
• 入栈逻辑错误：当前循环每push1次数据就把整个栈pop清空打印，执行完循环后栈内没有剩余数据可供排序

低复杂度新手友好排序方案 #

这里用辅助栈排序法，逻辑简单易懂，不需要复杂递归，时间复杂度O(n²)，空间复杂度O(n)，完全符合作业要求：
核心逻辑：

1. 维护一个始终保持升序/降序的辅助栈
2. 每次取出原栈的栈顶元素，将辅助栈中所有比当前元素大的元素弹回原栈
3. 将当前元素压入辅助栈
4. 重复上述步骤直到原栈为空，此时辅助栈就是有序栈，再全部导回原栈即可得到排序后的原栈

完整可运行代码 #

#include <iomanip>
#include <iostream>
#include <stack>
#include <string>
using namespace std;

// 封装单条用户数据，保证排序时三者绑定不错位
struct UserInfo {
    string firstName;
    string lastName;
    int score;
    // 重载小于号，按名字字母序排序
    bool operator<(const UserInfo& other) const {
        return firstName < other.firstName;
    }
};

// 栈排序函数：按名字升序排序
void sortStack(stack<UserInfo>& inputStack) {
    stack<UserInfo> tempStack; // 辅助栈，始终保持有序

    while (!inputStack.empty()) {
        // 取出原栈顶元素
        UserInfo current = inputStack.top();
        inputStack.pop();

        // 辅助栈里比当前元素大的都弹回原栈
        while (!tempStack.empty() && current < tempStack.top()) {
            inputStack.push(tempStack.top());
            tempStack.pop();
        }

        // 当前元素放到辅助栈正确位置
        tempStack.push(current);
    }

    // 把辅助栈的有序数据导回原栈
    while (!tempStack.empty()) {
        inputStack.push(tempStack.top());
        tempStack.pop();
    }
}

int main() {
    string Names[] = { "Sam", "John", "Simon", "Sarah", "Mat", "Nick", "Isaac", "Anna", "Daniel", "Aaron", "Jack", "Kathrine" };
    string Surnames[] = { "Williams", "Phoenix", "Johnson", "Khosa", "Jackon", "Roberts", "Wayne", "Mishima", "Rose", "Black", "Mohamed", "Bruckner" };
    int Score[] = { 60, 85, 75, 81, 38, 26, 74, 34, 64, 83, 27, 42 };
    int len = sizeof(Names) / sizeof(Names[0]);

    stack<UserInfo> Stack1;
    // 先把所有数据压入栈
    for (int i = 0; i < len; i++) {
        Stack1.push({Names[i], Surnames[i], Score[i]});
    }

    // 对栈进行排序
    sortStack(Stack1);

    // 打印排序后的结果
    cout << "排序后栈内数据（按名字字母升序）：" << endl;
    while (!Stack1.empty()) {
        UserInfo info = Stack1.top();
        cout << "\t" << setw(10) << info.firstName << " " << setw(15) << info.lastName << "\t分数：" << info.score << endl;
        Stack1.pop();
    }

    return 0;
}

补充说明 #

如果需要按分数或者姓氏排序，只需要修改UserInfo结构体里重载的operator<逻辑即可，不需要改动排序函数的核心代码。

内容的提问来源于stack exchange，提问作者christinec-dev