借助辅助栈实现排序

2024-03-01

algorithm

给栈结构设计一个求最小值的操作，要求入栈、出栈以及求最小值均在O(1)完成。

思路：

黑盒：作为一个整体的栈结构，作为黑盒，只有push,pop操作接口，并且提供求取最小值的接口。

白盒：细窥上述黑盒内部结构，内部由两个辅助栈最小栈 辅助栈来完成，实现接口细节如下：

push：当我们压入栈元素时，要保持栈内“排序”，从而达到能获取最小值。压入的元素与最小栈栈顶元素相比，如果小于则压入最小栈，否则压入辅助栈。
pop：优先从辅助栈弹出，弹出前比较最小栈栈顶，若相等，则一起弹出

求最小值：

直接返回最小栈的栈顶元素即可，该元素即为当前数据栈中的最小值。

代码：

#include <stack>
#include <iostream>

using namespace std;

class MinStack {
private:
    stack<int> dataStack;
    stack<int> minStack;

public:
    MinStack() {}

    void push(int x) {
        dataStack.push(x);
        if (minStack.empty() || x <= minStack.top()) {
            minStack.push(x);
        }
    }

    void pop() {
        if (!dataStack.empty()) {
            if (dataStack.top() == minStack.top()) {
                minStack.pop();
            }
            dataStack.pop();
        }
    }

    int top() {
        if (!dataStack.empty()) {
            return dataStack.top();
        }
        return -1; // 栈为空时返回-1
    }

    int getMin() {
        if (!minStack.empty()) {
            return minStack.top();
        }
        return -1; // 栈为空时返回-1
    }
};

int main() {
    MinStack minStack;
    minStack.push(3);
    minStack.push(5);
    cout << "Min: " << minStack.getMin() << endl; // 输出：Min: 3
    minStack.push(2);
    cout << "Min: " << minStack.getMin() << endl; // 输出：Min: 2
    minStack.pop();
    cout << "Top: " << minStack.top() << endl; // 输出：Top: 5
    cout << "Min: " << minStack.getMin() << endl; // 输出：Min: 3
    return 0;
}

给出策略利用栈去完成一个序列的排序，并分析相应的性能。

思路：

需要排序栈来辅助完成，每次要压入栈时，要找到适合他的位置！

当前数小于栈顶，则直接压入。
当前数大于栈顶，则需要pop栈，直到栈顶大于当前数，压入后，将之前pop出的元素压回（找到他合适的位置）

pop出的元素存在哪里？

新开数组？占空间✖

压回原栈，记录个数，最后的时候再全部pop（）✅

代码

#include <stack>
#include <vector>
#include <iostream>

using namespace std;

void sortStack(stack<int>& input) {
    stack<int> tempStack;
    
    while (!input.empty()) {
        int temp = input.top();
        input.pop();
        
        // 找到合适位置插入元素
        while (!tempStack.empty() && tempStack.top() > temp) {
            input.push(tempStack.top());
            tempStack.pop();
        }
        
        tempStack.push(temp);
    }
    
    // 将排序后的元素转移到原栈中
    while (!tempStack.empty()) {
        input.push(tempStack.top());
        tempStack.pop();
    }
}

int main() {
    stack<int> myStack;
    vector<int> input = {5, 2, 7, 3, 1};

    // 将输入序列压入栈中
    for (int num : input) {
        myStack.push(num);
    }

    // 排序栈
    sortStack(myStack);

    // 打印排序后的栈
    cout << "Sorted Stack: ";
    while (!myStack.empty()) {
        cout << myStack.top() << " ";
        myStack.pop();
    }
    cout << endl;

    return 0;
}