C++ 手动实现栈(stack) （课后作业版）

栈，一种遵循先进先出原则的数据结构，可以用顺序表实现，也可以用链表进行实现。

这里我使用数组实现方法，包含了进栈，出栈，访问栈顶等功能，以及一些辅助功能。

栈Stack类定义如下：

template <typename T>
class Stack {
public:
    Stack();
    Stack(int n);
    Stack(Stack& stack);
    ~Stack();
    T& top();
    Stack& push(const T& elem);
    Stack& pop();
    void reserve(int num);
    int size() {return current+1; }
    int capciaty() {return cap; }
    int is_empty() {return current == -1; }
    bool is_full() {return current == (cap-1); }
    void clear() {this->~Stack();}
private:
    T* arr;
    int current;
    int cap;
};

其中，成员变量的解释：

arr ：数组指针，指向栈底

current ： 当前栈顶的索引，没有元素的时候为-1, 有一个元素的时候为0, 以此类推

cap ：数组容量，注意容量和元素个数是不同的概念

然后，是成员函数的解释：

Stack();    默认构造函数
Stack(int n);    一般构造函数，容量为n
Stack(Stack& stack);    拷贝构造函数，浅拷贝
~Stack();       析构函数
T& top();      访问栈顶
Stack& push(const T& elem);    进栈
Stack& pop();    出栈
void reserve(int num);    增加容量
int size() {return current+1; }    获取当前元素个数
int capciaty() {return cap; }     获取容量
int is_empty() {return current == -1; }   是否为空栈
bool is_full() {return current == (cap-1); }    是否满栈
void clear() {this->~Stack();}    清除，调用析构函数

完成实现代码：

#include 
 
using namespace std;
 
template <typename T>
class Stack {
public:
    Stack();
    Stack(int n);
    Stack(Stack& stack);
    ~Stack();
    T& top();
    Stack& push(const T& elem);
    Stack& pop();
    void reserve(int num);
    int size() {return current+1; }
    int capciaty() {return cap; }
    int is_empty() {return current == -1; }
    bool is_full() {return current == (cap-1); }
    void clear() {this->~Stack();}
private:
    T* arr;
    int current;
    int cap;
};
 
//默认构造函数
template <typename T>
Stack::Stack() {
    cap = 0;
    current = -1;
    arr = nullptr;
}
 
//一般构造函数
template <typename T>
Stack::Stack(int n) {
    cap = n;
    current = -1;
    arr = new T[n]{};
}
 
//拷贝构造函数(前浅贝)
template <typename T>
Stack::Stack(Stack& stack) {
    cap = stack.capciaty();
    current = stack.size();
    this->arr = stack.arr;
}
 
//析构函数
template <typename T>
Stack::~Stack() {
    if ( cap == 0 ) {
        return;
    }
    cap = 0;
    current = -1;
    delete [] arr;
    arr = nullptr;
}
 
//访问栈顶
template <typename T>
T& Stack::top() {
    if ( is_empty() ) {
        cout << "[error]: stack has no element" << endl;
    }
    return *(arr+current);
}
 
//在栈顶添加一个元素
template <typename T>
Stack& Stack::push(const T& elem) {
    if ( is_full() ) {
        reserve(2*cap);
    }
    current++;
    arr[current] = elem;
    return *this;
}
 
//栈顶弹出
template <typename T>
Stack& Stack::pop() {
    if ( is_empty() ) {
        cout << "[error]: don't try to pop a empty stack" << endl;
        return *this;
    }
    current--;
    return *this;
}
 
//增加容量
template <typename T>
void Stack::reserve(int num) {
    if ( num < cap ) {
        cout << "[warning]: input of reserve() function shuold lager than capciaty" << endl;
        return;
    }
    T *arr_ = new T[num]{};
    for ( int i = 0; i <= current; i++ )
        arr_[i] = arr[i];
    delete [] arr;
    arr = arr_;
    arr_ = nullptr;
    cap = num;
}
 
int main() {
    Stack<int> stack(3);
//    cout << "top=" << stack.top() << ", 容量=" << stack.capciaty() << ", 元素个数=" << stack.size() << endl;
    stack.push(3);
    cout << "top=" << stack.top() << ", 容量=" << stack.capciaty() << ", 元素个数=" << stack.size() << endl;
    stack.push(2);
    cout << "top=" << stack.top() << ", 容量=" << stack.capciaty() << ", 元素个数=" << stack.size() << endl;
    stack.push(5);
    cout << "top=" << stack.top() << ", 容量=" << stack.capciaty() << ", 元素个数=" << stack.size() << endl;
    stack.push(5);
    cout << "top=" << stack.top() << ", 容量=" << stack.capciaty() << ", 元素个数=" << stack.size() << endl;
    stack.pop();
    cout << "top=" << stack.top() << ", 容量=" << stack.capciaty() << ", 元素个数=" << stack.size() << endl;
    stack.clear();
    cout << "top=" << stack.top() << ", 容量=" << stack.capciaty() << ", 元素个数=" << stack.size() << endl;
}