我目前正在致力于实现循环队列,在调整队列大小时遇到了问题。我已经成功实现了
linear (array) based queues
的调整大小功能。
这是我当前用于调整线性队列大小的函数:
template <typename T>
void Queue<T>::Grow() {
const uint32_t newSize = m_size + 1;
T* newArray = new T[newSize];
for (int i = 0; i < static_cast<int>(m_size); i++)
newArray[i] = array[i];
delete[] array;
m_size = newSize;
array = newArray;
}
但是,将相同的原理应用于循环队列似乎违背了使用循环结构的目的。
有人可以提供有关如何调整循环队列大小的见解或实现示例吗?
提前感谢您的帮助!
正如评论已经指出的那样,在 C++ 中,您最好远离 C 样式数组并使用
std::vector
,但要回答您的问题:要为 circular 队列实现此功能,您可以复制 的 used 部分数组到新数组的 start ,应用与循环队列的前/后位置相对应的移位。然后将前/后场设置为移位后的结果。根据您所说的前部或后部,在新设置中前部将获得 0 作为索引,而后部将由队列的使用大小确定。
类似这样的东西(但这取决于您在实现中如何定义和使用前/后概念):
template <typename T>
void Queue<T>::Grow() {
const uint32_t newSize = m_size + 1;
T* newArray = new T[newSize];
for (int i = 0; i < m_size; i++)
newArray[i] = array[(m_front + i) % m_size];
delete[] array;
m_size = newSize;
m_front = 0;
m_rear = (m_rear + m_size - m_front) % m_size;
array = newArray;
}
您需要对此进行调整以适应您的班级和前/后概念。此外,您可能需要在最后一个表达式中使用
newSize
而不是 m_size
。同样,这取决于您如何维护循环队列的前/后状态。