массивы — увеличение емкости кольцевой очереди в переполнении стека

Question

массивы — увеличение емкости кольцевой очереди в переполнении стека

Я изучаю очереди и пытаюсь написать метод для изменения максимальной емкости кольцевой очереди с использованием динамического массива. Вот как выглядит мой код прямо сейчас.

void ArrayQueue::setCapacity(unsigned newCapacity){
if(newCapacity == 0 || newCapacity < this->getSize()){
throw QueueException("setCapacity()", "invalid new capacity");
} else if(newCapacity != this->getSize()){
Item * tempArray = new Item[newCapacity];
for(unsigned i=0; i<newCapacity; i++){
tempArray[i] = myArray[i];
}
Item * oldArray = myArray;
myArray = tempArray;
delete [] oldArray;
}
this->myCapacity = newCapacity;
}

Однако, когда я уменьшаю емкость, мне не удается получить значения myFirst и myLast. Я понимаю, что мне нужно написать код для учета случая, когда записи обернулись, но я не совсем понимаю, как это сделать.

Тест, который я пытаюсь пройти, имеет следующий код:

    ArrayQueue q5(10);
for (int i = 0; i < 10; i++){
q5.append(i+1);
}
for (int i = 0; i < 7; i++){
q5.remove();
}
assert( q5.getCapacity() == 10 );
assert( q5.getSize() == 3 );
assert( !q5.isEmpty() );
assert( !q5.isFull() );
assert( q5.getFirst() == 8 );
assert( q5.getLast() == 10 );

//reduce the capacity
q5.setCapacity(5);
assert( q5.getCapacity() == 5 );
assert( q5.getSize() == 3 );
assert( !q5.isEmpty() );
assert( !q5.isFull() );
assert( q5.getFirst() == 8 );
assert( q5.getLast() == 10 );

Я передаю свой первый набор утверждений, но второе утверждение getFirst не выполняется.

Не могли бы вы дать мне указатель в правильном направлении? Благодарю.

0

arrays c++capacity dynamic queue

Решение

Другие решения

for(unsigned i=0; i<newCapacity; i++){
tempArray[i] = myArray[i];
}

Если ваша новая емкость больше, то вы получите доступ к myArray с недопустимыми индексами

0

Насколько я могу понять ваш вопрос, вы ссылаетесь на утверждения, выданные в другом месте, кроме фрагмента кода, который вы опубликовали. Поскольку вы не разместили код, который вы считаете проблематичным, вряд ли кто-нибудь даст вам ответ.

Тем не менее, я вижу вероятную ошибку во фрагменте кода, который вы разместили. Ваш код, который увеличивает размер массива:

Item * tempArray = new Item[newCapacity];
for(unsigned i=0; i<newCapacity; i++){
tempArray[i] = myArray[i];
}
Item * oldArray = myArray;
myArray = tempArray;
delete [] oldArray;

Скажем, например, старый размер myArray был 20, а вы увеличили его до 40.

Вы собираетесь выделить новый 40-элементный массив tempArray.

Затем перейдите к копированию первых 40 элементов из myArray в tempArray.

Неопределенное поведение.

0

Источник

Accepted Answer

Могу ли я предложить переписать это, используя следующее:

#include <algorithm>
//...
void ArrayQueue::setCapacity(unsigned newCapacity)
{
if(newCapacity == 0 || newCapacity < this->getSize()){
throw QueueException("setCapacity()", "invalid new capacity");
ArrayQueue tempQ(newCapacity);
for(unsigned i=0; i< capacity; i++)
tempQ.append(myArray[i]);
std::swap(myArray, tempQ.myArray);
std::swap(capacity, tempQ.capacity);
std::swap(size, tempQ.size);
}

Как это работает? Ну, мы создаем временный ArrayQueue с необходимой емкостью. Затем все, что мы делаем, это копируем данные во временный объект. После этого мы меняем временный объект this,

Готово.

Временный объект умирает со старыми данными, и this устанавливается с новыми данными. Это вариация copy/swap идиома. Это требует рабочего деструктора для ArrayQueue — если у вас есть это, то это становится куском пирога.

Обратите внимание, что если есть больше переменных-членов, их также необходимо поменять местами. Я просто поменял местами те, которые вы опубликовали. Я догадался, у вас есть size переменная-член, поэтому, если вы назвали ее по-другому, замените ее именем, которое вы использовали. Итог — поменяйте все с tempQи ты должен быть в порядке.

Если вы не знаете, что std::swap делает, он делает то, что говорит. Он просто меняет два элемента друг на друга — ничего особенного, просто удобно просто использовать функцию для этого.

1