使用指向数组的指针的无限大小堆栈实现

Question

我一直在尝试使用指向任意int的指针来创建一个无限大的堆栈：

//in class:
int* stack;

//In constructor:
stack = new int();

//In deconstructor:
delete stack;

//In Push:
stack(++top) = element;

这个声明正确吗？我能用它来做一个无限大小的堆栈吗？当我尝试使用这样的指针声明将元素放入堆栈时，我遇到了错误。

Answer 1

看起来你是在用C++写代码？如果没有，请忽略我的帖子(掌心)。

首先，可以分配给程序的内存是有限的，即没有无限大小的堆栈。在C++中，有BSS、堆栈和堆内存。在您的示例中，您使用了new操作符来分配内存。实际上，这实际上意味着您希望在堆中获得一块内存来存储您的值。虽然堆的大小可以动态扩展，但它的内存大小仍然不是无限的。

此外，似乎你想在构造函数中做的是构建一个大小不受限制的整型数组。实际上，要声明一个数组，可以编写new int[arraySize]在堆中声明一个大小为arraySize的整数数组。然而，您在这里编写的是在堆中分配一个int，因为您使用的括号不是方形的，而是圆形的。不幸的是，要创建数组，您需要首先声明它的大小(有关更多详细信息，您可以搜索堆栈数组和动态数组)。为了摆脱大小问题，您可以使用其他数据结构，如std::vector等，以便更简单。

int* stack;
stack = new int();

这两条语句将有一个指针指向堆内存中存储的单个int。因此，目前您创建的堆栈似乎只能存储int。

至于push函数，top是栈中top int的索引吗？

还有一件事，你想做的是创建一个指针来指向一个整型数组，并将该数组用作堆栈。然后，您可以考虑添加内存的方法，并将解构函数修改为如下所示：

delete[] stack;

如果你发现我上面的段落很难理解，并且有兴趣学习更多，也许你可以先学习栈和堆，然后是数组声明以及它与内存分配的关系，然后是关于指针的知识。

我是个新手。希望我的答案中没有任何错误。

Answer 2

首先，new int ()只创建一个int，而不是一个整数数组，因此您不能做像stack(++top) = element;这样的事情。

如果你想创建一个动态数组，你应该使用int* stack = new int[size]并用delete [] stack删除它。正如您所看到的，数组的size大小是有限的，但是您可以在数组变满时调整它的大小。没有内置的方法来调整数组的大小，但您可以创建一个更大的新动态数组，然后将旧的数组复制到其中，然后删除旧的数组。但是，由于内存有限，堆栈不会有无限的大小。如果分配失败，将抛出异常。

下面是一个基于动态数组的堆栈的简单实现。

#include <stdexcept>
using namespace std;

class Stack{

public:
    Stack (int _size = 20){
        size = _size;
        topIndex = 0;
        stack = new int [size];
    }

    ~Stack (){
        delete [] stack;
    }


    void resize(){
        int new_size = size*2;
        int * new_stack;
//        try{
        new_stack = new int[new_size];
//        } catch (std::bad_alloc&) {
            // unsuccessful allocation
//        }
        for ( int i=0; i<size; ++i ){
            new_stack[i] = stack[i];
        }
        delete [] stack;
        stack = new_stack;
        size = new_size;
    }


    void push(int element){
        if (topIndex + 1 == size){            
            resize();
        }
        stack[topIndex++] = element;
    }

    int top(){
        if ( topIndex <= 0 ){
            throw std::out_of_range("stack is empty");
        } else {
            return stack[topIndex-1];
        }
    }

    void pop(){
        if ( topIndex <= 0 ){
            throw std::out_of_range("stack is empty");
        } else {
            --topIndex;
        }
    }

private:    
    int * stack;
    int size;
    int topIndex;
};

int main(){
    Stack stk;
    for ( int i=0;i<50;++i ){
        stk.push(i);
        cout << stk.top() << endl;
    }
    for ( int i=0;i<50;++i ){
        stk.pop();
        cout << stk.top() << endl;
    }
}

请注意，这一切都只是为了练习，上面的实现很容易出错。在实际情况中，您几乎总是应该使用内置数据结构。