数据结构和算法的学习笔记（第二部分）

3.2 、队列

3.2.1队列的一个使用场景

• 银行排队的案例:

3.2.2、队列介绍

1) 队列是一个有序列表，可以用数组或是链表来实现。

2) 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

3) 示意图：(使用数组模拟队列示意图)

3.2.3、数组模拟队列思路

• 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中maxSize 是该队列的最大容量。
• 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear 则是随着数据输入而改变，如图所示:

• 当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析

  • 1) 将尾指针往后移：rear+1 , 当 front == rear 【空】
  • 2) 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。rear == maxSize - 1[队列满]

• 以下是代码实现

/**
 * description
 * 使用数组模拟队列--->编写一个ArrayQueue类
 * @author
 * @since 2022/10/19 15:30
 */
public class ArrayQueued {
    private int maxSize; //表示数组的最大容量
    private int front; //队列头
    private int rear; //队列尾
    private int[] arr; //该数组用于存放数据，模拟队列

    public ArrayQueued(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        front = -1; //指向队列头部，分析出front是指向队列头的前一个位置
        rear = -1;  //指向队列尾部，分析出rear是指向队列尾部的具体数据（即队列最后一个数据）
    }

    //判断队列是否满
    public boolean isFull() {
        return rear == maxSize - 1;
    }

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

    //添加数据到队列
    public void addQueue(int n) {
        //判断队列是否满
        if (isFull()) {
            System.out.println("队列已满，请耐心等待");
        }
        rear++;  //让rear后移
        arr[rear] = n;
    }

    //获取队列数据
    public int getQueue() {
        //判断队列是否为空
        if (isEmpty()) {
            //通过抛出异常来处理
            throw new RuntimeException("队列为空");
        }
        front++; //取数据前让front后移
        return arr[front];
    }

    //显示队列的所有数据
    public void showQueue() {
        //遍历之前判断数组是否为空
        if (isEmpty()) {
            System.out.println("队列为空，无法获取");
        } else {
            for (int i = 0; i < arr.length; i++) {
                System.out.printf("arr[%d]=%d\n", i, arr[i]);
            }
        }
    }

    //显示队列的头数据，注意：这里不是取出数据
    public int headQueue() {
        //显示之前判断队列是否为空
        if (isEmpty()) {
            throw new RuntimeException("队列为空，无法显示");
        }
        return arr[front + 1];
    }
}

• 测试队列的代码

/**
 * description
 * 使用数组模拟队列--->编写一个ArrayQueue类
 * @author
 * @since 2022/10/19 15:30
 */
public class ArrayQueued {
    private int maxSize; //表示数组的最大容量
    private int front; //队列头
    private int rear; //队列尾
    private int[] arr; //该数组用于存放数据，模拟队列

    public ArrayQueued() {
    }

    public ArrayQueued(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        front = -1; //指向队列头部，分析出front是指向队列头的前一个位置
        rear = -1;  //指向队列尾部，分析出rear是指向队列尾部的具体数据（即队列最后一个数据）
    }

    //判断队列是否满
    public boolean isFull() {
        return rear == maxSize - 1;
    }

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

    //添加数据到队列
    public void addQueue(int n) {
        //判断队列是否满
        if (isFull()) {
            System.out.println("队列已满，请耐心等待");
        }
        //让rear后移
        rear++;
        arr[rear] = n;
    }

    //获取队列数据
    public int getQueue() {
        //判断队列是否为空
        if (isEmpty()) {
            //通过抛出异常来处理
            throw new RuntimeException("队列为空");
        }
        front++; //取数据前让front后移
        return arr[front];
    }

    //显示队列的所有数据
    public void showQueue() {
        //遍历之前判断数组是否为空
        if (isEmpty()) {
            System.out.println("队列为空，无法获取");
        } else {
            for (int i = 0; i < arr.length; i++) {
                System.out.printf("arr[%d]=%d\n", i, arr[i]);
            }
        }
    }

    //显示队列的头数据，注意：这里不是取出数据
    public int headQueue() {
        //显示之前判断队列是否为空
        if (isEmpty()) {
            throw new RuntimeException("队列为空，无法显示");
        }
        return arr[front + 1];
    }
}

• 运行过程中发现问题：
  • 即当添加三个数据后并依次取出后队列已经为空的情况却无法再次使用

• 如图，当前队列为空，但是再次添加数据时控制台会显示队列已满并抛出异常

• 由此得出结论：队列中的数组在使用过之后就不能再使用了，所以这一块就可以进行优化
  • 问题分析并优化
  • 目前数组使用一次就不能用， 没有达到复用的效果
  • 解决办法：将这个数组使用算法，改进成一个环形的队列 取模：%

3.2.4、数组模拟环形队列

• 对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)

• 分析说明：

  • 1) 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意 (rear + 1) % maxSize == front 满]
  • 2) rear == front [空]
  • 3) 分析示意图:

  

• 思路如下:

  • front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素，front 的初始值 = 0

  • rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.

  • rear 的初始值 = 0

  • 当队列满时，条件是 (rear + 1) % maxSize == front 【满】

  • 对队列为空的条件， rear == front 空
  • 当我们这样分析， 队列中有效的数据的个数 (rear + maxSize - front) % maxSize / 我们就可以在原来的队列上修改得到，一个环形队列

• 思路清晰，代码实现如下，首先把模拟队列的类写好

/**
 * description
 * 环形数组队列
 * @author
 * @since 2022/10/19 21:09
 */
public class CircleArrayQueued {
    private int maxSize; //表示数组的最大容量

    /*front 变量的含义做一个调整：
    front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素，front 的初始值 = 0*/
    private int front; //队列头

    //rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
    private int rear; //队列尾
    private int[] arr; //该数组用于存放数据，模拟队列

    public CircleArrayQueued(int arrayMaxSize) {
        maxSize = arrayMaxSize;
        arr = new int[maxSize];
    }
    //判断队列是否满
    public boolean isFull() {
        return (rear+1) % maxSize == front;
    }

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

    //添加数据到队列
    public void addQueue(int n) {
        //添加前判断队列是否满
        if(isFull()){
            System.out.println("队列满，暂时不能加入数据，请耐心等待");
        }
        //直接将数据加入即可
        arr[rear] = n;
        //将rear的指针后移，这里必须考虑取模
        rear = (rear+1)% maxSize;
    }

    //从队列取出数据
    public int getQueue() {
        //取出数据前首先判断队列是否为空
        if(isEmpty()){
            //通过抛出异常
            throw new RuntimeException("队列空，不能取出数据");
        }
        //这里需要分析出front是指向队列的第一个元素，首先先把front对应的值保存到一个临时变量，再将front后移，再将临时变量返回
        int value = arr[front];
        //后移过程中要考虑取模
        front = (front+1) % maxSize;
        return value;
    }

    //显示队列的所有数据
    public void showQueue() {
        //遍历所有数据,首先判断队列是否为空
        if (isEmpty()){
            System.out.println("队列为空，没有数据");
        }
        //思路：从front开始遍历，遍历多少个元素
        for (int i = front; i < front + size(); i++) {
            System.out.printf("arr[%d]=%d\n",i % maxSize,arr[i % maxSize]);
        }
    }
    //求出当前队列有效数据的个数，否则无法遍历
    public int size() {
        return (rear + maxSize - front) % maxSize;
    }
    //显示队列的头数据，注意不是取出数据
    public int headQueue() {
        //首先判断队列的数据是否为空
        if(isEmpty()){
            throw new RuntimeException("队列是空的，没有数据");
        }
        return arr[front];
    }
}

• 环形队列的测试

/**
 * description
 * 测试环形的数组队列
 * @author
 * @since 2022/10/19 21:04
 */
public class CircleArrayQueueDemo {
    public static void main(String[] args) {
       //测试队列，首先创建一个队列对象
        CircleArrayQueued circleArrayQueued = new CircleArrayQueued(4); //说明设置是4，其队列有效数据是3
        //创建一个key模拟用户输入
        char key =' ';
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //输出一个菜单
        while (loop) {
            System.out.println("s(show) :显示队列");
            System.out.println("e(exit) :退出程序");
            System.out.println("a(add) :添加数据到队列");
            System.out.println("g(get) :从队列取出数据");
            System.out.println("h(head) :查看队列头的数据");
            key = scanner.next().charAt(0);  //接收一个字符

            switch (key) {
                //输入s显示队列
                case 's':
                    //调用显示队列的方法
                    circleArrayQueued.showQueue();
                    break;

                //输入a添加数据
                case 'a':
                    System.out.println("请输入一个数字");
                    int value = scanner.nextInt();
                    circleArrayQueued.addQueue(value);
                    break;

                //输入g取出数据
                case 'g':
                    try {
                        int result = circleArrayQueued.getQueue();
                        System.out.printf("取出的数据是%d\n",result);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;

                //查看队列头的数据
                case 'h':
                    try {
                        int result = circleArrayQueued.headQueue();
                        System.out.printf("队列头的数据是%d\n",result);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;

                //代表退出程序
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }
}

3.2.5、集合

集合一般被定义为：由一个或多个确定的元素所构成的整体。

通俗来讲，集合就是将一组事物组合在一起。你可以将力扣的题库看作一个集合：

也可以将商店里的礼品当成一个集合

甚至可以将桌面上的物品当作一个集合。

集合有什么特性呢？

首先，集合里的元素类型不一定相同。 你可以将商品看作一个集合，也可以将整个商店看作一个集合，这个商店中有人或者其他物品也没有关系。

其次，集合里的元素没有顺序。 我们不会这样讲：我想要集合中的第三个元素，因为集合是没有顺序的。

事实上，这样的集合并不直接存在于编程语言中。然而，实际编程语言中的很多数据结构，就是在集合的基础上添加了一些规则形成的。

3.2.6、列表

列表（又称线性列表）的定义为：是一种数据项构成的有限序列，即按照一定的线性顺序，排列而成的数据项的集合。

列表的概念是在集合的特征上形成的，它具有顺序，且长度是可变的。你可以把它看作一张购物清单：

在这张清单中：

• 购物清单中的条目代表的类型可能不同，但是按照一定顺序进行了排列；
• 购物清单的长度是可变的，你可以向购物清单中增加、删除条目。

在编程语言中，列表最常见的表现形式有数组和链表，而我们熟悉的栈和队列则是两种特殊类型的列表。除此之外，向列表中添加、删除元素的具体实现方式会根据编程语言的不同而有所区分。

3.2.7、数组

数组是列表的实现方式之一，也是面试中经常涉及到的数据结构。

正如前面提到的，数组是列表的实现方式，它具有列表的特征，同时也具有自己的一些特征。然而，在具体的编程语言中，数组这个数据结构的实现方式具有一定差别。比如 C++ 和 Java 中，数组中的元素类型必须保持一致，而 Python 中则可以不同。Python 中的数组叫做 list，具有更多的高级功能。

那么如何从宏观上区分列表和数组呢？这里有一个重要的概念：索引。

首先，数组会用一些名为 索引 的数字来标识每项数据在数组中的位置，且在大多数编程语言中，索引是从 0 算起的。我们可以根据数组中的索引，快速访问数组中的元素

而列表中没有索引，这是数组与列表最大的不同点。

其次，数组中的元素在内存中是连续存储的，且每个元素占用相同大小的内存。要理解这一点，我们需要了解数组在内存中的存储方式。

相反，列表中的元素在内存中可能彼此相邻，也可能不相邻。比如列表的另一种实现方式——链表，它的元素在内存中则不一定是连续的。

3.3、数组的四种操作

3.3.1、读取元素

读取数组中的元素，是通过访问索引的方式来读取的，索引一般从 0 开始。

在计算机中，内存可以看成一些已经排列好的格子，每个格子对应一个内存地址。一般情况下，数据会分散地存储在不同的格子中。

而对于数组，计算机会在内存中为其申请一段 连续 的空间，并且会记下索引为 0 处的内存地址。以数组 ["C", "O", "D", "E", "R"] 为例，它的各元素对应的索引及内存地址如下图所示

假如我们想要访问索引为 2 处的元素 "D" 时，计算机会进行以下计算：

找到该数组的索引 0 的内存地址： 2008；
将内存地址加上索引值，作为目标元素的地址，即 2008 + 2 = 2010，对应的元素为 "D"，这时便找到了目标元素。
我们知道，计算内存地址这个过程是很快的，而我们一旦知道了内存地址就可以立即访问到该元素，因此它的时间复杂度是常数级别，为 O(1)。

3.3.2、查找元素

假如我们对数组中包含哪些元素并不了解，只是想知道其中是否含有元素 "E"，数组会如何查找元素 "E" 呢？

与读取元素类似，由于我们只保存了索引为 0 处的内存地址，因此在查找元素时，只需从数组开头逐步向后查找就可以了。如果数组中的某个元素为目标元素，则停止查找；否则继续搜索直到到达数组的末尾。

我们发现，最坏情况下，搜索的元素为 "R"，或者数组中不包含目标元素时，我们需要查找 n 次，n 为数组的长度，因此查找元素的时间复杂度为 O(N)，N。

3.3.3、插入元素

假如我们想在原有的数组中再插入一个元素 "S" 呢？

如果要将该元素插入到数组的末尾，只需要一步。即计算机通过数组的长度和位置计算出即将插入元素的内存地址，然后将该元素插入到指定位置即可。

然而，如果要将该元素插入到数组中的其他位置，则会有所区别，这时我们首先需要为该元素所要插入的位置 腾出 空间，然后进行插入操作。比如，我们想要在索引 2 处插入 "S"。

我们发现，如果需要频繁地对数组元素进行插入操作，会造成时间的浪费。事实上，另一种数据结构，即链表可以有效解决这个问题。

3.3.4、删除元素

删除元素与插入元素的操作类似，当我们删除掉数组中的某个元素后，数组中会留下 空缺 的位置，而数组中的元素在内存中是连续的，这就使得后面的元素需对该位置进行 填补 操作。

以删除索引 1 中的元素 "O" 为例，具体过程如图所示

当数组的长度为 n 时，最坏情况下，我们删除第一个元素，共需要的步骤数为 1 + (n - 1) = n 步，其中，1 为删除操作，n - 1 为移动其余元素的步骤数。删除操作具有线性时间复杂度，即时间复杂度为 O(N)O(N)O(N)，NNN 为数组的长度。

3.3.5、数组的力扣练习题——寻找数组的中心索引

寻找数组的中心索引
给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1

示例 1：

输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

思路分析：

• 先求得数组中所有元素之和sum；
• 遍历数组，取当前下标左边的元素之和leftSum，同时sum减去已遍历元素，比较二者是否相等，相等则返回当前下标；
• 遍历结束，代表没有中心索引，返回-1；

代码实现

/**
 * description
 * 寻找数组的中心索引
 * 思路分析：
 * 1、先求出数组的总和sum
 * 2、遍历数组，取出下标左边的元素之和leftSum，同时sum减去已遍历元素，并比较二者是否相等，相等则返回当前下标
 * 3、遍历结束，代表没有中心索引，返回-1
 *
 * @author
 * @since 2022/11/26 9:36
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr = {1, 7, 3, 6, 5, 6};
        int i = pivotIndex(arr);
        System.out.println(i);
    }

    /**
     * 寻找数组中心索引的方法
     *
     * @param nums 需要寻找中心索引的数组
     * @return
     */
    public static int pivotIndex(int[] nums) {
        int sum = 0;  //临时变量，用于记录数组中所有的总和
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];  //在遍历此数组中使用变量接收总和
        }
        int leftSum = 0;  //用于记录下标左边的元素之和
        for (int i = 0; i < nums.length; i++) {
            sum -= nums[i]; //总和减去已遍历元素
            if (leftSum == sum) {
                //比较二者是否相等，相等则返回当前下标
                return i;
            }
            leftSum += nums[i];
        }
        return -1;   //遍历结束，代表中心没有索引，返回-1
    }
}