C++ 堆栈数据结构。这段代码有什么问题?

标签 c++ data-structures stack

所以我目前正在尝试通过实现各种数据结构将我的 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;
}

最佳答案

对于初学者,您应该在数组上递增索引,因此更改:

elementsInArray++;
stackArray[elementsInArray] = aValue;

到:

stackArray[elementsInArray++] = aValue;

或:

stackArray[elementsInArray] = aValue;
elementsInArray++;

其次,当您创建新的临时数组时,您是在 if 语句中进行的...因此它是一个局部变量,并放置在系统堆栈中,并在您退出 if 语句后丢失。所以改变

int temporaryArray[allocatedArraySize*beta];

到:

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

第三,通过在复制 tempArray 的位置之前保存 stackArray 中的原始指针来添加您正在谈论的删除,然后在完成指针复制后执行删除。

最后,您必须对 pop 函数进行类似的更改...

关于C++ 堆栈数据结构。这段代码有什么问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7153655/

相关文章:

c++ - 计算 1 - 小参数 x (~10^-12) 的 sqrt(x) 类似于 expm1(在 C/C++ 中)

c++ - 指针和动态分配的数组

java - 如何设置 JVM 拥有更多 1GB 堆栈大小?

c - 在使用堆栈方面,为什么我们需要一个基指针和一个堆栈指针

c++ - 如何读取字符串中的最后一个字符

c++ - for 循环的问题(初学者)

c - 将数千个数据结构保存在一个文件中并进行特定查找是否实用?

algorithm - 求有多少玩家不能赢得比赛?

c - c中的pf apply是什么?

c - 使用堆栈实现根据最后更新日期跟踪所有文件