栈的主要功能是:
bool Push(T val); //往栈顶添加元素val
T Top(); //返回栈顶元素的值
T Pop();//取出栈顶元素,并删除
void Clear(); //清空栈
bool IsEmpty();//判断是否为空
int Size();//返回元素个数
栈的链表表示
链表节点
template<class T>
class Node{
public:
~Node(void){ }
T val;
Node<T>* next;
Node(T nVal){
val = nVal;
next = NULL;
}
Node(void){}
};
栈的定义
template<class T>
class LinkStack
{
private:
Node<T>* m_pTop;
int size;
public:
LinkStack(void){
size = 0;
m_pTop = NULL;
}
~LinkStack(void){Clear();}
void Push(T val){ //栈顶添加元素
Node<T>* pNode = new Node<T>(val);
if(size == 0) //栈为空时
{
m_pTop = pNode;
}
else{
pNode->next = m_pTop;
m_pTop = pNode; //顶栈指针总是指向链表头
}
size++;
}
T Top(){ //返回栈顶元素
if(IsEmpty())
return NULL;
else
return m_pTop->val;
}
T Pop(){ //返回栈顶元素,并删除
if(IsEmpty())
return NULL;
else{
Node<T>* pNode = m_pTop;
m_pTop = m_pTop->next;
T tmp = pNode->val;
delete pNode;
size--;
return tmp;
}
}
void Clear(){ //清空栈
Node<T>* pNode;
while(m_pTop != NULL){
pNode = m_pTop;
m_pTop = m_pTop->next;
delete pNode;
size = 0;
}
}
bool IsEmpty() {
return size == 0?
true :false;}
int Size(){
return size;}
};