用一个栈实现另一个栈的排序

用一个栈实现另一个栈的排序

一、题目

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。

leetcode：https://leetcode.cn/problems/sort-of-stacks-lcci/

二、思路

想要对栈进行排序，并且从栈低到栈顶为从大到小。可以使用一个辅助栈，那么我们只需要让辅助栈的栈低到栈顶为从小到大即可。也就是我们将元素按照一定逻辑插入到辅助栈中，实现辅助栈的栈低到栈顶为从小到大即可。

我们从栈中取出一个元素记为 cur，当去插入到辅助栈中时，和辅助栈的 top 值进行比较（如果没有top，直接插入）

• 如果 cur 大于等于辅助栈的 top 值，直接插入
• 如果 cur 小于辅助栈的 top 值，则将辅助栈的元素重新插入回栈中，直到当前的 cur 值大于等于辅助栈的 top 值为止

记住，我们只需要保证辅助栈有序即可，不用管待排序的栈是否有序。

三、code

#include <stack>
#include <iostream>

class SortedStack {
public:
    SortedStack() {}

    void push(int val) {
        // 小于等于 top 值，直接插入
        if (st_.empty() || val <= st_.top()) {
            st_.push(val);
            return;
        }
        for (; !st_.empty() && st_.top() <= val ;) {
            help_st_.push(st_.top());
            st_.pop();
        }
        st_.push(val);
        for (; !help_st_.empty();) {
            st_.push(help_st_.top());
            help_st_.pop();
        }
    }

    void pop() {
        if (!st_.empty()) {
            st_.pop();
        }
    }

    int peek() {
        if (!st_.empty()) {
            return st_.top();
        }
        return -1;
    }

    bool isEmpty() {
        return st_.empty();
    }

private:
    std::stack<int> st_;
    std::stack<int> help_st_;
};

int main() {
    SortedStack s;
    s.pop();
    s.pop();
    s.push(1);
    s.pop();
    s.isEmpty();
    // s.push(1);
    // s.push(2);
    // std::cout << s.peek() << std::endl;
    // s.pop();
    // std::cout << s.peek() << std::endl;
}

也可以使用优先级队列来做，优先级队列直接帮我们排好序了。