模板類 Stack C++ 實現（線性存儲版）

今天自己寫了一個 C++ 中的棧（stack）實現，在實現的時候主要問題如下。

在 C++ 中，容器類是沒辦法實現「只存儲引用」這個目標的。假如我想實現一個只存儲引用（也就是存儲指針）的容器，那意味著我必須保證引用不懸空（不產生懸空指針）。然而，用戶push到棧中的元素可能是局部變量，那麼萬一用戶將我的stack傳遞到函數體外，就無法保證這一點了。所以，任何容器類必須面臨「複製構造函數」的時耗。

使用數組 T* arr = new T[count]; 的時候，每一個arr的成員都將被自動地初始化。由於分配空間是比較耗時的，我們一般會以翻倍的長度提前分配內存空間。然而，我們的內存空間是用來存儲push的成員的，不需要初始化新成員。方法就是改變T為T的指針類型。

/*
 * A Stack Implement
 * With Resizing Array
 *
 * Copyright(C) Ceeji
 */
 
#ifndef _STACK_H_
#define _STACK_H_
 
/*
 * stack : a stack implement template class
 */
template <typename T>
class stack {
public:
    stack();
    void push(const T& element); // push an element to this stack
    T pop(); // pop an element from this stack
    int size(); // get the size of this stack
    bool isEmpty(); // is the stack empty
 
private:
    void resizeCapacity(); // resize the capacity of stack
    const T** arr;
    int n; // count
    int capacity; 
};
 
template <typename T>
stack<T>::stack() {
    // init the variable
    this->n = 0;
    this->capacity = 1; // default capacity is 1
 
    // alloc memory for stack
    arr = new const T*[this->capacity];
}
 
template <typename T>
void stack<T>::push(const T& element) {
    // check memory size
    if (this->size() == this->capacity) {
        this->capacity = this->capacity << 1; // capacity *= 2
        resizeCapacity();
    }
 
    //push element
    arr[n++] = new T(element); // add the reference
}
 
template <typename T>
T stack<T>::pop() {
    // get the element
    T tmp(*arr[--n]);
    // release memory
    delete arr[n];
    // resize the capacity
    if (this->capacity / this->size() >= 3) {
        this->capacity = this->size();
        this->resizeCapacity();
    }
 
    return tmp;
}
 
template <typename T>
inline bool stack<T>::isEmpty() {
    return n == 0;
}
 
template <typename T>
inline int stack<T>::size() {
    return n;
}
 
/*
 * resize the capacity of this stack
 */
template <typename T>
void stack<T>::resizeCapacity() {
    const T** tmp = new const T*[this->capacity];
 
    for (int i = 0; i < n; ++i) {
        tmp[i] = this->arr[i];
    }
 
    delete[] this->arr;
 
    this->arr = tmp;
}
#endif

猜你喜歡