基于动态数组的栈类Max函数实现求助：如何获取栈中最大值？

先说说你现有代码的问题：

• while (!Empty())循环里没有弹出元素的操作，会直接陷入无限循环，因为栈永远不会为空。
• 比较max < next的逻辑在循环外面，只会执行一次，根本没遍历栈里的所有元素。
• 就算你在循环里加了Pop操作，遍历完原栈也会被清空，这显然不符合函数的预期——获取最大值不该破坏原栈结构。

针对动态数组实现的栈，有两种靠谱的实现方式：

方法一：直接遍历动态数组的有效元素 #

因为栈用动态数组存储，作为类成员函数你可以直接访问数组和top变量。假设你的top是栈顶元素的索引（比如栈空时top=-1，压入第一个元素后top=0），直接遍历数组的有效元素范围找最大值即可，这种方法效率最高，不会修改原栈。

示例代码：

int Stack::Max() {
    if (Empty()) {
        throw EmptyStack();
    }
    int max_val = array[0]; // 初始化为第一个有效元素
    // 遍历所有有效元素，范围根据你的栈实现调整：如果top是栈顶下一个位置，就改成i < top
    for (int i = 1; i <= top; ++i) {
        if (array[i] > max_val) {
            max_val = array[i];
        }
    }
    return max_val;
}

方法二：用临时栈保存元素，遍历后恢复原栈 #

如果不想直接操作内部数组（比如栈的实现细节需要隐藏），可以用临时栈暂存弹出的元素，遍历找最大值后再把元素压回原栈，保证原栈结构不变。

示例代码：

int Stack::Max() {
    if (Empty()) {
        throw EmptyStack();
    }
    int max_val = Top();
    Stack temp_stack;
    // 弹出原栈所有元素，存入临时栈并同步更新最大值
    while (!Empty()) {
        int current = Top();
        if (current > max_val) {
            max_val = current;
        }
        temp_stack.Push(current);
        Pop();
    }
    // 把临时栈的元素压回原栈，恢复原状态
    while (!temp_stack.Empty()) {
        Push(temp_stack.Top());
        temp_stack.Pop();
    }
    return max_val;
}

两种方法里，方法一的空间复杂度是O(1)，比方法二更高效，优先推荐。

内容的提问来源于stack exchange，提问作者AF4545