如何使我的堆栈类动态

Question

我在C++中编写了一个堆栈类（如下所示），但它是静态的，并且确定它使用大量内存。我怎么能使它动态，所以当它需要它添加一些内存的对象，当我弹出一些内存自动删除？

template <class T> 
class stack 
{ 
private: 
    T value[512]; 
    uint16_t length; 
public: 
    stack() 
    { 
     length=0; 
    } 

    stack(T _input) 
    { 
     value[0]=_input; 
     length=1; 
    } 

    bool push(T _input) 
    { 
     if(length+1<512) 
     { 
      value[++length]=_input; 
      return true;  
     } 
     else 
      return false; 
    } 

    T pop() 
    { 
     return value[length--];  
    } 

    T peak() 
    { 
     return value[length]; 
    } 

    bool has_data() 
    { 
     return (length>0?true:false); 
    } 

}; 

Answer 1

当需要出现时，您必须动态分配它。事情是这样的，也许：

#define STACK_INITIAL_ALLOC 32 
#define STACK_CHUNK_ALLOC 32 

template<typename T> 
class Stack 
{ 
public: 
    Stack() 
     : data(0), entries(0), allocated(0) 
     { } 

    Stack(const T &value) 
     : data(0), entries(0), allocated(0) 
     { 
      push(input); 
     } 

    ~Stack() 
     { 
      if (data) 
       delete [] data; 
     } 

    void push(const T &value) 
     { 
      if (entries == allocated) 
       allocate(); // Allocate more memory 

      data[entries++] = value; 
     } 

    T pop() 
     { 
      if (entries > 0) 
      { 
       shrink(); 
       return data[--entries]; 
      } 
      else 
       throw runtime_error("stack empty"); 
     } 

    T &top() 
     { 
      if (entries > 0) 
       return data[entries - 1]; 
      else 
       throw runtime_error("stack empty"); 
     } 

    // Return the number of entries in the stack 
    size_t count() const 
     { 
      return entries; 
     } 

private: 
    T  *data;  // The actual stack 
    size_t entries; // Number of entries in stack 
    size_t allocated; // Allocated entries in stack 

    void copy(T *from, T *to) 
     { 
      for (size_t i = 0; i < entries; i++) 
       *to++ = *from++ 
     } 

    void allocate() 
     { 
      if (data == 0) 
      { 
       allocated = STACK_INITIAL_ALLOC; 
       data = new T[allocated]; 
      } 
      else 
      { 
       // We need to allocate more memory 

       size_t new_allocated = allocated + STACK_CHUNK_ALLOC; 
       T *new_data = new T[new_allocated]; 

       // Copy from old stack to new stack 
       copy(data, new_data); 

       // Delete the old data 
       delete [] data; 

       allocated = new_allocated; 
       data = new_data; 
      } 
     } 

    // Shrink the stack, if lots of it is unused 
    void shrink() 
     { 
      // The limit which the number of entries must be lower than 
      size_t shrink_limit = allocated - STACK_CHUNK_ALLOC * 2; 

      // Do not shrink if we will get lower than the initial allocation (shrink_limit > STACK_INITIAL_ALLOC) 
      if (shrink_limit > STACK_INITIAL_ALLOC && entries < shrink_limit) 
      { 
       // We can shrink the allocated memory a little 
       size_t new_allocated = allocated - STACK_CHUNK_ALLOC; 

       T *new_data = new T[new_size]; 

       copy(data, new_data); 

       delete [] data; 

       data = new_data; 
       allocated = new_allocated; 
      } 
     } 
}; 

也是一个小声明，该代码被写入直接在浏览器中。它没有经过测试，但应该原则上...... :)

Answer 2

您也可以使用std ::向量：

template <class T> 
class stack{ 
private: 
std::vector<T> vec; 
public: 
inline void push(T arg){vec.push_back(arg);}; 
inline T pop(){return vec.pop_back();}; 
}; 

Answer 3

状结构的任何数组将是昂贵的增长和收缩（T必须是拷贝构造）和所有现有T■找到被移动。如果您发现您正在进行大量推送/弹出操作，并且需要保持内存使用率较低，请尝试在内部使用链接列表。它只需要单独连接。

这里是一个草图：

template <class T> 
class stack 
{ 
    struct Node 
    { 
    T data; 
    Node* next; 
    }; 
public: 

    // methods 

private: 
    Node *head; 
}; 

现在，推栈上的东西，构造一个Node与T，设置它的下一个指针当前head和head到Node指针。 Popping包括从head中取出next并将其设置为head。

当然，你需要正确地管理毁灭等内存

编辑：啊看来我的假设，你可能知道C的基础++是不正确的，我以为你做了，你正在使用的模板。在这种情况下 - 忽略这个答案，直到你学会了基础知识！