数据结构与算法---动态数组（3）顺序队列ArrayQueue、循环队列ArrayQueueLoop

1. 队列的顺序存储结构
   队列的定义：队列是只允许在一端经行插入操作，而在另一端进行删除操作的线性表
   队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队头
   

2. 队列的接口定义
   

3. 接口的实现 –基于ArrayList实现但是顺序队列存在一个问题，元素进队时时间复杂度为0(1),元素出队时时间复杂度为0(n)

4. 循环队列的顺序存储结构
   优化第一步：让队头指针与队尾指针一样随着元素的移动而移动
   这样子入队和出队的时间复杂度都为0(1)
   优化第二步：当队尾或队头指针到达尾部时，如需后移可重新指向表头
   
   
   这样如何判断队列已满，如何为空？
   队列满的条件（Rear+1)%n==Front; n为数组的长度
   优化第三步：将一个空间预留出来不放任何元素，尾指针始终指向这个null空间
   此时这样就表示队列已满
   队列为空的条件Rear==Front;

5. 循环队列的实现
   此时就不能在依赖于ArrayList应为他没有front和rear
   我们需要重写他的底层实现
   成员变量
   成员函数
   元素e入队
   1.先看队列是否满了((rear+1)%data.length= =front),则需要扩容
   2.若没满则元素往当前队尾的位置走，然后队尾对数组长度取余再加一
   3.然后size++
   
   元素出队
   1.先判断队列是否为空，若为空则提示队列为空
   2.若不为空，则返回front位置处的元素，此时队头的位置位队头加一在对数组长度取余，size–
   3.若有效元素个数小于等于（数组长度-1）的四分之一，并且（数组长度减一）除二要大于等于10时，则需要缩容
   扩容、缩容
   我们将新建的数组从位置零开始开始放元素，放size个
   原来的数组我们可以定义一个P从front开始,一直走到rear结束，但是P此时还需要对数组长度取余
   如果P==rear,则退出；此时rear就等于size。
   得到队头和队尾元素
   清空队列
   重写
   迭代器
   

最后

以上就是干净紫菜为你收集整理的数据结构与算法---动态数组（3）顺序队列ArrayQueue、循环队列ArrayQueueLoop的全部内容，希望文章能够帮你解决数据结构与算法---动态数组（3）顺序队列ArrayQueue、循环队列ArrayQueueLoop所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。