寒假冬令营（算法编程）1月11日（队列）

题目描述（1）

B3616 【模板】队列

请你实现一个队列（queue），支持如下操作：

• push(x)：向队列中加入一个数 x。

• pop()：将队首弹出。如果此时队列为空，则不进行弹出操作，并输出 ERR_CANNOT_POP。

• query()：输出队首元素。如果此时队列为空，则输出 ERR_CANNOT_QUERY。

• size()：输出此时队列内元素个数。

输入格式

第一行，一个整数 n，表示操作的次数。

接下来 n 行，每行表示一个操作。格式如下：

• 1 x，表示将元素 x 加入队列。

• 2，表示将队首弹出队列。

• 3，表示查询队首。

• 4，表示查询队列内元素个数。

输出格式

输出若干行，对于每个操作，按「题目描述」输出结果。

每条输出之间应当用空行隔开。

输入输出样例

输入

13
1 2
3
4
1 233
3
2
3
2
4
3
2
1 144
3

输出

2
1
2
233
0
ERR_CANNOT_QUERY
ERR_CANNOT_POP
144

说明/提示

样例解释

首先插入 2，队首为 2、队列内元素个数为 1。 插入 233，此时队首为 2。 弹出队首，此时队首为 233。 弹出队首，此时队首为空。 再次尝试弹出队首，由于队列已经为空，此时无法弹出。 插入 144，此时队首为 144。

数据规模与约定

对于 100%的测试数据，满足 n≤10000，且被插入队列的所有元素值是 1,1000000 以内的正整数。

解题结果

Java

实现了一个队列数据结构，支持四种操作：push用于将元素加入队列，pop用于将队首元素弹出，query用于输出队首元素，以及size用于输出队列内元素个数。通过使用LinkedList作为底层数据结构，代码分别实现了这四种操作，并根据题目要求输出相应结果。在弹出队首元素和查询队首元素时，代码进行了判空处理，防止在空队列的情况下产生错误输出。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
?
public class Main {
 ?  public static void main(String[] args) {
 ? ? ?  Scanner scanner = new Scanner(System.in);
 ? ? ?  int n = scanner.nextInt();
 ? ? ?  scanner.nextLine();
?
 ? ? ?  Queue<Integer> queue = new LinkedList<>();
?
 ? ? ?  for (int i = 0; i < n; i++) {
 ? ? ? ? ?  String[] operation = scanner.nextLine().split(" ");
 ? ? ? ? ?  int type = Integer.parseInt(operation[0]);
?
 ? ? ? ? ?  switch (type) {
 ? ? ? ? ? ? ?  case 1:
 ? ? ? ? ? ? ? ? ?  int x = Integer.parseInt(operation[1]);
 ? ? ? ? ? ? ? ? ?  push(queue, x);
 ? ? ? ? ? ? ? ? ?  break;
 ? ? ? ? ? ? ?  case 2:
 ? ? ? ? ? ? ? ? ?  pop(queue);
 ? ? ? ? ? ? ? ? ?  break;
 ? ? ? ? ? ? ?  case 3:
 ? ? ? ? ? ? ? ? ?  query(queue);
 ? ? ? ? ? ? ? ? ?  break;
 ? ? ? ? ? ? ?  case 4:
 ? ? ? ? ? ? ? ? ?  size(queue);
 ? ? ? ? ? ? ? ? ?  break;
 ? ? ? ? ?  }
 ? ? ?  }
 ?  }
?
 ?  private static void push(Queue<Integer> queue, int x) {
 ? ? ?  queue.offer(x);
 ?  }
?
 ?  private static void pop(Queue<Integer> queue) {
 ? ? ?  if (queue.isEmpty()) {
 ? ? ? ? ?  System.out.println("ERR_CANNOT_POP");
 ? ? ?  } else {
 ? ? ? ? ?  queue.poll();
 ? ? ?  }
 ?  }
?
 ?  private static void query(Queue<Integer> queue) {
 ? ? ?  if (queue.isEmpty()) {
 ? ? ? ? ?  System.out.println("ERR_CANNOT_QUERY");
 ? ? ?  } else {
 ? ? ? ? ?  System.out.println(queue.peek());
 ? ? ?  }
 ?  }
?
 ?  private static void size(Queue<Integer> queue) {
 ? ? ?  System.out.println(queue.size());
 ?  }
}

题目描述（2）

933. 最近的请求次数

. - 力扣（LeetCode）

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

• RecentCounter() 初始化计数器，请求数为 0 。

• int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证 每次对 ping 的调用都使用比之前更大的 t 值。

示例 1：

输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]
?
解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1); ? ? // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100); ? // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

提示：

• 1 <= t <= 109

• 保证每次对 ping 调用所使用的 t 值都 严格递增

• 至多调用 ping 方法 104 次

解题结果

Java

实现了一个名为RecentCounter的类，用于计算在特定时间范围内最近的请求数量。该类使用一个队列来存储请求的时间戳，每次调用ping方法时将新的请求时间加入队列，并移除队列中在时间范围外的请求（即在过去3000毫秒之前的请求）。最终返回队列的大小，表示在过去3000毫秒内发生的所有请求数。此实现基于一个假设，即每次对ping方法的调用都使用比之前更大的时间戳。

class RecentCounter {
 ?  private Queue<Integer> requests;
?
 ?  public RecentCounter() {
 ? ? ?  this.requests = new LinkedList<>();
 ?  }
?
 ?  public int ping(int t) {
 ? ? ?  requests.offer(t);
?
 ? ? ?  // 移除过期的请求，即在[t-3000, t]范围外的请求
 ? ? ?  while (requests.peek() < t - 3000) {
 ? ? ? ? ?  requests.poll();
 ? ? ?  }
?
 ? ? ?  return requests.size();
 ?  }
}