上次用C语言四线堆栈，本次我们使用C++来实现堆栈，利用C++的模板机制，使堆栈可以存储任意的数据类型。同时，使用链表来模拟栈，使得栈的大小可以达到硬件所能支持的最大内存空间。好了，下面马上实现。
1。首先还是先定义栈中元素的数据类型：
- /*堆栈使用链式存储，定义堆栈的节点数据类型*/
- template <typename T>
- struct Node
- {
- T data; //节点中的元素
- Node* next;
- };
2.其次定义Stack类：
- /*堆栈的类定义*/
- template <typename T>
- class Stack
- {
- private:
- Node<T>* mHead; //头指针，用于管理链栈
- int mSize; //栈中元素的个数
- public:
- Stack();
- virtual ~Stack();
- void push(T e); //入栈操作
- void pop(T& e); //出栈操作
- bool isEmpty(); //判断栈空
- int getSize(); //返回栈中总元素
- void print(); //打印栈中的元素 但不出栈
- };
3.下面就是实现Stack的各个函数：
（1）构造函数：
//构造函数 创建头指针
template <typename T>
Stack<T>::Stack()
{
mHead = new Node<T>(); //创建头结点指针
mHead->next = nullptr;
mSize = 0; //初始时栈中元素个数为0
}
（2）析构函数
/*析构函数：释放栈所占的堆内存*/
template <typename T>
Stack<T>::~Stack()
{
Node<T>* p = mHead->next; //p指向栈顶元素
Node<T>* q = nullptr;
while (nullptr != p)
{
q = p;
p = p->next;
delete q; //逐一释放栈中元素
}
delete mHead; //最后释放头指针
}
（3）入栈操作
//入栈：采用头插法创建
template <typename T>
void Stack<T>::push(T e)
{
Node<T>* s = new Node<T>();
s->data = e;
s->next = mHead->next;
mHead->next = s;
++mSize;
}
（4）出栈操作
//出栈
template <typename T>
void Stack<T>::pop(T& e)
{
if(isEmpty())
{
printf("栈已空!!!\n");
return;
}
Node<T>* p = mHead->next;
mHead->next = p->next;
e = p->data;
delete p;
--mSize;
}
（5）判断栈空
//判断栈空
template <typename T>
bool Stack<T>::isEmpty()
{
return nullptr == mHead->next ? true : false;
}
（6）获取栈中元素个数
//获取栈中总元素个数
template <typename T>
int Stack<T>::getSize()
{
return mSize;
}
（7）输出栈中元素，但不出栈
template <typename T>
void Stack<T>::print()
{
Node<T>* p = mHead->next;
while (nullptr != p)
{
cout << p->data << " ";
p = p->next;
}
}
4.测试
int main()
{
Stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
st.push(6);
st.print();
cout <<endl << "栈中元素个数:" << st.getSize() << endl;
return 0;
}
输出：
6 5 4 3 2 1
栈中元素个数:6
| 
楼主
