编程日志4.23

栈的C++顺序表实现

#include<iostream>
#include<stdexcept>

using namespace std;
//模板声明，表明Stack类是一个通用的模板，可以用于存储任何类型的元素T
template<typename T>

//栈的声明
//Stack类的声明，表示一个栈的数据结构
class Stack {
private://定义私有（成员变量）
    T* data;//用于存储栈中的元素，它是一个指向类型为T的指针
    int size;//用于记录栈中元素的数量
    int capacity;//用于记录栈的容量
    void resize();//用于在栈容量不足时进行扩容
public://定义公共
    //Stack（）是构造函数，用于初始化栈的成员变量。它创建一个新的栈，并分配一个容量为10的数组来存储元素
    Stack():data(new T[10]),size(0),capacity(10){}
    ~Stack();//析构函数，用于释放栈所用的内存
    void push(T element);//公共函数，用于将一个新元素压入栈顶
    T pop();//用于从栈顶弹出一个元素
    T top() const;//用于获取栈顶的元素，但不弹出它
    int getSize() const;//用于获取栈中元素数量
};
//模板声明，表明resize函数是一个通用的模板，可以用于处理任何类型的元素T
template<typename T>
//栈的扩容
void Stack<T>::resize() {
    int newCapacity = capacity * 2;//计算新的容量，并将其赋值给newCapacity变量，新的容量是当前容量的两倍
    T* newData = new T[newCapacity];//创建新数组newData,用于存储新扩容后的元素，新数组的大小为新的容量
    for (int i = 0; i < size; ++i) {
        newData[i] = data[i];//复制栈中元素到新数组
    }
    delete[] data;//释放旧数组data所占用的内存空间
    data = newData;//newData赋值给data，使其成为栈的新存储数组
    capacity = newCapacity;//更新了栈的容量为新的容量
}
//栈的销毁
template<typename T>
Stack<T>::~Stack() {//析构函数的声明，用于在对象销毁时执行清理操作
    delete[] data;//释放了动态分配的数组的data所占用的内存空间。
}

//入栈
template<typename T>
void Stack<T>::push(T element) {
    if (size == capacity) {//栈满，调用resize函数进行扩容
        resize();
    }
    data[size++] = element;//element赋值给data的size位置，并将size的值+1，以表示栈中元素数量增加
}

//出栈
template<typename T>
T Stack<T>::pop() {
    if (size == 0) {
        throw std::underflow_error("Stack is empty");//如果栈空，抛出异常
    }
    return data[--size];//不空，栈大小-1，并返回data数组中栈顶元素的值
}

//获取栈顶元素
template<typename T>
T Stack<T>::top() const{
    if (size == 0) {
        throw std::underflow_error("Stack is empty");//如果栈空，抛出异常
    }
    return data[size-1];//不空，返回data数组中的最后一个元素的值，即栈顶元素。
}

template<typename T>
int Stack<T>::getSize() const {
    return size;
}

int main() {
    Stack<int> st;
    st.push(4);
    st.push(7);
    st.push(13);
    cout << st.top() << endl;
    st.push(17);
    cout << st.top() << endl;
    st.pop();
    st.pop();
    cout << st.top() << endl;
    cout << st.getSize() << endl;

    return 0;
}