C++数据结构：stack实现

栈的实现

• 前言
  栈是一种基础且高效的数据结构，遵循先进后出的原则。其核心操作在于压栈和弹栈，分别用于在栈顶添加元素和移除栈顶元素。栈在计算机科学中广泛应用，例如在函数调用栈，表达式求值，括号匹配等场景中均发挥关键作用。本实现将详细展示栈的基本操作及其内部逻辑，通过代码与理论结合的方式，帮助读者深入理解其工作机制。

以下代码是实现stack的类，包括size（目前长度），data（指针），total（总长度）
resize（扩容函数）等。

template<typenameT>classstack{private:intsize;T*data;inttotal;voidresize();public:stack():data(newT[10]),size(0),total(10){}~stack();voidpush(T value);Tpop();Ttop()const;intgetsize()const;};

• resize函数

对于扩容函数resize（），我们先把新的总长度变成原来的总长度的二倍。
然后申请新的空间，新的空间大小用newtotal。
然后把原来的数组的元素存到新的数组里面，然后删除原来的数组的内容，把新的newdata赋值给原来的data，这样data就指向了新的数组的首元素，此处是把指向新数组首地址的指针newdata赋值给了data，让data指向新数组的首地址。

template<typenameT>voidstack<T>::resize(){intnewTotal=total*2;T*newdata=newT[newTotal];for(inti=0;i<size;++i){newdata[i]=data[i];}delete[]data;data=newdata;total=newTotal;}

• 析构实现
  析构函数的写法没有多余的代码，就是删除掉就好了

template<typenameT>stack<T>::~stack(){delete[]data;}

• push函数实现
  在函数的开始先判断一下size（当前的数组的元素个数size和数组的总空间total是否相等），如果相等，那么就进入resize（）函数，进行扩容，扩容后，data[size] = value，此时size = 10，然后size++，变成11.

template<typenameT>voidstack<T>::push(T value){if(size==total){resize();}data[size++]=value;}

• pop函数实现
  进入函数先判断size（当前数组中的元素个数）是否为0，如果为0，则弹出异常提示stack是空的，否则返回size自减之后作为下标的data数据

template<typenameT>Tstack<T>::pop(){if(size==0){throwstd::underflow_error("stack is empty");}returndata[--size];}

• top函数实现
  对于top函数我们只需要返回栈顶元素就可以了，所以我们要加一个const来保护数据。
  进入函数判断size元素个数是否为0，如果为0，则弹出异常。
  否则返回数组的元素个数减一作为下标的data数据，因为数组下标从0开始，所以10个元素的最后一个元素的下标为10 - 1 = 9；

template<typenameT>Tstack<T>::top()const{if(size==0){throwunderflow_error("stack is empty");}returndata[size-1];}

• getsize函数实现
  对于这个函数没什么可说的，我们直接返回size，并且不要忘记加上const来保护数据。

template<typenameT>intstack<T>::getsize()const{returnsize;}

• 总结
  以上就是stack的实现，如果你还没有搞懂指针和数组的概念和联系，可以移步我的主页，找到《另一个角度看指针》，相信会对你来说会有帮助。