题目链接

【模板】队列操作

题目描述

给定一个空队列，依次执行 n 个操作，操作类型定义如下：

  • 1 x：将整数 x 入队；
  • 2：若队列非空，则仅将队头元素出队，否则输出 ERR_CANNOT_POP；
  • 3：查询并输出队首元素，队列为空时输出 ERR_CANNOT_QUERY；
  • 4：输出队列当前元素数量。

输入描述:

  • 第一行包含整数 n，表示操作总数。
  • 接下来 n 行，每行描述一个操作。

输出描述:

  • 对于每个操作 2、3、4，按执行顺序，每行输出对应的结果。

解题思路

这是一个基础的数据结构模拟题，目标是实现一个队列并处理相应的操作。我们可以直接使用各语言提供的标准库中的队列数据结构来解决。

  • C++: 可以使用 <queue> 头文件中的 std::queue。
  • Java: 可以使用 java.util.Queue 接口，通常用 java.util.LinkedList 或 java.util.ArrayDeque 来实例化。
  • Python: 可以使用 collections.deque，它为在两端快速添加和弹出元素进行了优化。

解题步骤就是循环 n 次，每次读取操作码，然后根据操作码执行对应的队列操作，并根据题意处理边界情况（如对空队列进行出队或查询操作）并打印结果。

代码

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    queue<int> q;
    int op, x;
    for (int i = 0; i < n; ++i) {
        cin >> op;
        if (op == 1) {
            cin >> x;
            q.push(x);
        } else if (op == 2) {
            if (q.empty()) {
                cout << "ERR_CANNOT_POP" << endl;
            } else {
                q.pop();
            }
        } else if (op == 3) {
            if (q.empty()) {
                cout << "ERR_CANNOT_QUERY" << endl;
            } else {
                cout << q.front() << endl;
            }
        } else if (op == 4) {
            cout << q.size() << endl;
        }
    }
    return 0;
}

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            int op = sc.nextInt();
            switch (op) {
                case 1:
                    int x = sc.nextInt();
                    q.add(x);
                    break;
                case 2:
                    if (q.isEmpty()) {
                        System.out.println("ERR_CANNOT_POP");
                    } else {
                        q.poll();
                    }
                    break;
                case 3:
                    if (q.isEmpty()) {
                        System.out.println("ERR_CANNOT_QUERY");
                    } else {
                        System.out.println(q.peek());
                    }
                    break;
                case 4:
                    System.out.println(q.size());
                    break;
            }
        }
    }
}

from collections import deque

n = int(input())
q = deque()

for _ in range(n):
    line = input().split()
    op = int(line[0])
    if op == 1:
        q.append(int(line[1]))
    elif op == 2:
        if not q:
            print("ERR_CANNOT_POP")
        else:
            q.popleft()
    elif op == 3:
        if not q:
            print("ERR_CANNOT_QUERY")
        else:
            print(q[0])
    elif op == 4:
        print(len(q))

算法及复杂度

  • 算法：队列模拟
  • 时间复杂度：，其中 N 是操作的总数。标准队列的每次操作（入队、出队、查询队首）的平均时间复杂度都是 。
  • 空间复杂度：，在最坏的情况下，所有操作都是入队操作，队列中将存储 N 个元素。