Получение противоречивого нарушения прав доступа при работе с очередями - PullRequest
Новая
       17

Получение противоречивого нарушения прав доступа при работе с очередями

0 голосов
/ 22 марта 2019

Я пишу простую программу очереди, которая запускается для циклов и добавляет в очередь увеличивающиеся значения. После того, как он достигнет емкости очереди, он создает временную очередь, которая равна новой динамически присваиваемой очереди и удваивает емкость новой очереди. Он начинается с размера 8, но становится нарушением прав доступа при попытке массива 124. 

#include <iostream>
using namespace std;

class queue {
public:
    queue();
    void enqueue(int item);
    void dequeue();
    int front();
    bool empty();
private:
    int * data;
    int myFront;
    int myBack;
    int size;
    int capacity;
};

queue::queue() {
    myFront = 0;
    myBack = 0;
    size = 0;
    capacity = 8;
    data = new int[capacity];
}

bool queue::empty() {
    return (size == 0);
}

void queue::enqueue(int item) {
    if (size == capacity - 1) {
        int * temp = new int[capacity * 2];
        for (int i = 0; i < size; i++) {
            temp[i] = data[i];
        }
        delete[] data;
        data = temp;
        capacity = capacity * 2;
        myFront = data[0];
        //myBack = temp[capacity/2];
    }
    data[myBack] = item;
    myBack++;
    size++;
}

int queue::front() {
    return data[myFront];
}

void queue::dequeue() {
    myFront = (myFront + 1) % capacity;
    size = size - 1;
}

int main() {
    queue nq;
    // enqueue numbers 0-49
    for (int i = 0; i < 50; i++) {
        nq.enqueue(i);
    }
    // dequeue 25 times. Show prints 0 1 2 ... 24
    for (int i = 0; i < 25; i++) {
        cout << nq.front() << " ";
        nq.dequeue();
    }
    cout << endl;
    cout << "Check point 1" << endl;
    // enqueue numbers 50-124. Now the queue should be 
    // 25 26 ... 124 from front to end
    for (int i = 50; i < 125; i++) {
        nq.enqueue(i);
    }
    // dequeue 100 times. should show 25 26 ... 124
    for (int i = 0; i < 100; i++) {
        cout << nq.front() << " ";
        nq.dequeue();
    }
    cout << endl;
    int temp1;
    cin >> temp1;
}

Какая часть кода создает эту ошибку доступа и что мне делать, чтобы ее исправить? Кажется, он работает нормально для первых двух итераций, но затем перестает правильно обращаться к концу.

1 Ответ

0 голосов
/ 22 марта 2019

enqueue не обрабатывает перенос очереди, а также расширение не обрабатывает должным образом обработанную очередь (где есть данные в конце и начале массива с неиспользуемыми элементами в середине).

После того, как вы удалили первые 25 элементов, емкость равна 64, элементы [25..49] заняты в массиве data.Когда вы добавляете 15-й новый элемент (65), размер составляет только 39, поэтому хранилище очереди не расширяется, и вы пишете после конца выделенного пространства.

enqueue необходимо выполнить перенос сmyBack, что dequeue делает с myFront, и код расширения необходимо изменить для обработки завернутой очереди.

...