时间戳

首页 > 解决方案 > 在 Java 中使用队列对元素进行排序

java - 在 Java 中使用队列对元素进行排序

问题描述

我正在尝试使用另一个队列对队列中存在的元素（整数）进行排序。队列没有负数或重复值队列必须按升序排序。（头->尾）示例输入：4 [7 3 9 5]

输出：[3 5 7 9]

import java.util.*;

public class Source {
public static void main(String args[]) {
    Queue<Integer> queue = new LinkedList<Integer>();
    Scanner s = new Scanner(System.in);
    int n = s.nextInt();
    while (n-- > 0)
        queue.add(s.nextInt());
    sort(queue);
}

// Method to sort the queue
static void sort(Queue<Integer> queue) {
    Queue<Integer> queue2 = new LinkedList<Integer>();
    queue2.add(queue.remove());
    while(queue.size()!=0){
    int temp = queue.remove();
   queue2.add(temp);
    while(temp<queue2.peek()){
        queue2.add(queue2.remove());
    }
    }
    System.out.println(queue2);
}

}

标签： javadata-structuresqueue

解决方案

由于队列中没有负数，我想按如下方式操作：
1. 在第一个队列中插入一个负数（“虚拟”技术）。
2.在第一个队列中搜索最小的数字，直到你碰到假人。
3. 移除假人。
4. 在队列中搜索您在步骤 2 中找到的最小值，将其移除并将其插入到第二个队列中。
5. 执行这 4 个步骤，直到第一个队列为空。

Java代码：

static void sort(Queue<Integer> q1) {
    Queue<Integer> q2 = new Queue<Integer>();
    int min=Integer.MAX_VALUE;
    while (!q1.isEmpty())
    {
        q1.insert(-1);
        while(q1.head() != -1)
        {
            if (q1.head() < min)
            {
                min=q1.head();
            }
            q1.insert(q1.remove());

        }
        q1.remove(); //removing the -1
        while (q1.head() != min)
        {
            q1.insert(q1.remove());
        }
        min = Integer.MAX_VALUE;
        q2.insert(q1.remove()); //inserting the minimum to the second queue.
    }
    System.out.println(q2);
}

推荐阅读