文章目录

• • • 1、队列介绍
    • 2、数组模拟队列思路
    • 3、数组模拟环形队列思路

1、队列介绍

• 队列是一个有序列表，可以用数组或是链表来实现
• 遵循先入先出的原则 （first in first out，简称“FIFO”）。即：先存入队列的数据，要先取出。后存入的要后取出
• 示意图：（使用数组模拟队列示意图）
  

队列的实现同样有两种方式：顺序存储(数组)和链式存储(链表)。本文使用数组实现队列

2、数组模拟队列思路

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

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

  1. 将为指针后移： rear + 1
  2. 若尾指针 rear 小于队列的最大下标 maxSize - 1 ，则将数据存入 rear 所指的数组元素中，否则无法存入数据。

  队列满 rear == maxSize - 1