C++テンプレート学習のスタックの実現
3641 ワード
昨日はC++primer上のキューの実装を書きましたが、今日はその上でスタックの実装を見てみましょう.
ここでquesta.hヘッダファイルの内容は:
スタックはスタックの要求を実現するために、ここでは双方向チェーンテーブルを使用し、スタックのテンプレートクラスは以下の通りである.
このテンプレートクラスは主にインスタックpush、アウトスタックpop、クリアスタックcleanstack、圧入スタックの要素個数stack_を実現するlen、出力スタック内の要素リロード演算子<.
試験手順:
ここでquesta.hヘッダファイルの内容は:
#ifndef _QUSTA_H
#define _QUSTA_H 1
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
/** **/
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
/** **/
#include<bitset>
#include<utility>
#include<set>
#include<map>
/** **/
#include<algorithm>
#include<numeric>
/* */
#include<exception>
#include<stdexcept>
using namespace std;
#endif
スタックはスタックの要求を実現するために、ここでは双方向チェーンテーブルを使用し、スタックのテンプレートクラスは以下の通りである.
#ifndef _STACK_H
#define _STACK_H 1
#include"questa.h"
template<class type> class stackc;
template <class type> ostream& operator<<(ostream&,const stackc<type>&);
template<class type> class stackcitem{
type data;
stackcitem *prev;
stackcitem *next;
friend class stackc<type>;
friend ostream& operator<< <type>(ostream&, const stackc<type>&);
stackcitem():data(type()),prev(0),next(0){}
stackcitem(const type &t):data(t),prev(0),next(0){}
};
template<class type> class stackc{
private:
stackcitem<type> *headnode;
stackcitem<type> *tailnode;
int count;
public:
stackc():count(0){
cout<<"construct stack..."<<endl;
initstack();
}
void initstack();
void push(const type&);
type pop();
int stack_len();
void cleanstack();
friend ostream& operator<< <type>(ostream&, const stackc<type>&);
inline bool isempty()
{
return tailnode==0;
}
~stackc(){
cleanstack();
}
};
template<class type> void stackc<type>::initstack()
{
cout<<"init stack..."<<endl;
stackcitem<type> *node;
node=new stackcitem<type>;
cout<<"build stack node ok..."<<endl;
if(NULL==node)
{
cerr<<"no memory..."<<endl;
exit(1);
}
headnode=tailnode=node;
}
template<class type> void stackc<type>::push(const type &data)
{
stackcitem<type> *node;
node=new stackcitem<type>(data);
if(NULL==node)
{
cerr<<"no memory..."<<endl;
exit(1);
}
tailnode->next=node;
node->prev=tailnode;
tailnode=node;
++count;
}
template<class type> type stackc<type>::pop()
{
stackcitem<type> *p=tailnode;
type value=p->data;
p=p->prev;
delete tailnode;
tailnode=p;
--count;
return value;
}
template<class type> void stackc<type>::cleanstack(){
while(!isempty())
pop();
}
template<class type> int stackc<type>::stack_len(){
return count;
}
template <class type> ostream& operator<< <type> (ostream &os, const stackc<type> &q)
{
os <<"{*";
stackcitem<type> *p;
for(p=q.headnode->next;p;p=p->next)
os <<p->data<<",";
os<<"*}";
return os;
}
#endif
このテンプレートクラスは主にインスタックpush、アウトスタックpop、クリアスタックcleanstack、圧入スタックの要素個数stack_を実現するlen、出力スタック内の要素リロード演算子<.
試験手順:
#include"questa.h"
#include"queue.h"
#include"stack.h"
int main()
{
stackc<string> s;
s.push("hello");
s.push("world!");
cout<<s.stack_len()<<":"<<s<<endl;
while(!s.isempty())
cout<<s.pop()<<endl;
}