#ifndef __STACK_H_INCLUDED__
#define __STACK_H_INCLUDED__
#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_prevnode(0), m_nextnode(0), m_data(data)// 初期化子によるゼロクリア
{
}
/*===========================================================================*/
/* 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 bool empty() const; // スタックが空なら true
inline int bytes() const; // スタック全要素のデータのバイト数
public:// メソッド
void push(const TYPE& data); // スタックへ要素をプッシュ
void pop(); // スタックから要素をポップ
TYPE& top(); // スタック最上段要素のデータへの参照を返す
const TYPE& top() const; // "
void swap(Stack<TYPE>& rother) throw();// スタックをスワップ
void clear(); // スタックのクリア
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 == 0);
}
/*---------------------------------------------------------------------------*/
/* Stack: Constructers */
/*---------------------------------------------------------------------------*/
template <typename TYPE>
Stack<TYPE> ::Stack()
: m_lownode(0), m_topnode(0), m_elems(0)// 初期化子によるゼロクリア
{
}
template <typename TYPE>
Stack<TYPE> ::Stack(const Stack<TYPE>& rother)
: m_lownode(0), m_topnode(0), m_elems(0)// 初期化子によるゼロクリア
{
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: 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 == 0) { // スタックが空なら
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 == 0) {
std::cout << "error: Pop: stack underflow." << std::endl;
return;
}
StackNode<TYPE> *prevnode;
prevnode = m_topnode->m_prevnode;// 要素の削除準備
delete m_topnode; // 要素の削除
// 以下、リンク
if ( prevnode ) { // 削除要素の前が空でなければ
prevnode->m_nextnode = 0; // 次の要素へのポインタをクリアして
m_topnode = prevnode; // 最上段要素のポインタを更新
} else { // 削除要素がスタック最下段要素なら
m_lownode = m_topnode = 0; // ポインタをクリア
} // 以上、リンク
m_elems--; // 要素数をデクリメント
}
template <typename TYPE>
TYPE& Stack<TYPE>::top()
{
static TYPE dummy;
if ( m_topnode )
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 )
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>::swap(Stack<TYPE>& rother) throw()
{
std::swap(m_lownode, rother.m_lownode);// 最下段要素へのポインタをスワップ
std::swap(m_topnode, rother.m_topnode);// 最上段要素へのポインタをスワップ
std::swap(m_elems, rother.m_elems); // 要素数をスワップ
}
template<typename TYPE>
void Stack<TYPE> ::clear()
{
StackNode<TYPE> *curstack, *delstack;
for (curstack = m_topnode; curstack != 0; )// 要素を最上段から辿りすべて削除
{
delstack = curstack;
curstack = curstack->m_prevnode;
delete delstack;
}
// メンバのクリア
m_lownode = m_topnode = 0;
m_elems = 0;
}
/*---------------------------------------------------------------------------*/
/* Stack: Operator Overload */
/*---------------------------------------------------------------------------*/
template <typename TYPE>
Stack<TYPE>& Stack<TYPE> ::operator =(const Stack<TYPE>& rother)
{
Stack<TYPE>(rother).swap(*this);
return *this;
}
#endif//__STACK_H_INCLUDED__