知识点补充

队列：先进先出
- 插入的队尾
- 删除的是队头
- 查询的队头

题目描述

模拟队列的插入队尾，删除队头，查询对头，判断队列是否为空。

输入样例

10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

输出样例

NO
6
YES
4

算法1

(模拟队列) $O(n)$

思路:需要头尾两个指针(hh = 0,dd = -1),一个数组存储队列元素即可.
- 插入队列的话就是q[加加tt]=x;
- 弹出队列的话就是hh++; 头指针向后移动
- 查询队头的话就是q[hh]
- 判断队列是否为空就是:hh <= tt is empty else not empty

时间复杂度：$O(n)$

参考文献：y总

Java 代码

import java.util.Scanner;

/**
 * 模拟队列
 *   队尾插入元素，队头弹出元素
 */
public class Main {
    static int N = 100010;
    static int hh;// 队头 初始是0
    static int tt = -1;// 队尾 初始是-1 因为添加的时候从0开始添加 ++tt
    static int[] q = new int[N];// 队列

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        while (m-- > 0){
            String op = scan.next();
            if ("push".equals(op)){// 添加
                int x = scan.nextInt();
                q[++tt] = x;// 队尾插入元素
            }else if("pop".equals(op)){
                ++ hh;// 弹出队头 一定是++hh 而不是--hh
            }else if("empty".equals(op)){
                System.out.println(hh <= tt?"NO":"YES");// 判空
            }else if ("query".equals(op)){
                System.out.println(q[hh]);// 查询队头
            }
        }
    }

}