stack.h

外排序 对于海量数据进行快速排序 然后利用败者树进行归并的算法的一个模板

#ifndef STACK_QUEUE_H
#define STACK_QUEUE_H

#include <stdlib.h>
#include <iostream.h>
#define InitSize 10

template<class T> class Stack;

template<class T>
class Stack
{
	T* Array;
	int top;
	int MaxSize;
	void doubleArray(int Max);
public:
	Stack();
	~Stack(){ delete [ ] Array; }
	void push(const T &info);
	void pop();
	void clear(){top = -1;}
	bool empty() const {return top == -1; }
	bool full() const {return top == MaxSize-1;}
	T getTop()const;
	void output()const;
};


template<class T>
Stack<T>::Stack( )
:top(-1), MaxSize(InitSize)
{
	Array = new T[MaxSize];
}

template<class T>
void Stack<T>::push(const T &info)
{
	if ( top + 1 == MaxSize )
		doubleArray( 2 * MaxSize );
	Array[++top] = info;
}

template<class T>
void Stack<T>::doubleArray(int Max)
{
	T *ArrayNew = new T[Max];
	for(int i=0;i<MaxSize;i++)
		ArrayNew[i]=Array[i];
	Array=ArrayNew;
	MaxSize=MaxSize*2;
}

template<class T>
void Stack<T>::pop( )
{
	if (top >= 0)
		top--;
	else
		cout<<"Stack is empty.\n";
}

template<class T>
T Stack<T>::getTop() const
{
	if (top >= 0)
		return Array[top];
	else
	{
		cout<<"Stack is empty.\n";
		return 0;
	}
}

template<class T>
void Stack<T>::output()const
{
	T info;
	if (top == -1)
	{
		cout<<"Stack is empty.\n";
		return;
	}
	for (int i = top; i >= 0;i-- )
	{
		info = Array[i];
		if (i == top)
			cout<<"==>";
		cout<<"\tStack[ "<<i<<" ] = "<<info<<" \n";
	}
}

#endif