#ifndef __STACK_H_INCLUDED__
#define __STACK_H_INCLUDED__
#include <cstdlib>
#include <iostream>
template <typename TYPE> class StackNode; // スタック要素
template <typename TYPE> class Stack; // スタック
/*===========================================================================*/
/* StackNode: */
/*===========================================================================*/
template <typename TYPE>
class StackNode
{
public:// メンバ
StackNode* m_prevnode; // 前の要素へのポインタ
StackNode* m_nextnode; // 次の要素へのポインタ
TYPE m_data; // この要素が持つデータ
public:// コンストラクタ
StackNode(TYPE data);
};
template <typename TYPE>
StackNode<TYPE>::StackNode(TYPE data)
{
m_data = data;
m_prevnode = m_nextnode = NULL;
}
/*===========================================================================*/
/* Stack: */
/*===========================================================================*/
template <typename TYPE>
class Stack
{
private:// メンバ
StackNode<TYPE>* m_lownode; // スタック最下段要素へのポインタ
StackNode<TYPE>* m_topnode; // スタック最上段要素へのポインタ
int m_elems; // スタックの要素数
public:// コンストラクタ＆デストラクタ
Stack(); // コンストラクタ
Stack(const Stack<TYPE>& rother);// コピーコンストラクタ
~Stack(); // デストラクタ
public:// インライン関数
inline int Size() const; // スタックの要素数
inline int Bytes() const; // スタック全要素のデータのバイト数
inline bool Empty() const; // スタックが空なら true
public:// メソッド
void Push(const TYPE& data); // スタックへ要素をプッシュ
void Pop(); // スタックから要素をポップ
TYPE& Top(); // スタック最上段要素のデータへの参照を返す
const TYPE& Top() const; // "
void Clear(); // スタックのクリア
private:// メソッドその他
void Init(); // メンバの初期化
void Copy(const Stack<TYPE>& rother); // スタックのコピー
public:// オペレータのオーバロード
Stack<TYPE>& operator =(const Stack<TYPE>& rother); // スタックのコピー
};
/*---------------------------------------------------------------------------*/
/* Stack: Inline Functions */
/*---------------------------------------------------------------------------*/
template <typename TYPE>
inline int Stack<TYPE> ::Size() const
{
return m_elems;
}
template <typename TYPE>
inline int Stack<TYPE> ::Bytes() const
{
return m_elems * sizeof(TYPE);
}
template <typename TYPE>
inline bool Stack<TYPE> ::Empty() const
{
return (m_topnode == NULL);
}
/*---------------------------------------------------------------------------*/
/* Stack: Constructers */
/*---------------------------------------------------------------------------*/
template <typename TYPE>
Stack<TYPE> ::Stack()
{
Init();
}
template <typename TYPE>
Stack<TYPE> ::Stack(const Stack<TYPE>& rother)
{
Init();
Copy(rother);
}
/*---------------------------------------------------------------------------*/
/* Stack: Destructer */
/*---------------------------------------------------------------------------*/
template <typename TYPE>
Stack<TYPE> ::~Stack()
{
Clear();
}
/*---------------------------------------------------------------------------*/
/* Stack: Methods */
/*---------------------------------------------------------------------------*/
template <typename TYPE>
void Stack<TYPE> ::Push(const TYPE& data)
{
StackNode<TYPE>* newnode;
newnode = new StackNode<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>
void Stack<TYPE>::Pop()
{
if (m_topnode == NULL) {
std::cout << "error: Pop: stack underflow." << std::endl;
return;
}
StackNode<TYPE> *prevnode;
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--; // 要素数をデクリメント
}
template <typename TYPE>
TYPE& Stack<TYPE>::Top()
{
static TYPE dummy;
if (m_topnode != NULL)
return m_topnode->m_data;
else {
std::cout << "error: Stack: TYPE& Top(): stack underflow." << std::endl;
return dummy;
}
}
template <typename TYPE>
const TYPE& Stack<TYPE>::Top() const
{
static TYPE dummy;
if (m_topnode != NULL)
return m_topnode->m_data;
else {
std::cout << "error: Stack: const TYPE& Top() const: stack underflow." << std::endl;
return dummy;
}
}
template<typename TYPE>
void Stack<TYPE> ::Clear()
{
StackNode<TYPE> *curstack, *delstack;
for (curstack = m_topnode; curstack != NULL; )// 要素を最上段から辿りすべて削除
{
delstack = curstack;
curstack = curstack->m_prevnode;
delete delstack;
}
Init();// メンバを初期化
}
/*---------------------------------------------------------------------------*/
/* Stack : Methods etc */
/*---------------------------------------------------------------------------*/
template <typename TYPE>
void Stack<TYPE> ::Init()
{
m_lownode = NULL;
m_topnode = NULL;
m_elems = 0;
}
template<typename TYPE>
void Stack<TYPE> ::Copy(const Stack<TYPE>& rother)
{
if (this == &rother)// 自分自身はコピーしない
return;
Clear();// スタックをクリア
StackNode<TYPE> *thisnode, *newnode;
for (thisnode = rother.m_lownode; thisnode != NULL; thisnode = thisnode->m_nextnode)
{
newnode = new StackNode<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;
}
/*---------------------------------------------------------------------------*/
/* Stack: Operator Overload */
/*---------------------------------------------------------------------------*/
template <typename TYPE>
Stack<TYPE>& Stack<TYPE> ::operator =(const Stack<TYPE>& rother)
{
Copy(rother);
return *this;
}
#endif//__STACK_H_INCLUDED__