40. 逆转数组（三）

一. 问题

给定一个含有 n 个元素的序列 A，将序列中的元素逆转。

二. 思路

在前两篇文章中，我用到两种手法来逆转数组，第一种是元素交换第二种是用一个额外的栈。现在我们考虑一种新的算法：用一个队列来读入序列中的元素，再将队列中元素弹出，从后向前重新放回序列中，这样就完成了整个序列的逆转。此算法的时间复杂度仍然是 O( n )，但是空间复杂度变为 O( n )（因为队列的大小随着序列长度变化）。不难看出，队列实际上充当了一个临时变量的角色。在第一种方法中，我们每次处理一个元素；在这个方法中，我们一次处理所有元素。因此，这两种方法的本质是一样的。

三. 代码实现

void reverse_array_queue(vector<int>& data) {
    queue<int> temp_data;

    for (auto& x : data) {
        temp_data.push(x);
    }

    for (int i = data.size() - 1; i >= 0; --i) {
        data[i] = temp_data.front();
        temp_data.pop();
    }
}

代码中有几处需要说明

（1）先声明一个队列，用于存放元素。

（2）将元素从放回原序列时，应该从后往前放，否则就没有逆转的效果了。