構造隊列——網易有道2017内推程式設計題

題目描述

小明同學把1到n這n個數字按照一定的順序放入了一個隊列Q中。現在他對隊列Q執行了如下程式：

while(!Q.empty()) //隊列不空，執行循環

{

int x=Q.front();            //取出目前隊頭的值x

Q.pop();                 //彈出目前隊頭

Q.push(x);               //把x放入隊尾

x = Q.front();              //取出這時候隊頭的值

printf("%d\n",x);          //輸出x

Q.pop();                 //彈出這時候的隊頭
           

}

做取出隊頭的值操作的時候，并不彈出目前隊頭。

小明同學發現，這段程式恰好按順序輸出了1,2,3,…,n。現在小明想讓你構造出原始的隊列，你能做到嗎？

輸入描述

第一行一個整數T（T ≤ 100）表示資料組數，每組資料輸入一個數n（1 ≤ n ≤ 100000），輸入的所有n之和不超過200000。

輸出描述

對于每組資料，輸出一行，表示原始的隊列。數字之間用一個空格隔開，不要在行末輸出多餘的空格。

示例一

輸入

4

1

2

3

10

輸出

1

2 1

2 1 3

8 1 6 2 10 3 7 4 9 5

題目分析

小明的操作是把隊頭的元素放到隊尾，然後再彈出隊頭并輸出隊頭，然而題目要求的是原始的隊列，此時我們就需要進行逆向思維。

倒過來的步驟是，把一個元素插入到隊頭，然後再把這個元素從隊尾放到隊頭。

我們拿n=3舉例：

1.當n=3的最後一步是将3從隊頭放到隊尾，然後将3從隊頭彈出；倒過來就是，将3插入到隊頭，然後将3從隊尾放到隊頭。

2.倒數第二步是将3從隊頭放到隊尾，然後彈出隊頭元素2；倒過來就是，将2插入隊頭，然後将3從隊尾放到隊頭。

3.第一步是将2從隊頭放到隊尾，然後彈出隊頭元素1,；倒過來就是，将1插入隊頭，然後将2從隊尾放到隊頭。

代碼

C++代碼如下：

#include<iostream>
#include<deque>
using namespace std;
int main()
{
    int n,k;
    cin>>n;
    while(n--)
    {
        deque<int> q;
        cin>>k;
        for(int i=k;i>0;i--)
        {
            q.push_front(i);
            int t=q.back();
            q.pop_back();
            q.push_front(t);
        }
        for(int i=0;i<q.size();i++)
        {
            if(i==q.size()-1)
                cout<<q[i];
            else
            {
                cout<<q[i]<<" ";
            }
            
        }
        cout<<endl;
            
    }
    return 0;
}