模拟队列

用数组模拟队列

队列的特点：先进先出

模板

普通队列

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt)
{

}

循环队列

// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh != tt)
{

}

题目

AcWing

829 模拟队列

Ac829 模拟队列

描述

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

(1) “push x” – 向队尾插入一个数x；

(2) “pop” – 从队头弹出一个数；

(3) “empty” – 判断队列是否为空；

(4) “query” – 查询队头元素。

现在要对队列进行M个操作，其中的每个操作3和操作4都要输出相应的结果。

解答

import java.io.*;
public class Main {
	static final int N = 100010;
	static int[] q = new int[N];
    static int hh = 0;
    static int tt = -1;
    
    //入队
    public static void push(int val){
        q[++tt] = val;
    }
    
    //出队
    public static void pop(){
        hh++;
    }
    
    //是否为空
    public static boolean empty(){
        return hh > tt; // 大于就是空
    }
    
    //查询对头
    public static int query(){
        return q[hh];
    }
    
    //查询队尾
    public static int queryToTail(){
        return q[tt];
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine());
        
        while(m-->0){
            String[] s = br.readLine().split(" ");
            
            if(s[0].equals("push")) {
				int val = Integer.parseInt(s[1]);
				push(val);
			}else if(s[0].equals("pop")) {
				pop();
			}else if(s[0].equals("query")) {
				System.out.println(query());
			}else {
                if(empty()) {
					System.out.println("YES");
				}else {
					System.out.println("NO");
				}
            }
        }
    }
}