数组零元素后置解法是否满足线性时间与常数空间要求

给定一个包含若干数字和0的数组，对其进行整理，使得所有非零数字位于数组前端，所有0位于数组末尾。

问询 #

下述解法的运行时间是否为线性时间（Linear time）？空间占用是否为常数空间（constant space）？

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main()
{
    cin.tie(0);
    std::ios_base::sync_with_stdio(false);

    vector<int> MyVec;
    int input;
    int i = 0;
    stack<int> mystack;
    stack<int> zerostack;
    while((input = getchar())&& (input!=10))
    {
        if(input != 32)
        {
            MyVec.push_back(input - '0');

            if(MyVec[i] == 0)
                zerostack.push(MyVec[i]);
            else
                mystack.push(MyVec[i]);

            i++;
        }
    }
    MyVec.clear();
    while(!mystack.empty())
    {
         MyVec.push_back(mystack.top());
         mystack.pop();
    }
    while(!zerostack.empty())
    {
         MyVec.push_back(zerostack.top());
         zerostack.pop();
    }
    for(auto a : MyVec)
        cout << a << " ";

    return 0;
}

时间复杂度判定 #

该解法是线性时间复杂度O(n)。
所有操作的总次数和输入元素的规模n成正比：输入阶段遍历所有元素1次，每个元素只会被存入对应栈1次；重构数组阶段两个栈的元素总数量就是n，每个元素只会被取出并写入数组1次；最终输出阶段遍历所有元素1次。整体没有嵌套循环之类的超线性操作，符合线性时间要求。

空间复杂度判定 #

该解法不属于常数空间，是线性空间复杂度O(n)。
代码额外定义了两个栈mystack和zerostack，两个栈存储的元素总数和输入的n个元素完全相等，额外空间占用会随着输入规模的增长线性增长，不符合常数空间要求（常数空间要求额外占用的空间大小固定，和输入规模无关）。

额外补充 #

该解法的输出会反转非零元素的原有相对顺序，比如输入1 2 0 3，输出会是3 2 1 0，如果题目要求非零元素保持原有相对顺序，这个实现是不符合要求的。如果要同时满足常数空间、线性时间、保留非零元素顺序，可以使用双指针原地交换的方案实现。

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