【Java】想进大厂？你应该知道的算法经典习题(队列)

✅作者简介：大家好我是烫嘴的辛拉面，大家可以叫我拉面。
📜个人主页: weixin_49405762的博客
📕系列专栏： 经典算法习题集
🌞为大🔥推荐一款刷题神器哦👉 点击跳转进入网站

前言：我将在专栏 经典算法习题集持续更新，整理牛客网经典算法的习题练习，如果感兴趣请关注专栏。牛客网除了算法题单之外还有其他热门的各种提单，应有尽有，大家快刷起来吧点击跳转进入牛客网

✏️队列

✒️AB7 【模板】队列

题目描述

请你实现一个队列。
操作：
push x：将 x x\ x 加入队尾，保证 x x\ x 为 int 型整数。
pop：输出队首，并让队首出队
front：输出队首：队首不出队

输入描述：
第一行为一个正整数 n n\ n ，代表操作次数。(1≤n≤100000)(1 \leq n \leq 100000)(1≤n≤100000)
接下来的 n n\ n ，每行为一个字符串，代表一个操作。保证操作是题目描述中三种中的一种。

输出描述：
如果操作为push，则不输出任何东西。
如果为另外两种，若队列为空，则输出 "error“
否则按对应操作输出。

示例1
输入：
6
push 1
pop
front
push 2
push 3
pop

输出：
1
error
2

解题思路

在本题中，我们使用 ArrayList 结构存放数据，而不直接使用 int[] 结构存放数据，主要是因为后者 初始化 要开辟很大的 内存空间，不然后续如果加入 太多 的数据，存不下 了怎么办。与此同时，我们还要维护一个 指针，它永远指向当前的 队头。

    push 操作，没啥好说的，直接调用 add 方法即可。
    pop 操作，需要返回 当前指针 指向位置的元素。同时，指针 向后移动一位。
    front 操作和 pop 操作类似，区别在于，不需要 移动指针的位置。
1
2
3
4
5

代码实现(Java)

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = Integer.valueOf(scan.nextLine().trim());
        ArrayList<String> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String[] operator = scan.nextLine().split(" ");
            if ("push".equals(operator[0])) {
                push(operator[1]);
            } else if ("pop".equals(operator[0])) {
                ans.add(pop());
            } else {
                ans.add(front());
            }
        }
        for (String str : ans) {
            System.out.println(str);
        }
    }
    public static ArrayList<String> arr = new ArrayList<>();
    public static int index = 0;
    public static void push(String num) {
        arr.add(num);
    }
    public static String pop() {
        return index == arr.size() ? "error" : arr.get(index++);
    }
    public static String front() {
        return index == arr.size() ? "error" : arr.get(index);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

✒️AB8 【模板】循环队列

题目描述

请你实现一个循环队列，该循环队列可利用的空间大小等于nnn个int型变量的大小。
操作：
push x：将xxx加入到循环队列尾端。若循环队列已满，输出"full"(不含引号)，否则不输出任何内容。保证xxx为int型整数。
front：输出队首元素，队首不出队。若队列为空，输出"empty"(不含引号)。
pop：输出队首元素，且队首出队。若队列为空，输出"empty"(不含引号)。

输入描述：
第一行输入两个整数n,qn,qn,q (1≤n,q≤1051\le n,q \le 10^51≤n,q≤105)，表示循环队列可利用的空间大小和操作次数。
接下来的qqq行，每行一个字符串，表示一个操作。保证操作是题目描述中的一种。
输出描述：
按对应操作要求输出。

示例1

输入：
3 10
push 1
push 2
front
push 3
push 4
pop
pop
pop
front
pop

输出：
1
full
1
2
3
empty
empty

解题思路

对于循环队列我们要考虑的问题主要是，什么时候表示队列为空，什么时候队列为满？

对于可存n个整型数据的队列

如果一个下标front指示队首，下标rear指示队尾；
如果front=rear时，可以保证队列是空的，例如初始状态front=rear=0;
如果(rear+1)%(n+1)=front，即队列中如果再要存一个元素就只能覆盖front位置的元素了，说明此时队列为满
1
2
3

值得注意的细节是，对(n+1)取余，而不是对n取余。可以这么理解要判断队列满了，规定队列最多可以存n个元素，当循环队列中只剩下一个空闲存储单元时，队列就满了，这也是为什么代码中开辟的队列空间大小为（n+1)而不是n的缘由。

代码实现

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sca=new Scanner(System.in);
        int n=sca.nextInt();
        int q=sca.nextInt();
        sca.nextLine();
        String s;
        //注意这里不是n,而是n+1
        MyCirQueue queue=new MyCirQueue(n+1);
        for(int i=0;i<q;++i){
            s=sca.nextLine();
            String strs[]=s.split(" ");
            if(strs[0].equals("push")){
                queue.push(Integer.parseInt(strs[1]));
            }else if(strs[0].equals("front")){
                queue.front();
            }else{
                queue.pop();
            }
        }
    }
}
class MyCirQueue{
    int maxSize;
    int rear,front;
    int []q;
    public MyCirQueue(int maxSize){
        this.maxSize=maxSize;
        q=new int[maxSize];
        rear=0;
        front=0;
    }

    //添加元素
    public void push(int val){
        if(isFull()){
            System.out.println("full");
        }else{
            //从队尾入队
            q[rear]=val;
            //队尾下标+1
            rear=(rear+1)%maxSize;
        }
    }

    //输出但不移除队首元素
    public void front(){
        if(isEmpty()){
            System.out.println("empty");
        }else{
            //队首元素出列
            System.out.println(q[front]);
        }
    }

    //输出且移除队首元素
    public void pop(){
        if(isEmpty()){
            System.out.println("empty");
        }else{
            //队首元素出列
            System.out.println(q[front]);
            //队首下标+1
            front=(front+1)%maxSize;
        }
    }

    //判断队列是否为空
    public boolean isEmpty(){
        if(rear==front){
            return true;
        }
        return false;
    }

    //判断队列是否为满
    public boolean isFull() {
        if((rear+1)%maxSize==front){
            return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84