C++题目 模拟STL stack类设计实现你的stack类，该类需具有入栈，出栈，判栈空，取栈顶元素等功能；

C++题目 模拟STL stack类设计实现你的stack类，该类需具有入栈，出栈，判栈空，取栈顶元素等功能；

struct CAtlPlex
{
CAtlPlex* pNext;
DWORD dwRef;
void* data() { return this+1; }
static CAtlPlex* Create(CAtlPlex*& head, size_t nMax, size_t cbElement);
void FreeDataChain();
};
inline CAtlPlex* CAtlPlex::Create( CAtlPlex*& pHead, size_t nMax, size_t nElementSize )
{
CAtlPlex* pPlex;
ATLASSERT( nMax > 0 );
ATLASSERT( nElementSize > 0 );
pPlex = static_cast< CAtlPlex* >(malloc(nMax*nElementSize+sizeof(CAtlPlex)));
if( pPlex == NULL )
{
return( NULL );
}
pPlex->pNext = pHead;
pHead = pPlex;
pHead->dwRef=0;
return( pPlex );
}
inline void CAtlPlex::FreeDataChain()
{
CAtlPlex* pPlex;
pPlex = this;
while( pPlex != NULL )
{
CAtlPlex* pNext;
pNext = pPlex->pNext;
free( pPlex );
pPlex = pNext;
}
}
template
struct CLinkedStack
{
public:
struct CNode
{
public:
TYPE m_data;
CNode(CONST TYPE& element):m_data(element){}
~CNode() throw(){}
protected:
CNode(const CNode&)throw();
CNode* m_pNext;
friend struct CLinkedStack;
};
CLinkedStack(LONG nBlockSize=128):m_nBlockSize(nBlockSize),
m_pHead(NULL),m_nElements(0),m_pBlocks(NULL),m_pFree(NULL)
{
ATLASSERT(nBlockSize>0);
}
~CLinkedStack()
{
RemoveAll();
ATLASSUME(m_nElements==0);
}
HRESULT Push(CONST TYPE& in);
HRESULT Pop();
TYPE Top();
LONG Count();
BOOL IsEmpty();
VOID RemoveAll();
protected:
HRESULT GetFreeNode();
CNode* NewNode(CONST TYPE& element,CNode* pNext);
VOID FreeNode(CNode* pNode);
CNode* m_pHead;
LONG m_nElements;
CAtlPlex* m_pBlocks;
CNode* m_pFree;
LONG m_nBlockSize;

};
template
HRESULT CLinkedStack::Push(CONST TYPE& in)
{
HRESULT hr=E_FAIL;
CNode* pNode=NewNode(in,m_pHead);
if(pNode==NULL)
{
hr=E_OUTOFMEMORY;
goto END;
}
m_pHead=pNode;
hr=S_OK;
END:
return hr;
}
template
HRESULT CLinkedStack::Pop()
{
HRESULT hr=E_FAIL;
CNode* pNode=m_pHead;
if(m_pHead==NULL||m_nElements==0)
{
ATLASSERT(m_pHead==NULL&&m_nElements==0);
hr=E_FAIL;
goto END;
}
m_pHead=m_pHead->m_pNext;
FreeNode(pNode);
hr=S_OK;
END:
return hr;
}
template
TYPE CLinkedStack::Top()
{
return m_pHead->m_data;
}
template
LONG CLinkedStack::Count()
{
return m_nElements;
}
template
BOOL CLinkedStack::IsEmpty()
{
return m_nElements==0;
}
template
HRESULT CLinkedStack::GetFreeNode()
{
HRESULT hr=S_OK;
if(m_pFree==NULL)
{
CAtlPlex* pPlex;
CNode* pNode;
pPlex=CAtlPlex::Create(m_pBlocks,m_nBlockSize,sizeof(CNode));
if(pPlex==NULL)
{
hr=E_OUTOFMEMORY;
goto END;
}
pNode = (CNode*)pPlex->data();
pNode += m_nBlockSize-1;
for( int iBlock = m_nBlockSize-1; iBlock >= 0; iBlock-- )
{
pNode->m_pNext = m_pFree;
m_pFree = pNode;
pNode--;
}
}
hr=S_OK;
ATLASSUME(m_pFree!=NULL);
END:
return hr;
}
#pragma push_macro("new")
#undef new
template
typename CLinkedStack::CNode* CLinkedStack::NewNode(CONST TYPE& element,CNode* pNext)
{
CNode* pNewNode=NULL;
if(GetFreeNode()!=S_OK)
{
goto END;
}
pNewNode=m_pFree;
m_pFree=m_pFree->m_pNext;
::new(pNewNode) CNode(element);
pNewNode->m_pNext=pNext;
m_nElements++;
ATLASSERT(m_nElements>0);
END:
return pNewNode;
}
#pragma pop_macro("new")
template
VOID CLinkedStack::FreeNode(CNode* pNode)
{
pNode->~CNode();
pNode->m_pNext=m_pFree;
m_pFree=pNode;
ATLASSERT(m_nElements>0);
m_nElements--;
if(m_nElements==0)
{
RemoveAll();
}
}
template
VOID CLinkedStack::RemoveAll()
{
CNode* pNode;
for (pNode = m_pHead; pNode != NULL; pNode = pNode->m_pNext)
pNode->~CNode();
m_nElements = 0;
m_pHead = NULL;
m_pBlocks->FreeDataChain();
m_pBlocks = NULL;
m_pFree = NULL;
}