程序员面试金典 - 面试题 03.05. 栈排序（两栈）

Michael阿明

发布于 2020-07-13 15:51:11

3520

发布于 2020-07-13 15:51:11

文章被收录于专栏：Michael阿明学习之路 Michael阿明学习之路Michael阿明学习之路

1. 题目

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

示例1:
 输入：
["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]
 输出：
[null,null,null,1,null,2]

示例2:
 输入： 
["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]
 输出：
[null,null,null,null,null,true]
说明:
栈中的元素数目在[0, 5000]范围内。

2. 解题

用两个栈，来回倒数据，保证其中一个为空
倒的过程中找到最小的放在非空的栈的顶端

class SortedStack {
    stack<int> s;
    stack<int> temp;
    int nextMin;
public:
    SortedStack() {}
    
    void push(int val) {
        if(isEmpty())
            s.push(val);
        else if(temp.empty())
        {
            if(s.top() < val)//栈顶小
                swap(val,s.top());//把栈顶变成大的
            s.push(val);//在把原来的小栈顶放回
        }
        else //s.empty()
        {
            if(temp.top() < val)
                swap(val,temp.top());
            temp.push(val);
        }
    }
    
    void pop() {
        if(isEmpty())
            return;
        if(temp.empty())
        {
            s.pop();//最小值pop
            while(!s.empty())//倒数据到temp
            {
                nextMin = s.top();
                s.pop();
                if(!temp.empty() && nextMin > temp.top())
                    swap(nextMin, temp.top());
                temp.push(nextMin);
            }
        }
        else //s.empty()
        {
            temp.pop();//最小值
            while(!temp.empty())//倒数据到s
            {
                nextMin = temp.top();
                temp.pop();
                if(!s.empty() && nextMin > s.top())
                    swap(nextMin, s.top());
                s.push(nextMin);
            }
        }
    }
    
    int peek() {
        if(isEmpty())
            return -1;
        if(temp.empty())
            return s.top();
        else //s.empty()
            return temp.top();
    }
    
    bool isEmpty() {
        return s.empty()&&temp.empty();
    }
};