队列概述

  • 队列的特点：先进先出
  • 分类
    • 单端队列：只有一个口可以进，一个口可以出
    • 双端队列：两个口都可以进，两个口都可以出

队列的四种操作（单端队列为例）

  • 访问 Access 时间复杂度 O(N)
    遍历从前往后一个个找，从而进行访问
  • 搜索 Search 时间复杂度 O(N)
    需要对队列进行遍历查找
  • 插入 Insert 时间复杂度 O(1)

只能在尾端插入

  • 删除 Remove 时间复杂度 O(1)
    只能删除队列头

队列实际的常用操作（Java）

  • 创建队列

    1.       //Create a queue
    2.       Queue<Integer> queue = new LinkedList<>();

  • 添加元素

    1.       //Add element
    2.       //Time Complexity:O(1)
    3.       queue.add(1);
    4.       queue.add(2);
    5.       queue.add(3);
    6.       //[1,2,3]
    7.       System.out.println(queue.toString());

  • 获取即将出队的元素

    1.       //Get the head of queue
    2.       //Time Complexity:O(1)
    3.       int temp1 = queue.peek();
    4.       //1
    5.       System.out.println(temp1);

  • 删除即将出队的元素

    1.       //Remove the head of queue
    2.       //Time Complexity:O(1)
    3.       int temp2 = queue.poll();
    4.       //1
    5.       System.out.println(temp2);
    6.       //[2,3]
    7.       System.out.println(queue.toString());

  • 判断队列是否为空

    1.       //Queue is empty?
    2.       //Time Complexity:O(1)
    3.       //false
    4.       System.out.println(queue.isEmpty());

  • 队列长度

    1.       //The length of Queue
    2.       // Time Complexity:O(1)
    3.       //2
    4.       System.out.println(queue.size());

  • 遍历队列

    1.       //Time Complexity:O(1) 边删除边遍历
    2.       while (!queue.isEmpty()) {
    3.           int temp = queue.poll();
    4.           System.out.println(temp);
    5.       }

LeetCode练习

#933

参考：https://www.bilibili.com/read/cv8623247?spm_id_from=333.788.b_636f6d6d656e74.14