队列的应用场景和介绍
队列的应用场景和介绍
-
特点：先进先出 英文：Queue 应用场景举例 银行排队：四个业务员，为排队的人的服务，每有一个业务员服务完成后，这时下一位被服务者从下面的队列中产生。 队列介绍 队列是一个有序列表，可以用数组和链表实现。数组顺序存储，链表链式存储。 遵循先入先出的原则，即先存入队列的数据，要先取出，后存入的要后取出。 用数组模拟示意图：rear代表尾部，front代表队首，MaxSize代表数组的最大容量，当数据加入的时候，队首不变，队尾增加，数据出去的时候，队首指针增加。 因为队列的输出、输入分别从前后端来处理，因此需要两个变量front和rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear会随着数据的输入而改变。 数据存入队列步骤分析 将尾指针往后移rear+1，当front==rear的时候，队列为空。 若为指针rear小于队列的最大下标maxSize-1,则将数据存入rear所指数组元素中，否则无法存入数据。当rear==maxSize-1，队列满。 front在队首前一个位置，rear除非队为空，正常队列（循环情况暂时不考虑），rear总是在队的最后一个元素。 实现代码 上述代码有缺陷，就是当队列不断出栈为空时，那么再往里面添加元素，不能再添加，因为front和rear都已经是数组最大位置。数组只能用一次，原因是数组没有取模，做成环形队列。
下一篇：
算法修炼10、矩形覆盖