type
status
date
slug
summary
tags
category
icon
password
AI summary

数组实现环形队列 详细讲解

数组模拟环形队列

对前面的数组模拟队列的优化,将数组看做是一个环形的。(通过取模的方式来实现即可)

解题思路

1、既然是环形队列,那就一定有头有尾,有容量
2、既然是数组实现,那一定有个算法保证可以让数组循环起来
notion image
如图所示: rear为7 ,front为0,实际的数据为7,是因为rear定义指向了最后一个元素的后一个位置,所以满数组的size变成了size-1,空出的位置来保证循环
notion image
  1. front 变量的含义做一个调整: front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 front 的初始值 = 0
  1. rear 变量的含义做一个调整:rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.rear 的初始值 = 0
  1. 当队列满时,条件是 (rear + 1) % maxSize == front 【满】
  1. 对队列为空的条件, rear == front 空
  1. 当我们这样分析, 队列中有效的数据的个数 (rear + maxSize - front) % maxSize // rear = 1 front = 0
  1. 我们就可以在原来的队列上修改得到,一个环形队列

代码实现

 
数组实现栈 详细讲解数组实现队列 详细讲解