目的

用数组实现队列

问题描述

实现一个队列，队列初始为空，支持四种操作：

  1. push x – 向队尾插入一个数 x；
  2. pop – 从队头弹出一个数；
  3. empty – 判断队列是否为空；
  4. query – 查询队头元素。

现在要对队列进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。
输出格式
对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。
数据范围
1≤M≤100000
1≤x≤109
所有操作保证合法。
输入样例：

  1. 10
  2. push 6
  3. empty
  4. query
  5. pop
  6. empty
  7. push 3
  8. push 4
  9. pop
  10. query
  11. push 6

输出样例：

  1. NO
  2. 6
  3. YES
  4. 4

方法

  1. static int N = 100010; //规模视具体问题而定
  2. int[] q = new int[N];
  3. int hh = 0, tt = -1;    //设置头尾指针分别为0和-1

当 hh <= tt 说明队列不为空，此时hh指向队头元素，tt指向队尾元素

代码

  1. import java.util.*;
  2. import java.io.*;
  4. public class Main {
  5.     static int N = 100010;
  6.     public static void main(String[] sss) throws IOException{
  7.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  8.         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  9.         int m = Integer.parseInt(br.readLine());
  10.         int[] q = new int[N];
  11.         int hh = 0, tt = -1;
  13.         while (m-- > 0) {
  14.             String[] str = br.readLine().split(" ");
  15.             int x = 0;
  16.             switch(str[0]) {
  17.                 case "push":
  18.                     x = Integer.parseInt(str[1]);
  19.                     q[++tt] = x;
  20.                     break;
  21.                 case "pop":
  22.                     if (hh <= tt)
  23.                         hh++;
  24.                     break;
  25.                 case "empty":
  26.                     if (hh <= tt) bw.write("NO\n");
  27.                     else bw.write("YES\n");
  28.                     break;
  29.                 case "query":
  30.                     if (hh <= tt)
  31.                         x = q[hh];
  32.                     bw.write(x + "\n");
  33.                     break;
  34.             }
  35.         }
  38.         br.close();
  39.         bw.close();
  41.     }
  42. }

参考

AcWing 829. 模拟队列