首页 > 试题广场 >

构造队列

[编程题]构造队列
  • 热度指数:17267 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
小明同学把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。现在小明想让你构造出原始的队列,你能做到吗?[注:原题样例第三行5有错,应该为3,以下已修正]

输入描述:
第一行一个整数T(T ≤ 100)表示数据组数,每组数据输入一个数n(1 ≤ n ≤ 100000),输入的所有n之和不超过200000。


输出描述:
对于每组数据,输出一行,表示原始的队列。数字之间用一个空格隔开,不要在行末输出多余的空格.
示例1

输入

4
1
2
3
10

输出

1
2 1
2 1 3
8 1 6 2 10 3 7 4 9 5
^_^
#include <iostream> #include <deque> using namespace std; int main() { int n, k; cin >> k; while(k > 0) { deque<int> q; k--; cin >> n; for(int i = n; 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++) cout << q[i] << " "; cout << endl; } }


编辑于 2016-08-18 14:45:42 回复(21)
import java.util.LinkedList;
import java.util.Scanner;
public class NewTest{
 	public static LinkedList<Integer> func(int n){
        LinkedList<Integer> help=new LinkedList<Integer>();
        for(int i=n;i>=1;i--){
            help.addFirst(i);
            help.addFirst(help.removeLast());
        }
        return help;
    }
    public static void main(String[] args){
        int t;
        Scanner scan = new Scanner(System.in);
        t=scan.nextInt();
        int n;
        LinkedList<Integer> res;
        while(t-->0){
            n=scan.nextInt();
            res=func(n);
            for(int i=0;i<n-1;i++){
                System.out.print(res.removeFirst()+" ");
            }
            System.out.println(res.removeFirst());
        }
    }
}

发表于 2016-08-25 16:42:27 回复(9)
//将顺序序列处理得出结果
//比如1 2 3 4 5,先将5插入到3、4之间(隔1),得到1 2 3 5 4,再将4插入到2、3之间(隔2),得到1 2 4 3 5,再将5插入
//到1、2之间(隔3),得到1 5 2 4 3,最后将3插入到1前面(隔4),得到最终结果:3 1 5 2 4
//从上面例子可看出,不断的将最后一个元素插入到前面,规律为相隔元素个数依次递增,上面是从1到4
#include<iostream>
#include<vector>
using namespace std;

int main() {
	int t;
	while (cin >> t) {
		while (t) {
			int n;
			cin >> n;
			vector<int> vec;
			for (int i = 1; i <= n; i++) {
				vec.push_back(i);
			}
			for (int i = 1; i < n; i++) {
				int tmp = *(vec.end() - 1);
				vec.insert(vec.end() - i - 1, tmp);
				vec.pop_back();
			}
			bool flag = true;
			for (int i : vec) {
				if (flag) {
					flag = false;
					cout << i;
				}
				else
					cout << " " << i;
			}
			cout << endl;
			t--;
		}
	}
}

编辑于 2016-08-18 13:14:01 回复(6)
import java.util.LinkedList;
import java.util.Scanner;

/**
 * 思想:先使用一个1到n的数组模拟小明的操作,
 * 然后会得到一组输出,例如:3,5,10,7....
 * 按题意是应该输出   1,2,3,4....
 * 这样,我们就可以反推出
 * 1应该在第3个位置
 * 2应该在第5个位置
 * 3应该在第10个位置
 * 4应该在第7个位置
 * ....
 * Created by hzlizhou on 2016/9/8.
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int number = scanner.nextInt();
        while(number-->0){
            int n = scanner.nextInt();
            helper(n);
        }
    }

    public static void helper(int n) {
        //生成一个1-n的数组
        LinkedList<Integer> original = new LinkedList<Integer>();
        for (int i = 1; i <= n; i++) {
            original.addLast(i);
        }

        //模拟过程
        LinkedList<Integer> res = new LinkedList<Integer>();
        while (!original.isEmpty()) {
            int x = original.removeFirst();
            original.addLast(x);
            x = original.removeFirst();
            res.addLast(x);
        }

        //反推出正确位置,放入out数组中
        int[] out = new int[n];
        for (int i = 1; i <= n; i++) {
            int x = res.removeFirst();
            out[x - 1] = i;
        }

        //输出out数组
        System.out.print(out[0]);
        for (int i = 1; i < n; i++) {
            System.out.print(" "+out[i]);
        }
        System.out.println();
    }
}

发表于 2016-09-08 19:09:16 回复(2)
我的想法很简单,假设有原始序列为a0,a1,a2,...,an-1,现在压入队列的都是下标0,1,2,...,n-1,
然后依据题意的while循环,记录每次出队的下标,正好对应1,2,3。。。,并插入map,前键是下标,后键是实际的出队数字。
使用map是为了输出阶段,快速依据下标[0,n-1],找到对应的数字。
#include<iostream>
#include<queue>
#include<vector>
#include<map>
 
using namespace std;
 
intmain() {
    intt;
    cin >> t;
    for(inti = 0; i<t; i++) {
        intn;
        cin >> n;
        vector<int> nums(n, 0);
        queue<int> q;
        for(intj = 0; j<n; j++)
            q.push(j);
        map<int, int> index_value;
        intvalue = 1;
        while(!q.empty())              //队列不空,执行循环
        {
            intx = q.front();           //取出当前队头的值x
            q.pop();                 //弹出当前队头
            q.push(x);               //把x放入队尾
            x = q.front();              //取出这时候队头的值
            //printf("%d\n", x);          //输出x
            index_value.insert(pair<int,int>(x,value++));
            q.pop();                 //弹出这时候的队头
        }
        for(inti = 0; i < n; i++)
        {
          if(i<n-1)cout << index_value[i] << " ";
          elsecout << index_value[i] << endl;
        }
 
 
    }
    return0;
}

发表于 2016-09-03 21:12:04 回复(4)
这道题其实是约瑟夫环问题的变形,构造一个长度为n的数组,没两个数填一下,结果就是了

发表于 2016-08-18 14:02:45 回复(2)

将数组看成一个环,每隔一个空位放入一个数字
例如长度为10时,用0代表空位
每隔一个空位放入数字 0 1 0 2 0 3 0 4 0 5
环继续从头开始,此时还剩5个空位,继续每隔一个空位放入一个数字 0 1 6 2 0 3 7 4 0 5
同理 8 1 6 2 0 3 7 9 5
最后 8 1 6 2 10 3 7 9 5

public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        for(int i=0;i<t;i++){
            int n = scanner.nextInt();
            int[] arr = new int[n];
            int zero = 0;
            int num = 1;
            do {
                for(int j=0;j<n;j++){
                    if(arr[j]==0){
                        zero++;
                        if(zero%2==0){
                            arr[j] = num++;
                        }
                    }
                }
            }while (num<=n);

            for(int j=0;j<n;j++){
                if(j>0) System.out.print(" ");
                System.out.print(arr[j]);
            }
            System.out.println();
        }
    }
发表于 2018-10-10 16:45:11 回复(0)
可以按照题目反思路来做,从大到小每次插入数到队列队头,然后将队尾移至队头,循环即可
发表于 2016-08-22 09:19:56 回复(1)
参考大佬的思路,把过程倒过来做,用python3做的:

t = int(input())

for _ in range(t):
    n = int(input())
    res = []
    for i in range(n, 0, -1):
        res.append(i)
        tmp = res[0]
        res.pop(0)
        res.append(tmp)
        
        
    len_r = len(res)
    for i in range(len_r - 1):
        print(res[len_r - 1 - i], end = ' ')
        
    print(res[0])
    print(res)


发表于 2018-09-13 11:01:18 回复(1)
// :-)
#include <stdio.h>
#include <stdlib.h>

void Queue(int n);
int main()
{
  int T, i;
  int *num;

  scanf("%d", &T);
  num = (int *)malloc(sizeof(int) * T);
  for (i=0; i<T; i++)
    scanf("%d", &num[i]);
  for (i=0; i<T; i++)
    Queue(num[i]);
  return 0;
}

void Queue(int n){

  int book[n];
  int qout[n];
  int i, j=0;

  for (i=0; i<n; i++)
    book[i] = 0;

  // Construct the output queue
  for (i=0; i<n; i++){
    while (book[j++%n] != 0);
    while (book[j%n] != 0) j++;
    qout[j%n] = i+1;
    book[j%n] = 1;
  }

  // Outputs
  for (i=0; i<n-1; i++)  printf("%d ", qout[i]);
  printf("%d\n", qout[n-1]);
}

编辑于 2017-12-15 16:37:31 回复(1)
#include<iostream>//活用题目给的代码啊。加输入输出就好了
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct Node
{
    int date;
    int Index;
};
Node node[100100];
int main()
{
    queue<Node>Q;
    int N;
    cin>>N;
    while(N--)
    {
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            node[i].Index=i;
        }
        for(int i=0;i<n;i++)
        {
            Q.push(node[i]);
        }
        int Num=0;
        while(!Q.empty())              //队列不空,执行循环
        
        {

            Node x=Q.front();            //取出当前队头的值x

            Q.pop();                 //弹出当前队头

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

            x = Q.front();              //取出这时候队头的值

            node[x.Index].date=Num++;         //输出x

            Q.pop();                 //弹出这时候的队头

        }
        for(int i=0;i<n;i++)
        {
            if(i!=n-1)
                cout<<node[i].date+1<<" ";
            else
                cout<<node[i].date+1<<endl;
        }
    }
    return 0;
}
发表于 2016-12-13 11:31:51 回复(0)
#include<iostream>
#include<vector>
 
using namespace std;
 
int main(){//偶然发现的一个规律,也不是的为什么
    int m;
    cin>>m;
    while(m--){
        int n;
        cin>>n;
        vector<int> a(n,0); //建一个全是0的列表
        int p = 0; 
        for(int i=0;i<n;i++){
            while(a[p]!=0) p = (p==n-1?0:p+1);//找到一个不是0的位置
            p = (p==n-1?0:p+1);//跳过第一个不是0位置
            while(a[p]!=0) p = (p==n-1?0:p+1);//找到第二个不是0的位置
            a[p]=i+1;
        }
        for(int i=0;i<n-1;i++) cout<<a[i]<<" ";
        cout<<a[n-1]<<endl;
    }
}

编辑于 2016-10-29 19:13:17 回复(1)
process.stdin.resume();
process.stdin.setEncoding('utf-8');
var input = "";
process.stdin.on('data', function (data) {
    input += data;
});
process.stdin.on('end', function () {
    var arr = input.split("\n"),
        len = arr.length,
        res = [];
    for (var i=1; i<len; i++) {
        var n = arr[i],
            strArr = [];
        for(var j=n; j>0; j--){
            strArr.unshift(j);
            strArr.unshift(strArr.pop());
        }
        res.push(strArr.join(" "));
    }
    process.stdout.write(res.join("\n"))
});

编辑于 2016-09-07 22:16:00 回复(9)
根据题目和实例,题目对队列的操作为:1.将第一个放到最后;2.弹出第一个。最终弹出结果为1,2,3……n。故还原操作为两个:1.插入到第一个位置;2.将最后一个放到第一个。注:由于弹出结果为正序,故还原序列应为逆序,故为 n,n-1,……,3,2,1。
import sys

if __name__ == "__main__":
    T = int(sys.stdin.readline().strip())
    
    for i in range(T):
        n = int(sys.stdin.readline().strip())
        
        res_list = []
        
        for j in reversed((range(1, n + 1))):
            res_list.insert(0, j)
            tmp = res_list.pop()
            res_list.insert(0, tmp)
        
        res = list(map(str, res_list))
        
        print(" ".join(res))


发表于 2020-07-27 21:13:11 回复(0)
#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int k;
        cin>>k;
        deque<int> dq;
        for(int i=k;i>0;--i)
        {
            dq.push_front(i);
            int c=dq.back();
            dq.pop_back();
            dq.push_front(c);
        }
        for(auto i=dq.begin();i!=dq.end();++i)
        {
            cout<<*i<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

编辑于 2020-06-04 22:34:22 回复(0)

用遍历的方式,没有大神的方法好

#include <iostream>
#include <string.h>
using namespace std;
int main(){
    int T,n;
    cin>>T;
    while(T){
        cin>>n;
        int b[n];
        memset(b,0,sizeof(b));
        int i=0;
        int temp=0;
        int start=1;
        while(start<=n){
            if(!b[i]){
                if(temp==0)
                    temp++;
                else if(temp==1){
                    b[i]=start;
                    temp=0;
                    start++;
                }
            }
            i++;
            if(i==n)
                i=0;
        }
        for(int j=0;j<n-1;j++)
            cout<<b[j]<<" ";
        cout<<b[n-1]<<endl;
        T--;
    }
    return 0;
}
发表于 2018-09-22 17:09:10 回复(0)
约瑟夫环,暂不考虑末尾空格

运行时间:705ms

占用内存:32560k


import java.util.Arrays;
import java.util.Scanner;

public class Main
{
    static int n;
    static int[] num;

    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();

        while (T-- != 0)
        {
            n = scan.nextInt();
            num = new int[n];

            int lastPos = 0;
            for (int i = 1; i <= n; i++)
            {
                lastPos = findNextPos(lastPos);
                num[lastPos] = i;
            }
            
            for (int i = findIndex(n / 2), count = 0; count < n; count++)
            {
                System.out.print(num[i] + " ");
                i = (i + 1) % n;
            }
            System.out.println();

        }
        scan.close();
    }

    private static int findNextPos(int lastPos)
    {
        if (lastPos == 0 && num[lastPos] == 0)
            return 0;
        boolean foundNextBlank = false;
        int ret = lastPos;
        while (true)
        {
            ret = (ret + 1) % n;
            if (num[ret] == 0)
                if (foundNextBlank)
                    return ret;
                else
                    foundNextBlank = true;
        }
    }
    
    private static int findIndex(int d)
    {
        int i = 0;
        for (i = 0; i < n; i++)
            if (num[i] == d)
                break;
        if ((n & 1) == 1)
            i += 2;
        else
            i++;
        
        return i % n;
    }
}

发表于 2018-08-16 18:14:07 回复(0)
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int num = input.nextInt();
        for (int i = 0; i < num; i++){
            int n = input.nextInt();
            int[] data = new int[n];
            int index = 0;
            for (int j = 1; j <= n; j++){
                int flag = 0;
                while (index < data.length){
                    if (index < data.length && data[index] == 0){
                        flag++;
                        if (flag >= 2) {
                            flag = 0;
                            break;
                        }
                    }
                    index = (index+1)%data.length;
                }
                data[index] = j;
            }
            for (int j = 0; j < data.length-1; j++){
                System.out.print(data[j]+ " ");
            }
            System.out.println(data[data.length-1]);
        }
    }
}


刷点存在感,,,
发表于 2018-07-30 19:23:13 回复(0)
// 这个题看上去很简单,但是就是没想出好方法。最早想通过正确顺序进行逆向队列还原,
// 但是脑袋总是转不过弯来,总是分不清什么时候前插什么时候后插。于是就使用了一种比
// 较笨的方法,思路如下:
// 可以画一下草图,不难发现这道题就是隔一个填一个就可以了,我这里以示例中的 1 - 10
// 为例,先进行第一次填写(未填的地方补0)
//                              第一次填写:      0 1 0 2 0 3 0 4 0 5
// 即隔一个 0 再下一个 0 里填顺序的下一个数。那么,第二次填写为
//                               第二次填写:      0 1 6 2 0 3 7 4 0 5
//                               第三次填写:      8 1 6 2 0 3 7 4 9 5
//                               第四次填写:      8 1 6 2 10 3 7 4 9 5
// 根据方法特点,选用单向循环列表即可。本来想用 STL 中的 list 模板,但是不是很会用,
// 循环列表环不起来,于是自己写的链表程序,代码如下:
  1. #include <iostream>
  2. using namespace std;
  3. class List                           //制作一个链表类
  4. {
  5. int numb;
  6. List *head, *next;
  7. public:
  8. void Create(int);
  9. List() :head(nullptr), next(nullptr), numb(0) {}
  10. void clear(void){delete[] head, head = nullptr;}
  11. void Print(void);
  12. };
  13. int main(void)
  14. {
  15. int n;
  16. cin >> n;
  17. int *numb = new int[n];
  18. for (int i = 0; i < n; i++) cin >> numb[i];
  19. for (int i = 0; i < n; i++)
  20. {
  21. List mylist;
  22. mylist.Create(numb[i]);
  23. List() :head(nullptr), next(nullptr), numb(0) {}
  24. mylist.Print();
  25. mylist.clear();
  26. }
  27. return 0;
  28. }
  29. void List::Create(int cont)
  30. {
  31. List *ptr1, *ptr2;
  32. ptr1 = ptr2 = nullptr;
  33. for (int i = 1; i <= cont; i++)                     //构建链表
  34. {
  35. ptr1 = new List;
  36. ptr1->numb = 0;
  37. if (head == nullptr) head = ptr1;
  38. else ptr2->next = ptr1;
  39. ptr2 = ptr1;
  40. }
  41. ptr2->next = head;
  42. List *write = head;
  43. for (int i = 1; i <= cont; i++) //进行数只填写,直至所有数值填完
  44. {
  45. while (write->numb != 0) write = write->next;//寻找为0的位置
  46. write = write->next;                                       //跳过第一个0位
  47. while (write->numb != 0) write = write->next;//寻找第二个0位
  48. write->numb = i;                                           //第二个0位填数
  49. }
  50. }
  51. void List::Print(void)                                              //打印链表
  52. {
  53. List *tmp = head;
  54. if (tmp == nullptr) return;
  55. do
  56. {
  57. cout << tmp->numb;
  58. if (tmp->next == head) cout << endl;
  59. else cout << " ";
  60. tmp = tmp->next;
  61. } while (tmp != head);
  62. }
发表于 2018-02-02 13:11:48 回复(0)

#include <iostream>

#include <vector>

using namespace std;


int main(int argc, const char * argv[]) {

    vector<int> order,amount;

    int T,temp;

    cin>>T;

    for(int i=0;i<T;i++)

    {

        cin>>temp;

        amount.push_back(temp);

    }

    for(int i=0;i<amount.size();i++)

    {

        for(int j=1;j<=amount[i];j++)//构造1~n的顺序数列

        {

            order.push_back(j);

        }

        int change=1;

        for(int k=0;k<amount[i];k++)//根据原操作的逆向操作

        {

            order.insert(order.end()-change, order.back());

            change++;

            order.pop_back();

        }

        for(int j=0;j<order.size()-1;j++)//打印输出

        {

            cout<<order[j]<<" ";

        }

        cout<<order.back()<<endl;

        order.clear();

    }

    return 0;

}


发表于 2018-02-01 11:48:57 回复(0)