如何使我的堆棧類動態

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的基礎++是不正確的，我以爲你做了，你正在使用的模板。在這種情況下 - 忽略這個答案，直到你學會了基礎知識！