调整循环队列的大小?

问题描述 投票:0回答:1

我目前正在致力于实现循环队列,在调整队列大小时遇到了问题。我已经成功实现了

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++ data-structures
1个回答
0
投票

正如评论已经指出的那样,在 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
。同样,这取决于您如何维护循环队列的前/后状态。

© www.soinside.com 2019 - 2024. All rights reserved.