模板类 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

本文版权遵循 CC BY-NC-SA 4.0发布，转载需附带本文链接。

猜你喜欢