数组模拟队列-java

我们主要通过数组来模拟一下队列，实现基本的入队、出队、判断队空和查询队头元素的操作。

我们主要通过数组来模拟一下队列，实现基本的入队、出队、判断队空和查询队头元素的操作。

一、队列

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

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≤1000000000
所有操作保证合法。

二、算法思路

队列的主要特点是先进先出，我们可以想象成平常在超市排队结账，最早去排队的可以先结账出去。

1.变量解释

图1.1队列图示 

我们引入一维整型数组queue来存储队列中的值 ；整型变量head用来表示队头指针，整型变量rear用来表示队尾指针。

2.队列初始化

我们将head的值默认初始化为0，rear的初始化为-1，这样便于我们后续的操作。

    //队列初始化
    public static void init(){
        head = 0;
        rear = -1;
    }

3.向队尾插入一个值x

图3.1 入队图示

我们执行入队操作，将x放入队列。我们要先让队尾指针后移，然后再将x放入数组queue中即可。即queue[++rear] = x。（注：因为我们队尾指针rear的初始值为-1，直接用的话会数组越界，所以我们都是先让队尾指针加1，然后再存储值） 

    //入队
    public static void push(int x){
        queue[++rear] = x;
    }

4.从队头弹出一个元素

图4.1 出队图示

我们进行出队操作只需要让队头指针后移，这样我们我们就相当于让原本的队头元素出队了。即head++。

    //出队
    public static void pop(){
        head++;
    }

5.判断队列是否为空

我们创建一个isEmpty的方法，返回值设置成布尔类型。从队列的初始化状态观察我们就可以发现，当队头指针在队尾指针的后面时即head > rear时，此时队列就是空队列，没有存储任何值；当队头指针和队尾指针相等时即head = rear，说明此时队列中仅存储了1个值；当队头指针在队尾指针后面时即head < rear，说明此时队列中共有rear - head + 1个值。我们可以看图1.1想象一下。

    public static boolean isEmpty(){
        return head > rear;
    }

 6.查看队头元素

此时我们的队头指针head就是队头元素在队列queue中的下标即queue[head]就是队头元素的值如图1.1所示。

    //查看队头元素
    public static int query(){
        return queue[head];
    }

三、代码如下

1.代码如下（示例）：

import java.io.*;
import java.util.*;
public class Main {
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N = 100010;
    static int[] queue = new int[N];
    static int head;
    static int rear;
    public static void main(String[] args) {
        Scanner sc = new Scanner(br);
        init();
        int m = Integer.parseInt(sc.nextLine());
        while (m-- > 0){
            String[] str = sc.nextLine().split(" ");
            int x;
            String cmd = str[0];
            //入队
            if (cmd.equals("push")){
                x = Integer.parseInt(str[1]);
                push(x);
            }
            //出队
             else if (cmd.equals("pop")) {
                pop();
            }
             //判断队列是否为空
             else if (cmd.equals("empty")) {
                pw.println(isEmpty() == true? "YES": "NO");
            }
             //查看队头元素
             else if (cmd.equals("query")) {
                pw.println(query());
            }
        }
        pw.flush();
    }
    //队列初始化
    public static void init(){
        head = 0;
        rear = -1;
    }
    //入队
    public static void push(int x){
        queue[++rear] = x;
    }
    //出队
    public static void pop(){
        head++;
    }
    public static boolean isEmpty(){
        return head > rear;
    }
    //查看队头元素
    public static int query(){
        return queue[head];
    }
}

2.读入数据

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

3.代码运行结果

NO
6
YES
4

对列元素：6入队、6出队、3入队、4入队、3出队、6入队。最后的队列元素为 4 6。

总结

我们主要通过数组来模拟一下队列，实现基本的入队、出队、判断队空和查询队头元素的操作，代码很简单，大家看一下思路就能懂。