シーケンススタックのテンプレートクラス実現
データ構造の観点から、スタックも線形表の一つであり、その特殊性は、スタックの基本的な動作か、それとも線形表に依存して実現されるかにある.スタックはスタックの一番上でのみ挿入と削除を許可します.倉庫の保存方式も順序スタックとチェーンスタックの2種類に分けられています.個人的には、運営だけしてスタックのトップを操作するなら、チェーンスタックは意味がないと思います.
#ifndef STACK_H_
#define STACK_H_
template <typename T>
class Stack
{
public:
Stack(int size = Stack_init_size);
//
~Stack();
Stack(const Stack<T> &s);
//
const Stack<T>& operator=(const Stack<T> &s);
//
void ClearStack();
//
bool StackEmpty();
// TRUE FALSE
int StackLength();
// ，
bool GetTop(T &elem);
// ， elem ， true， ERROR
void Push(T elem);
// elem
bool Pop(T &elem);
// ， ， elem ， true， error
private:
T *base;
T *top;
int m_size;
enum StackSize
{
Stack_init_size = 100, //
Stack_incerement = 10 //
};
};
template <typename T>
Stack<T>::Stack(int size)
{
base = new T[Stack_init_size];
if (base==NULL)
{
exit(1);
}
top = base;
m_size = size;
}
template <typename T>
Stack<T>::Stack(const Stack<T> &s)
{
base = new T[s.m_size];
if (base == NULL)
{
exit(1);
}
top = base;
m_size = s.m_size;
T * p1 =s.base ;
T * p2 = base;
while (p1!=s.top)
{
*p2 = *p1;
p1++;
p2++;
}
top = p2;
}
template <typename T>
const Stack<T>& Stack<T>::operator=(const Stack<T> &s)
{
delete[] base;
base = new T[s.m_size];
if (base == NULL)
{
exit(1);
}
top = base;
m_size = s.m_size;
T * p1 = s.base;
T * p2 = base;
while (p1 != s.top)
{
*p2 = *p1;
p1++;
p2++;
}
top = p2;
return *this;
}
template <typename T>
Stack<T>::~Stack()
{
delete[] base;
}
template <typename T>
int Stack<T>::StackLength()
{
int n = 0;
T * p = top;
while (p!= base)
{
n++;
p--;
}
return n;
}
template <typename T>
void Stack<T>::ClearStack()
{
while (top != base)
{
top--;
*top = 0;
}
}
template <typename T>
bool Stack<T>::StackEmpty()
{
if (top == base)
{
return true;
}
return false;
}
template <typename T>
bool Stack<T>::GetTop(T &elem)
{
if (StackEmpty())
{
return false;
}
else
{
top--;
elem = *top;
*top = 0;
return true;
}
}
template <typename T>
void Stack<T>::Push(T elem)
{
int size_increment;
if (top - base>Stack_init_size)
{
m_size = m_size + Stack_incerement;
T *temp = new T[m_size];
T *p = base;
T *q = temp;
while ((p + 1) != top)
{
*q = *p;
q++;
p++;
}
delete[] base;
base = temp;
*q = elem;
q++;
}
else
{
*top = elem;
top++;
}
}
template <typename T>
bool Stack<T>::Pop(T &elem)
{
if (top == base)
{
return false;
}
top--;
elem = *top;
*top = 0;
return true;
}
#endif