Структура данных стека C ++.Что не так с этим куском кода?

Question

, поэтому в настоящее время я пытаюсь перенести свой опыт работы с Java на C ++, внедряя различные структуры данных для реализации их хотя бы один раз.

Не могли бы вы дать мне несколько советов?Проблема, с которой я столкнулся, в основном сосредоточена вокруг указателей в push (int value) и особенно в pop ().Так как push работает правильно, я обнаружил, что изо всех сил пытаюсь вернуть правильное значение при всплывающих окнах.В чем дело?

PS: Я также думаю, что, поскольку я выделяю пространство массива вручную, мне нужно также удалить его.Как мне это сделать?

#ifndef STACK_H
#define STACK_H

class Stack
{
private:
    int *stackArray;
    int elementsInArray;
    int allocatedArraySize;
    int alpha;
    int beta;

public:
    Stack();
    void push(int aValue);
    int pop();
    bool isEmpty();
    int size() const;
};

#endif

и реализация:

#include <iostream>
#include "Stack.h"

Stack::Stack() 
{
    alpha = 4;
    beta = 2;
    elementsInArray = 0;
    allocatedArraySize = 1;
    stackArray = new int[1];
}

void Stack::push(int aValue)
{
    if (elementsInArray == allocatedArraySize) 
    {
        int temporaryArray[allocatedArraySize*beta];

        for (int i = 0; i < elementsInArray; i++)
            temporaryArray[i] = stackArray[i];

        stackArray = temporaryArray;
        allocatedArraySize *= beta;
    }

    elementsInArray++;
    stackArray[elementsInArray] = aValue;
}

int Stack::pop()
{
    int result = -INT_MAX;

    if (elementsInArray == 0)
        return result;

    if (elementsInArray > 0) 
    {
        result = stackArray[elementsInArray-1];
        elementsInArray--;

        if (elementsInArray <= allocatedArraySize/alpha) 
        {
            int temporaryArray[allocatedArraySize/alpha];

            for (int i = 0; i < elementsInArray; i++) 
                temporaryArray[i] = stackArray[i];

            stackArray = temporaryArray;
            allocatedArraySize /= beta;
        }
    }

    return result;
}

bool Stack::isEmpty()
{
    if (elementsInArray == 0) 
        return true;

    return false;
}

int Stack::size() const
{
    return allocatedArraySize;
}

Answer 1

Для начала, вы должны постинкрементно увеличивать индекс массива, поэтому измените:

elementsInArray++;
stackArray[elementsInArray] = aValue;

на:

stackArray[elementsInArray++] = aValue;

или:

stackArray[elementsInArray] = aValue;
elementsInArray++;

Во-вторых, когда вы создаете новый временный массив, вы делаете это внутри оператора if ... поэтому он является локальной переменной и помещается в системный стек и теряется после выхода из оператора if.Поэтому измените

int temporaryArray[allocatedArraySize*beta];

на:

int *temporaryArray = new int[allocatedArraySize*beta];

В-третьих, добавьте удаление, о котором вы говорили, сохранив исходный указатель из stackArray перед копированием расположения tempArray и затем выполните удалениепосле того, как вы сделали копию указателя.

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

Answer 2

Вы используете массив в стеке (не ваш стек - стек выполнения программы).Он называется временным массивом в вашей функции push.Адрес этого массива будет недействительным, когда вы вернетесь из этой функции (потому что другие функции будут использовать стек для хранения других данных).

что вы хотите сделать, это разместить этот массив в куче 1004 *.Это память, которая остается для вашей программы до тех пор, пока она вам нужна.Чтобы сделать это, вы должны выделить временный массив как

int * temporaryArray(new int[allocatedArraySize*beta]);

Затем, после копирования элементов из старого массива, удалите его с помощью:

delete [] stackArray;

Сделайте это перед назначениемstackArray с временным массивом.

Могут быть и другие проблемы с вашей структурой данных, но вы правильно выполняете базовое индексирование и соответствующим образом увеличиваете / уменьшаете текущий индекс (хотя я бы предпочел использовать преинкремент / декрементформируется, когда не используется временная как хорошая привычка - например. ++ elementsInArray / --elementsInArray).

Answer 3

хорошо, я уверен, что вы уже знаете, что у вас есть стек как универсальный (c ++ называет его шаблонами) в библиотеке STD.Предполагая, что вы делаете это как код ката, я бы начал писать его как шаблон, чтобы он не мог принимать типы объектов, отличные от целых.

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