tstack.h

此程序实现了表达式求值

// tstack.h
// 模版类声明和实现必须写在一个文件内
//
#ifndef __TSTACK_DOT_H__
#define __TSTACK_DOT_H__

#include <stdio.h>
#include <assert.h>

template<class T> class TStack;

template<class T>
class TNode
{
public:
	friend class TStack<T>;
public:
	TNode();
	~TNode();
	void SetNode(T d);
private:
	T data;
	TNode<T>* pNext;
	TNode<T>* pPrev;
};

template<class T>
class TStack
{
public:
	TStack();
	~TStack();

	void ClearAll();
	void Push(T t);
	T Pop();
	T GetTop();

	bool IsEmpty();
//	int GetTop(T& t)const;//取首元素,成功非0

private:
	void Free();

private:
	TNode<T>* m_pHead;
	TNode<T>* m_pTail;
};


/////////////////////////////////////////////////////////////////////////
// class TNode
//
template<class T>
TNode<T>::TNode() : pNext(NULL), pPrev(NULL)
{
}

template<class T>
TNode<T>::~TNode()
{
}

template<class T>
void TNode<T>::SetNode(T d)
{
	data = d;
	pNext = NULL;
	pPrev = NULL;
}

////////////////////////////////////////////////////////////////////////
//  class TStack
//

template<class T>
TStack<T>::TStack()
{
	m_pHead = m_pTail = NULL;
}

template<class T>
TStack<T>::~TStack()
{
	Free();
}

template<class T>
void TStack<T>::Free()
{
	ClearAll();
}

template<class T>
void TStack<T>::ClearAll()
{
	while(!IsEmpty())
		Pop();
}

template<class T>
void TStack<T>::Push(T t)
{
	TNode<T>* pTemp = new TNode<T>;
	assert(pTemp != NULL);
	pTemp->SetNode(t);

	if(NULL == m_pHead)
	{
		m_pHead = pTemp;
		m_pTail = m_pHead;
		m_pHead->pNext = NULL;
		m_pTail->pPrev = NULL;
	}
	else
	{
		m_pTail->pNext = pTemp;
		pTemp->pPrev = m_pTail;
		m_pTail = pTemp;
	}
}

template<class T>
T TStack<T>::Pop()
{
	T temp;
	if(m_pTail != NULL)
	{
		temp = m_pTail->data;
		TNode<T>* pTemp = m_pTail;
		m_pTail = m_pTail->pPrev;

		if(NULL == m_pTail)
			m_pHead = NULL;

		delete pTemp;
		pTemp = NULL;
	}

	return temp;
}

template<class T>
T TStack<T>::GetTop()
{
	T temp;
	if(m_pTail != NULL)
	{
		temp = m_pTail->data;
	}

	return temp;
}

template<class T>
bool TStack<T>::IsEmpty()
{
	return (NULL == m_pTail);
}

#endif