#ifndef __STACK_H_INCLUDED__
#define __STACK_H_INCLUDED__
#include <cstdlib>
#include <iostream>
template <typename TYPE> class CStackNode; // スタック要素
template <typename TYPE> class CStack; // スタック
/*===========================================================================*/
/* CStackNode: */
/*===========================================================================*/
template <typename TYPE>
class CStackNode
{
public:// メンバ
CStackNode* m_prevnode;// 前の要素へのポインタ
CStackNode* m_nextnode;// 次の要素へのポインタ
TYPE m_data;// この要素が持つデータ
public:// コンストラクタ
CStackNode(TYPE data);
};
template <typename TYPE>
CStackNode<TYPE>::CStackNode(TYPE data)
{
m_data = data;
m_prevnode = m_nextnode = NULL;
}
/*===========================================================================*/
/* CStack: */
/*===========================================================================*/
template <typename TYPE>
class CStack
{
private:// メンバ
CStackNode<TYPE>* m_lownode; // スタック最下段要素へのポインタ
CStackNode<TYPE>* m_topnode; // スタック最上段要素へのポインタ
int m_elems; // スタックの要素数
public:// コンストラクタ＆デストラクタ
CStack(); // コンストラクタ
CStack(const CStack<TYPE>& rother); // コピーコンストラクタ
~CStack(); // デストラクタ
public:// インライン関数
inline int Size() const; // スタックの要素数
inline int Bytes() const; // スタック全要素のデータのバイト数
inline bool Empty() const; // スタックが空なら true
public:// メソッド
void Push(const TYPE& data); // スタックへ要素をプッシュ
TYPE Pop(); // スタックから要素をポップ
TYPE& Top(); // スタック最上段要素のデータへの参照を返す
const TYPE& Top() const; // "
void Clear(); // スタックのクリア
private:// メソッドその他
void Init(); // メンバの初期化
void Copy(const CStack<TYPE>& rother); // スタックのコピー
public:// オペレータのオーバロード
void operator =(const CStack<TYPE>& rother); // スタックのコピー
};
/*---------------------------------------------------------------------------*/
/* CStack: Inline Functions */
/*---------------------------------------------------------------------------*/
template <typename TYPE>
inline int CStack<TYPE> ::Size() const
{
return m_elems;
}
template <typename TYPE>
inline int CStack<TYPE> ::Bytes() const
{
return m_elems * sizeof(TYPE);
}
template <typename TYPE>
inline bool CStack<TYPE> ::Empty() const
{
return (m_topnode == NULL);
}
/*---------------------------------------------------------------------------*/
/* CStack: Constructers */
/*---------------------------------------------------------------------------*/
template <typename TYPE>
CStack<TYPE> ::CStack()
{
Init();
}
template <typename TYPE>
CStack<TYPE> ::CStack(const CStack<TYPE>& rother)
{
Init();
Copy(rother);
}
/*---------------------------------------------------------------------------*/
/* CStack: Destructer */
/*---------------------------------------------------------------------------*/
template <typename TYPE>
CStack<TYPE> ::~CStack()
{
Clear();
}
/*---------------------------------------------------------------------------*/
/* CStack: Methods */
/*---------------------------------------------------------------------------*/
template <typename TYPE>
void CStack<TYPE> ::Push(const TYPE& data)
{
CStackNode<TYPE>* newnode;
newnode = new CStackNode<TYPE>( data ); // 新規要素を確保
if (m_topnode == NULL) { // スタックが空なら
m_lownode = m_topnode = newnode; // 新規要素を最下段と最上段へ
} else { // スタックが空でなければ
m_topnode->m_nextnode = newnode; // 最上段要素の次に新規要素を繋げ
newnode->m_prevnode = m_topnode;// 新規要素の前に最上段要素を繋げ
m_topnode = newnode; // 最上段要素を更新
}
m_elems++; // 要素数をインクリメント
}
template <typename TYPE>
TYPE CStack<TYPE>::Pop()
{
if (m_topnode == false) {
std::cout << "error: Pop: stack underflow." << std::endl;
exit(0);
}
CStackNode<TYPE> *prevnode;
TYPE data;
data = m_topnode->m_data; // データを返す準備
prevnode = m_topnode->m_prevnode; // 要素の削除準備
delete m_topnode; // 要素の削除
// 以下、リンク
if (prevnode != NULL) { // 削除要素の前が空でなければ
prevnode->m_nextnode = NULL;// 次の要素へのポインタをクリアして
m_topnode = prevnode; // 最上段要素のポインタを更新
} else { // 削除要素がスタック最下段要素なら
m_topnode = NULL; // ポインタを
m_lownode = NULL; // クリア
} // 以上、リンク
m_elems--; // 要素数をデクリメント
return data;
}
template <typename TYPE>
TYPE& CStack<TYPE>::Top()
{
if (m_topnode != NULL)
return m_topnode->m_data;
else {
std::cout << "error: CStack: TYPE& Top: m_topnode is null." << std::endl;
exit(0);
}
}
template <typename TYPE>
const TYPE& CStack<TYPE>::Top() const
{
if (m_topnode != NULL)
return m_topnode->m_data;
else {
std::cout << "error: CStack: TYPE& Top: m_topnode is null." << std::endl;
exit(0);
}
}
template<typename TYPE>
void CStack<TYPE> ::Clear()
{
CStackNode<TYPE> *curstack, *delstack;
for (curstack = m_topnode; curstack != NULL; )// 要素を最上段から辿りすべて削除
{
delstack = curstack;
curstack = curstack->m_prevnode;
delete delstack;
}
Init();// メンバを初期化
}
/*---------------------------------------------------------------------------*/
/* CStack : Methods etc */
/*---------------------------------------------------------------------------*/
template <typename TYPE>
void CStack<TYPE> ::Init()
{
m_lownode = NULL;
m_topnode = NULL;
m_elems = 0;
}
template<typename TYPE>
void CStack<TYPE> ::Copy(const CStack<TYPE>& rother)
{
CStackNode<TYPE> *thisnode, *newnode;
for (thisnode = rother.m_lownode; thisnode != NULL; thisnode = thisnode->m_nextnode)
{
newnode = new CStackNode<TYPE>( thisnode->m_data );
if (m_topnode == NULL) {
m_lownode = m_topnode = newnode;
} else {
m_topnode->m_nextnode = newnode;
newnode->m_prevnode = m_topnode;
m_topnode = newnode;
}
}
m_elems = rother.m_elems;
}
/*---------------------------------------------------------------------------*/
/* CStack: Operator Overload */
/*---------------------------------------------------------------------------*/
template <typename TYPE>
void CStack<TYPE> ::operator =(const CStack<TYPE>& rother)
{
Copy(rother);
}
#endif//__STACK_H_INCLUDED__