Code02-队列

Posted Feb 11, 2025 Updated Jun 30, 2025

By hhhi21g

12 min read

洛谷 P1540

  
package luogu;

import java.util.Queue;
import java.util.Scanner;
import java.util.concurrent.ArrayBlockingQueue;

public class P1540 {

	public static void main(String[] args) {	
		int m,n;
		Scanner scanner = new Scanner(System.in);
		m = scanner.nextInt();
		n = scanner.nextInt();
		
		Queue<Integer> q = new ArrayBlockingQueue<>(m);
		int []word = new int[n];
		
		for(int i = 0;i<n;i++) {
			word[i] = scanner.nextInt();
		}
		
		int cnt = 0;
		int contain = 0;
		for(int i = 0;i<n;i++) {
			if(!q.contains(word[i])) {
				if(q.size() == m) {
					q.poll();
				}
				q.offer(word[i]);
				cnt++;
			}
		}
		
		System.out.println(cnt);
	}
}

简单的队列应用，主要为标准库中队列的使用，该题中使用限制大小的队列ArrayBlockQueue

洛谷 P1886

  
package luogu;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class P1886_02 {

    public static void main(String[] args) throws IOException {
        int n, k;
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = reader.readLine().split(" ");
        n = Integer.parseInt(firstLine[0]);
        k = Integer.parseInt(firstLine[1]);
        
        int[] aSeq = new int[n];
        String[] elements = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            aSeq[i] = Integer.parseInt(elements[i]);
        }

        // 存储最小值和最大值
        int[] aMin = new int[n - k + 1];
        int[] aMax = new int[n - k + 1];

        // 双端队列存储索引，确保队列中从前到后是递增或递减的
        Deque<Integer> minDeque = new ArrayDeque<>(n-k+1);
        Deque<Integer> maxDeque = new ArrayDeque<>(n-k+1);

        for (int i = 0; i < n; i++) {
            // 删除过期元素
            if (!minDeque.isEmpty() && minDeque.peekFirst() == i - k) {
                minDeque.pollFirst();
            }
            if (!maxDeque.isEmpty() && maxDeque.peekFirst() == i - k) {
                maxDeque.pollFirst();
            }

            // 更新最小值队列
            while (!minDeque.isEmpty() && aSeq[minDeque.peekLast()] >= aSeq[i]) {
                minDeque.pollLast();
            }
            minDeque.offerLast(i);

            // 更新最大值队列
            while (!maxDeque.isEmpty() && aSeq[maxDeque.peekLast()] <= aSeq[i]) {
                maxDeque.pollLast();
            }
            maxDeque.offerLast(i);

            // 记录当前窗口的最小值和最大值
            if (i >= k - 1) {
                aMin[i - k + 1] = aSeq[minDeque.peekFirst()];
                aMax[i - k + 1] = aSeq[maxDeque.peekFirst()];
            }
        }

        // 使用StringBuilder来拼接输出结果
        StringBuilder sbMin = new StringBuilder();
        StringBuilder sbMax = new StringBuilder();
        for (int i = 0; i < aMin.length; i++) {
            sbMin.append(aMin[i]).append(' ');
            sbMax.append(aMax[i]).append(' ');
        }
        if (sbMin.length() > 0) sbMin.setLength(sbMin.length() - 1);
        if (sbMax.length() > 0) sbMax.setLength(sbMax.length() - 1);
        System.out.println(sbMin);
        System.out.println(sbMax);
    }
}

思路：

滑动窗口；

使用双端队列 Deque 存储最大值最小值对应索引;
删除已经不在窗口中的元素：当索引队列中头元素等于i-k,pollFirst
分别更新最小值、最大值队列：
- 当新进入窗口的元素<=最小值队列尾对应的元素时，从尾部poll；
当新进入窗口的元素>=最大值队列尾对应的元素时，从尾部poll(pollLast);
- 找到新元素的位置，从尾部加入队列 offerLast
- 完成后，队列头对应元素分别为当前滑块内最大/最小值，peekFirst,存入到结果数组

注意：高效的输入输出

输入：BufferedReader

使用实例：

  
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] firstLine = reader.readLine().split(" ");
int n = Integer.parseInt(firstLine[0]);  //上面定义的String[] firstLine行的第一个元素

将scanner换为readerTLE的测试通过；

输出：StringBuilder

使用实例：

  
StringBuilder sbMin = new StringBuilder();
for(int i = 0;i<aMin.length;i++){
    sbMin.append(aMin[i]).append(' ');
}
sbMin.setLength(sbMin.length()-1);
System.out.println(sbMin);

ZOJ 3210

  
package ZOJ;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class ZOJ_3210 {

    public static void main(String[] args) {
    	Scanner scanner = new Scanner(System.in);
		int total = scanner.nextInt();
		int len;
		for(int cnt = 0;cnt<total;cnt++) {
			len = scanner.nextInt();
		
			int[] input = new int[len];
			int[] output = new int[len];
			
			Stack<Integer> s = new Stack<>();
			Queue<Integer> q = new LinkedList<>();
			
			boolean isStack = true;
			boolean isQueue = true;
			
			for(int i = 0;i<len;i++) {
				input[i] = scanner.nextInt();
				s.push(input[i]);
				q.offer(input[i]);
			}
			for(int i = 0;i<len;i++) {
				output[i] = scanner.nextInt();
			}
			
			for(int i = 0;i<len;i++) {
				if(!s.isEmpty() && s.pop()!= output[i]) isStack = false;
				if(!q.isEmpty() && q.poll() != output[i]) isQueue = false;
				if(!isStack && !isQueue)break;
			}
			
			if(isStack && isQueue)
				System.out.println("both");
			else if(isStack)
				System.out.println("stack");
			else if(isQueue)
				System.out.println("queue");
			else 
				System.out.println("neither");
			}
		scanner.close();
    }
}

栈与队列的简单判断

掉坑位置:

想要边接受输出的序列边判断，导致没有接受完输入就有可能退出，出现 非零返回 的错误

ZOJ 1948

  
package ZOJ;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;

public class ZOJ_1948 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int scenario = 1;
		
		while(true) {
			int t = scanner.nextInt();  // 每组数据中的团队数量
			if(t == 0) break;
			
			// 建立元素到团队的映射
			Map<Integer,Integer> elementToTeam = new HashMap<>();
			for(int i = 0;i<t;i++) {
				int n = scanner.nextInt();  // 团队中元素的数量
				for(int j = 0;j<n;j++) {
					int element = scanner.nextInt();
					elementToTeam.put(element, i);
				}
			}
			
			Queue<Integer> teamQueue = new LinkedList<>();
			Map<Integer,Queue<Integer>> teamInternalQueue = new HashMap<>();
			
			System.out.println("Scenario #" + scenario++);
			while(true) {
				String command = scanner.next();
				if(command.equals("STOP")) {
					break;
				}else if(command.equals("ENQUEUE")) {
					int x = scanner.nextInt();
					int team = elementToTeam.get(x);
					
					// 团队队列不含当前元素的团队
					if(!teamInternalQueue.containsKey(team)) {
						teamInternalQueue.put(team, new LinkedList<>());
						teamQueue.offer(team);
					}
					
					//将元素添加到其团队
					teamInternalQueue.get(team).offer(x);
				}else if(command.equals("DEQUEUE")) {
					int team = teamQueue.peek();
					Queue<Integer> internalQueue = teamInternalQueue.get(team);
					
					int element = internalQueue.poll();
					System.out.println(element);
					
					if(internalQueue.isEmpty()) {
						teamQueue.poll();
						teamInternalQueue.remove(team);
					}
				}
			}
			System.out.println();
		}
		scanner.close();
	}
}

思路：

依靠ds

根据团队队列概念，分析，dequeue按照enqueue的团队序号弹出：
即若第一个进入团队队列的元素属于团队1，那么dequeue时将加入的团队1的元素全部弹出才会弹出其他团队的元素
选择合适的类型，使用HashMap, 建立：
- 元素到团队序号的映射，Map<Integer,Integer> elementToTeam = new HashMap<>()
- 团队队列：Queue<Integer> teamQueue = new LinkedList<>()
- 团队序号到队列的映射，Map<Integer,Queue<Integer>> teamInternalQueue = new HashMap<>()
先接收普通数据：
- 团队数量，每个团队中元素数目及元素
再接收带有指令的输入：
- ENQUEUE：
  - 通过.get()获得该入队队列对应的团队序号；
  - 如果团队队列中 不包含该团队序号 ，创建该团队序号与一个空队列的映射
    并将该团队序号offer进团队序列；
  - 将该元素添加到团队序号对应的队列中：teamInternalQueue.get(team).offer(x)
- DEQUEUE：
  - 获取团队队列中头元素，即第一个入队元素的团队序号；
  - .get()获取该团队序号对应的队列
  - 出队直至该单独队列为空，将该团队序号从团队队列中取出，删除该映射(.remove())
- STOP: 结束程序

注意：

HashMap的使用

可以定义两个泛型，前面的决定key元素的类，后面的决定value元素的类；且key元素不能重复

举例，定义：

  
HashMap<String,Integer> map = new HashMap<String,Integer>();

1 map.put("Tom",100);
1 int score = map.get("Tom");

  
map.size();  //返回key-value的组数，即map集合中数据数量

  
int score = map.remove("Tom");  //移除相应key的数据，并返回对应的value值

  
map.containsKey(key);  //是否含有当前key对应的value

该题中输入格式的应对
给出例如：ENQUEUE 101
因为指令和数据之间含有空格，可以通过scanner.next()获取”ENQUEUE”，再正常获取数据

UVA 12207

  
package UVA;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class UVA_12207 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int peo,commandCnt;
		int caseCnt = 0;
		while(true) {
			peo = scanner.nextInt();
			commandCnt = scanner.nextInt();
			if(peo == 0 && commandCnt == 0) {
				break;
			}
			caseCnt ++;
			System.out.println("Case "+caseCnt+":");
			Deque<Integer> q = new LinkedList<>();
			Deque<Integer> qPre = new ArrayDeque<>();
			int min = peo<commandCnt?peo:commandCnt;
			for(int i = 1;i<=min;i++) {
				q.offer(i);
			}

			for(int j = 0;j<commandCnt;j++) {
				String command = scanner.next();
				if(command.equals("N")) {
					int savePeo;
					if(!qPre.isEmpty()) {
						savePeo = qPre.peek();
						qPre.pop();
						q.offer(savePeo);
						System.out.println(savePeo);
					}else {
						savePeo = q.peek();					
						q.poll();
						q.offer(savePeo);
						System.out.println(savePeo);
					}
				}else if(command.equals("E")) {
					int prePeo = scanner.nextInt();		
					q.remove(prePeo);
					qPre.remove(prePeo);
					qPre.push(prePeo);
				}
			}
		}
	}
}

思路：

分析使用两种数据结构：队列存储待处理的病人；栈存储需要优先处理的病人
待处理队列的初始化：初始化为自然数序列
命令为E：
- 获得需要有限处理的病人序号prePeo
- 该prePeo病人需要是最后一个加入优先栈，且队列和栈的前面都不存在该病人，这里使用remove()方法
- 随后push入优先处理的栈
命令为N：
- 若优先处理的栈为空：
  此时没有需要处理的病人，直接出队列一个数据，再从尾部加入数据即可；
- 若优先处理的栈不为空：
  需要优先处理栈顶元素，pop出处理，再从队列尾入队即可

注意：

最开始的朴素思路为：使用两个队列，出现需要优先处理的数据时，将其加入到一个空队列，再遍历原有队列从而获得一个新队列，结果超时，应选取合适的数据结构；
忘记了remove方法，使用后很多问题迎刃而解
初始化队列时，起初想要循环至人数，后分析取两个输入的最小值即可，看见测试用例中有两个数据相差较大而发现问题。

数据结构与算法

刷题

This post is licensed under CC BY 4.0 by the author.

洛谷 P1540

洛谷 P1886

ZOJ 3210

ZOJ 1948

UVA 12207

Trending Tags