众所周知队列是一种基础的数据结构。 但是队列的应用十分的广泛，在计算机网络中会用到队列，在并发编程中会用到阻塞队列，在线程池中会用到工作队列，这些基本遵从FIFO原则，不过也有一种特殊的队列，优先队列，也叫做堆。 聊聊在算法中队列的巧妙运用，第一个，是大家很熟悉的bfs，需要一个队列，不再详细解释。 第二个，求二进制。十进制转二进制，大家都知道怎么做，不停%2 不过如果求1~n的所有二级制排列，那么这样做无疑是非常耗费时间的， 1~n每一个数都需要去做这样的工作，想一想就知道复杂度一定会很大，n越大越麻烦。 那么请看一棵树
1 / \ 0 1 /\ /\ 0 1 0 1请找规律。1 ->1 2 ->10 3->11 4->100 5->101 6->110 7->111
看明白了吗，很像层序遍历吧？ 那么这里不需要去建一棵树。 需要一个队列。
这里贴代码。
import java.util.*; public class Main { public static void main(String[] args) { Queue<String> queue = new LinkedList<>(); queue.offer("1"); Scanner in = new Scanner(System.in); int n = in.nextInt(); while(!queue.isEmpty() && (n > 0)) { String x = queue.poll(); System.out.print(x + " "); n -= 1; if(n == 0) break; String a = x + "0"; String b = x + "1"; queue.offer(a); queue.offer(b); } } } 16 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000输出的就像这样。
以及可以运用于拓扑排序。 这是图论中的一种算法，我觉得很巧妙，给出一些关系，继而判断它们之间的关系。
那么做法是这样的，首先抽象化成图， 计算所有点的入度。 删去入读为0的点，不如说，入度为0是排在前面的点，删去以后也要去边，就是要将那些和这个点有关的点，入度也要减去1，如果这个点的入度为0，重复上面的操作，如果有环就是不存在拓扑排序。 那么怎么计算快呢，用普通的遍历去肯定是慢的，那么这里用队列，如果是按名次，或是字典序列，那么就用优先队列。
看一个题目。
题目描述 有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。 输入描述: 输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。 输出描述: 给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。 其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。 示例1 输入 4 3 1 2 2 3 4 3 输出 1 2 4 3
这就是经典的拓扑排序吧，不过这里一开始我用了普通队列，直接错了，因为题目要求了编号小的队伍在前，所以要用优先队列。
贴代码。
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int n = sc.nextInt(); int m = sc.nextInt(); int[][] edge = new int[n + 1][n + 1]; int[] degrees = new int[n + 1]; for(int i = 0; i < m; i ++) { int x = sc.nextInt(); int y = sc.nextInt(); edge[x][y] = y; degrees[y] ++; } PriorityQueue<Integer> queue = new PriorityQueue<>(); for(int i = 1; i <= n; i ++) { if(degrees[i] == 0) queue.offer(i); } List<String> res = new ArrayList<>(); while(!queue.isEmpty()) { int cur = queue.poll(); res.add(String.valueOf(cur)); for(int i = 0; i < edge[cur].length; i ++) { if(-- degrees[edge[cur][i]] == 0) queue.offer(edge[cur][i]); } } System.out.println(String.join(" ", res)); } } }