スタックのC++クラステンプレート実装
4909 ワード
ヘッダファイル:
実装ファイル:
テストファイル:
/*****************************************************************************
* stack.h
*
* A C++ template class implemented stack.
*
* The defualt initial size of the stack is set to 20. If the elements number
* exceed initial size, then it will be extended by a factor of 2.
*
* Zhang Ming, 2009-10
*****************************************************************************/
#ifndef STACK_H
#define STACK_H
#include <iostream>
#include <cstdlib>
#include <constants.h>
using namespace std;
namespace itlab
{
template <typename Type>
class Stack
{
public:
explicit Stack( int maxSize = INITSIZE );
~Stack();
// Stack( const Stack<Type> & );
// Stack<Type>& operator=( const Stack<Type> & );
inline bool isEmpty() const;
inline void makeEmpty();
inline void push( const Type &x );
inline void pop( Type &x );
inline void getTop( Type &x );
private:
int top;
int capacity;
Type *elements;
void handleOverflow();
inline void handleUnderflow();
};
// class Stack
#include <stack-impl.h>
}
// namespace itlab
#endif
// STACK_H
実装ファイル:
/*****************************************************************************
* stack-impl.h
*
* Implementation for Stack class.
*
* Zhang Ming, 2009-10
*****************************************************************************/
/**
* constructors and destructor
*/
template <typename Type>
Stack<Type>::Stack( int maxSize ) : top (-1), capacity(maxSize)
{
elements = new Type[maxSize];
if( !elements )
{
cerr << "Out of memory!" << endl;
exit(1);
}
};
template <typename Type>
Stack<Type>::~Stack()
{
top = -1;
capacity = INITSIZE;
delete []elements;
}
/**
* If the stack is empty, return true.
*/
template <typename Type>
inline bool Stack<Type>::isEmpty() const
{
return ( top == -1 );
}
/**
* Make the stack empty.
*/
template <typename Type>
inline void Stack<Type>::makeEmpty()
{
top = -1;
}
/**
* Push an element into the stack.
*/
template <typename Type>
inline void Stack<Type>::push( const Type &x )
{
elements[++top] = x;
if( top == capacity-1 )
handleOverflow();
};
/**
* Pop an element out of stack.
*/
template <typename Type>
inline void Stack<Type>::pop( Type &x )
{
if( !isEmpty() )
x = elements[top--];
else
handleUnderflow();
};
/**
* Get the top element of the stack.
*/
template <typename Type>
inline void Stack<Type>::getTop( Type &x )
{
if( !isEmpty() )
x = elements[top];
else
handleUnderflow();
};
/**
* If the capability of the stack exceeds the initial size, make it double.
*/
template <typename Type>
void Stack<Type>::handleOverflow()
{
capacity = EXTFACTOR * capacity ;
Type *newArray = new Type[capacity];
if( newArray == NULL )
{
cerr << "Out of memory!" << endl;
exit(1);
}
for( int i=0; i<=top; ++i )
newArray[i] = elements[i];
delete []elements;
elements = newArray;
};
/**
* Handle the error of get element from an empty stack.
*/
template <typename Type>
inline void Stack<Type>::handleUnderflow()
{
cerr << "The stack is empty!" << endl << endl;
exit( 1 );
};
テストファイル:
/*****************************************************************************
* stack_test.cpp
*
* Stack class testing.
*
* Zhang Ming, 2009-10
*****************************************************************************/
#include <iostream>
#include <string>
#include <utility>
#include <stack.h>
using namespace std;
using namespace itlab;
int main()
{
pair<int, string > stu;
Stack< pair<int, string> > s;
s.push( make_pair(1, "XiaoMing") );
s.push( make_pair(2, "XiaoHong") );
s.push( make_pair(3, "XiaoLing") );
s.getTop( stu );
cout << stu.first << "\t" << stu.second << endl;
cout << endl;
while( !s.isEmpty() )
{
s.pop( stu );
cout << stu.first << "\t" << stu.second <<endl;
}
cout << endl;
s.getTop( stu );
cout << stu.first << "\t" << stu.second <<endl;
cout << endl;
return 0;
}