首页 > 试题广场 >

构造队列

[编程题]构造队列

热度指数：17274 时间限制：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

输入

输出

1
2 1
2 1 3
8 1 6 2 10 3 7 4 9 5

算法知识视频讲解

Java

pein531

模拟

自己构造一个稍微长一点的例子我们就能够推导出反向过程，从而逆向构造出原始队列。例如n=10

根据第二次才打印队首元素的特点，在偶数位置填数可以得到初始队列应该形如：x 1 x 2 x 3 x 4 x 5

第二次也在偶数位开始填数，得到：x 1 6 2 x 3 7 4 x 5

第三次填数，得到：8 1 6 2 x 3 7 4 9 5

最后一次填数得到原始队列：8 1 6 2 10 3 7 4 9 5

可以看到，我们该尾插的时候头插，该从头部弹出的时候从尾部弹出，该插入的时候弹出，该弹出的时候插入就可以了。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0){
            int n = sc.nextInt();
            ArrayDeque<Integer> deque = new ArrayDeque<>();
            for(int i = n; i >= 1; i--){
                deque.offerFirst(i);
                int t = deque.pollLast();
                deque.offerFirst(t);
            }
            StringBuilder sb = new StringBuilder();
            while(!deque.isEmpty()){
                sb.append(deque.pollFirst()).append(" ");
            }
            System.out.println(sb);
        }
    }
}

发表于 2022-04-09 21:25:35 回复(0)

Java

放学后我不走~

题目告诉我们怎么做了，就是逆向来做

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
public class Main{
public static void main(String[] args){
    Main t = new Main();
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    while(n-- > 0){
        int T = in.nextInt();
        t.get(T);
    }
}

public void get(int n){
    Queue<Integer> Q = new LinkedList<Integer>();
    for(int i=n;i>0;i--){//反向操作，得到逆序队列
        Q.add(i);
        int x = Q.remove();
        Q.add(x);
    }
    Stack<Integer> s = new Stack<Integer>();
    while(!Q.isEmpty())//逆序队列用栈中转，就是正序了
        s.push(Q.remove());
    for(int i=0;i<n-1;i++)
        System.out.print(s.pop()+" ");
    System.out.println(s.pop());
}
}

发表于 2018-08-26 20:50:18 回复(0)

Java

ooSecret

//第一次写思路，不知道会不会跟别人一样emmmm
//若有错请轻喷。。请大家多多指教

import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;

public class Main {

static Queue<Integer> queue = new LinkedList<>();


public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);
    int t = scanner.nextInt();
    while (t>0){

        int n = scanner.nextInt();

        //用一个数组来存储原队列
        int[] num = new int[n+1];

        for (int i=1;i<=n;i++){
            //把位置存入队列中
            queue.add(i);
        }

        //模拟题目给的过程
        //把符合1,2,3...的序列的位置找出来，然后赋值
        int m = 1;
        while (!queue.isEmpty()){

            int x = queue.element();
            queue.poll();
            queue.add(x);

            x = queue.element();
            //从1到n，如果模拟的过程中刚好可以得到那样的序列
            //就把当前的x，即位置x，则在该位置上赋值
            num[x] = m;
            m++;
            queue.poll();

        }

        for (int i=1;i<=n;i++){
            if (i!=n){
                System.out.print(num[i]+" ");
            }
            else {
                System.out.print(num[i]);
            }
        }
        System.out.println();

        t--;

    }


}

}

发表于 2018-06-26 10:08:46 回复(0)

Java

傻傻傻傻

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int total = in.nextInt();
            int[] input = new int[total];
            for (int i = 0; i < total; i++)
                input[i] = in.nextInt();

            for (int i = 0; i < total; i++) {
                Deque<Integer> deque = getArray(input[i]);
                while (deque.size() > 0) {
                    if (deque.size() == 1) System.out.print(deque.removeFirst());
                    else System.out.print(deque.removeFirst() + " ");
                }
                System.out.println();
            }
        }
    }
    private static Deque<Integer> getArray(int num) {
        Deque<Integer> deque = new LinkedList<>();
        int size = num;
        while (deque.size() < size) {
            if (deque.isEmpty()) deque.addLast(num);
            else {
                int last = deque.removeLast();
                deque.addFirst(last);
                deque.addFirst(num);
            }
            num--;
        }
        deque.addFirst(deque.removeLast());
        return deque;
    }
}
------------------------------------------------------------------------
//参考高票答案，进行代码改进
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int total = in.nextInt(); //输入次数
            while (total-- > 0) {
                int num = in.nextInt();
                LinkedList<Integer> list = getPreData(num);
                for (int i = 0; i < num; i++) {
                    if (i == num - 1) System.out.print(list.removeFirst());
                    else System.out.print(list.removeFirst() + " ");
                }
                System.out.println();
            }
        }
    }
    private static LinkedList<Integer> getPreData(int num) {
        LinkedList<Integer> list = new LinkedList<>();
        //整个过程模拟一下就明白了
        for (int i = num; i > 0; i--) {
            list.addFirst(i);
            list.addFirst(list.removeLast());
        }
        return list;
    }
}

编辑于 2017-12-11 13:46:07 回复(0)

Java

wkb

首先把题目意思直白化

package test;

import java.util.LinkedList;
import java.util.Scanner;

public class test01 {
     public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t;
        t = scanner.nextInt();
        LinkedList<Integer> res;
        while(t-->0){
            int n;
            n = scanner.nextInt();
            res=f(n);
            for(int i=0;i<n-1;i++){
                System.out.print(res.removeFirst()+" ");//print单行输出
            }
            System.out.println(res.removeFirst());//println最后一个连接点输出完要换行输出
        }
    }

     public static LinkedList<Integer> f(int n){//整题的核心就这个方法,
         LinkedList<Integer> linkedList = new LinkedList<Integer>();
         for (int i = n; i >0; i--) {
            linkedList.addFirst(i);
            linkedList.addFirst(linkedList.removeLast());
        }
         return linkedList;
     }

}

发表于 2017-09-20 12:01:47 回复(0)

Java

指offer的剑在哪？

题中的队列的变形方式为先pop出队首，然后push出来将队首元素重新add到队列的末尾最终成为1-n组成的有序队列数，因此想要获取到原先的队列，可以逆向转换，先添加元素到队首，然后取出最后一个元素添加到队首

最终输出如果使用get(i)将会超时，因为get貌似会对队列进行遍历，而使用removeLast()来输出将能ac

参照大神解法，这里笔记记下~

import java.util.LinkedList;
import java.util.Scanner;

public class StringUtil {
	
	//构造队列
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		LinkedList<Integer> res;
		while(t != 0){
			int n = in.nextInt();
			res = getRes(n);
			for(int i=0; i<n-1; i++){
				System.out.print(res.removeFirst() + " ");
			}
			System.out.println(res.removeFirst());
			t--;
		}
	}
	public static LinkedList<Integer> getRes(int n){
		LinkedList<Integer> head = new LinkedList<Integer>();
		for(int i=n; i>0; i--){
			head.addFirst(i);
			head.addFirst(head.removeLast());
		}
		return head;
	}
}

发表于 2017-09-04 13:19:14 回复(0)

Java

miki痴狂到天荒

import java.util.ArrayList;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
	 Scanner sc = new Scanner(System.in);
	 while(sc.hasNext()) {
		int t = sc.nextInt();
		ArrayList<int[]> ar = new ArrayList<int[]>();
		while(t>0) {
		 int n = sc.nextInt();
	     int[] a = new int[n];
	     int j = 1,i=0,k=0;
	     while(j<=n) {	
	    	 if(i>n-1) i = 0; 
	         while(a[i++]==0) {
	        	 k++;
	        	 if(k%2==0) a[i-1] = j++;
	        	 if(i>n-1) i=0;
	         }       
	     }
	     ar.add(a);
	      t--;
		}
		for(int[] arr: ar) {
		    for(int i=0;i<arr.length;i++) {
		        if(i<arr.length-1)  System.out.print(arr[i]+" ");
		        else  System.out.println(arr[i]);
		   }
	  }
	}
 }
}

编辑于 2017-04-05 17:44:33 回复(0)

Java

我要sp要要要

import java.util.*;
public class Main{
    public static void main(String arg[]){
        Scanner s=new Scanner(System.in);
        
            int T=s.nextInt();
            for(int i=0;i<T;i++){
                int n=s.nextInt();
                int temp=1;
                int[]b=new int[2*n];
                for(int j=1;j<n+1;j++){
                    b[2*j-1]=temp;
                    temp++;
                }
                for(int j=1;j<n+1;j++){
                   b[2*n-2*j]=b[2*n-j]; 
                }
                for(int j=0;j<n-1;j++){
                    System.out.print(b[j]+" ");
                }
                System.out.println(b[n-1]);
            }
        
    }
}

发表于 2017-03-17 02:16:37 回复(0)

Java

markcheney

//求指教
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.Scanner;
public class in {
	public static void format(Deque<Integer> s){
		int t=s.size();
		for(int i=0;i<t-1;i++){
			System.out.print(s.removeFirst()+" ");
		}
		System.out.println(s.removeFirst());
	}
	public static void rebuild(int[] tmp){
		int data;
		Deque<Integer> deque=new ArrayDeque<>();
		for(int i=0;i<tmp.length;i++){
			data=tmp[i];
			if(data==1){
				System.out.println("1");;
				continue;
			}
			if(data==2){
				System.out.println("2 1");
				continue;
			}
			deque.offerLast(data-1);
			deque.offerLast(data);
			for(int j=data-2;j>0;j--){
				deque.offerFirst(deque.removeLast());
				deque.offerFirst(j);
			}
			deque.addFirst(deque.removeLast());
			format(deque);
			deque.clear();	
		}
	}
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		while(scanner.hasNext()){
			int recyle=scanner.nextInt();
			int[] t=new int[recyle];
			for(int i=0;i<recyle;i++){
				t[i]=scanner.nextInt();
			}
			rebuild(t);		
	}
}
}

编辑于 2016-09-15 21:03:08 回复(0)

Java

Holiday_12138

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)

Java

木易星

import java.util.Scanner;

import java.util.Vector;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNextInt()){
			int T = sc.nextInt();
			while(T>0){
				int n = sc.nextInt();
				Vector vector = new Vector<>();				
				for(int i = 1;i<=n;i++){
					vector.add(i);
				}
				for(int i = 1;i < n;i++){
					int temp = (int) vector.get(vector.size()-1);//取到最后一个数字
					vector.insertElementAt(temp, vector.size() - 1 - i);//将数字插入到队列中
					vector.remove(vector.size()-1);//移除最后一个数字	
				}
				for(int i = 0;i<vector.size();i++){
					if(i!=vector.size()-1){
						System.out.print(vector.get(i)+" ");
					}else{
						System.out.println(vector.get(i));
					}
				}
				
			}
		}
	}
}  java  到底怎么实现才能不超时啊？？？

发表于 2016-08-18 15:21:20 回复(1)