【算法百题之十九】序列逆序

    大家好，我是Lampard~~

    很高兴又能和大家见面了，接下来准备系列更新的是算法题，一日一练，早日升仙！

    今天的问题是：

    小易有一个长度为n的整数序列,a_1,...,a_n。然后考虑在一个空序列b上进行n次以下操作:

   1、将a_i放入b序列的末尾

   2、逆置b序列  

   小易需要你计算输出操作n次之后的b序列。

     思路：

     题目要求，先插入，后倒置。说到倒置，我们很容易想到栈的后入先出的特点。

     为了实现数据能倒来倒去，我们就给他分配两个栈，从而实现功能。

#include "pch.h"
#include <vector>
#include <stack>
#include <iostream>using namespace std;
#define size 200000 // 数组的最大容量int main()
{stack<int> stackA;    stack<int> stackB;cout << "请输入n的大小：" << endl;int n;cin >> n;cout << "请输入数组的元素：" << endl;int array[size];for (int i = 0; i < n; i++){cin >> array[i];}stackA.push(array[0]);   for (int i = 1; i < n; i++){// 循环插入，找出不为空的栈，在后面插入，然后再把站内元素转移到另外一个栈中，以达到倒置的效果if (stackA.empty()==true){stackB.push(array[i]);while (!stackB.empty()){stackA.push(stackB.top());stackB.pop();}}else if (stackB.empty() == true){stackA.push(array[i]);while (!stackA.empty()){stackB.push(stackA.top());stackA.pop();}}}// 找出最后是哪一个栈存放着元素，倒序输出if (stackA.empty()){for (int i = 0; i < n; i++){stackA.push(stackB.top());stackB.pop();}for (int i = 0; i < n; i++){cout << stackA.top()<< " ";stackA.pop();}}else if (stackB.empty()){for (int i = 0; i < n; i++){stackB.push(stackA.top());stackA.pop();}for (int i = 0; i < n; i++){cout << stackB.top()<< " ";stackB.pop();}}}

  关键在于循环插入时判断哪一个栈存有数据，先插再倒置，这个顺序不能错！

 结果：

OK，今天的博客就到这里，谢谢大家！！！