C++ 數據結構：棧能否排序後再 Peek？兩種實現方案對比

問題本質

棧（Stack）是**後進先出（LIFO）**結構，標準操作僅有 push、pop、peek/top。直接排序違背棧的定義，但可通過輔助結構實現「有序棧」效果。

方案一：雙棧排序（面試經典）

// 將輸入棧 s1 排序為升序（棧頂最小），使用輔助棧 s2
void sortStack(stack& s1) {
    stack s2;
    while (!s1.empty()) {
        int tmp = s1.top(); s1.pop();
        while (!s2.empty() && s2.top() > tmp) {
            s1.push(s2.top()); s2.pop();
        }
        s2.push(tmp);
    }
    // 移回 s1，此時 s1 棧頂為最大元素（降序）
    while (!s2.empty()) {
        s1.push(s2.top()); s2.pop();
    }
}

時間複雜度 O(n²)，空間 O(n)。排序後可直接 peek() 獲取極值。

方案二：最小棧——O(1) 獲取最小值

若只需快速獲取最小值，無需完全排序：

class MinStack {
    stack data, minStack;
public:
    void push(int x) {
        data.push(x);
        if (minStack.empty() || x <= minStack.top()) minStack.push(x);
    }
    void pop() {
        if (data.top() == minStack.top()) minStack.pop();
        data.pop();
    }
    int top() { return data.top(); }
    int getMin() { return minStack.top(); } // O(1)
};

方案三：C++11 std::priority_queue（堆）替代

若業務允許，直接用優先隊列（大根堆/小根堆）實現「自動有序」的棧語義：

priority_queue, greater> minHeap; // 棧頂最小
minHeap.push(3); minHeap.push(1); minHeap.push(2);
cout << minHeap.top(); // 1
minHeap.pop();         // 移除最小

總結建議

參考博客：棧的排序與最小值獲取詳解