学步园

今天抓起Stack的模板各种改了一发。。。经过各种无限CE之后终于把这BT的模板搞出来了。。。

又学了一堆关于模板的知识- - 主要就是结构体里面的static变量要在外面声明之后才可以使用- - 否则报错- -

原型：

template<typename T>class Stack;

使用方法：

using namespace PoPoQQQ_Stack;
int main()
{
	Stack<int> s;
	s.Push(1);//入栈
	cout<<s.Top()<<endl;//出栈
	cout<<s.Size()<<endl;//返回栈的大小
	cout<<s.Empty()<<endl;//返回栈是否为空
	s.Pop();//弹栈
	cout<<s.Empty()<<endl;
}

代码：

#define _STACK_
//Writen by PoPoQQQ
//Shouldn't access fuction "Top()" or "Pop()" when the stack is empty.
namespace PoPoQQQ_Stack{
	template<typename T>class Stack_Point{
	private:
		static Stack_Point<T>* bin;
	public:
		T mem;
		Stack_Point *last;
		void* operator new (size_t,T _,Stack_Point *__);
		void operator delete (void *p);
	};
	
	template<typename T> Stack_Point<T>* Stack_Point<T> :: bin;
	
	template<typename T> void* Stack_Point<T> :: operator new (size_t,T _,Stack_Point *__)
	{
		if(bin)
		{
			Stack_Point *re=bin;
			bin=bin->last;
			re->mem=_;re->last=__;
			return re;
		}
		static Stack_Point *mempool,*C;
		if(C==mempool)
		{
			C=new Stack_Point[1<<15];
			mempool=C+(1<<15);
		}
		C->mem=_;
		C->last=__;
		return C++;
	}
	
	template<typename T> void Stack_Point<T> :: operator delete (void *p)
	{
		( (Stack_Point<T>*)p)->last=bin;
	}
	
	template<typename T>class Stack{
	private:
		Stack_Point<T> *top;
		int size;
	public:
		Stack():top(0x0),size(0) {}
		inline T Top()
		{
			return top->mem;
		}
		inline void Pop()
		{
			Stack_Point<T>* temp=top->last;
			delete top;
			top=temp;
			--size;
		}
		inline bool Empty()
		{
			return size==0;
		}
		inline int Size()
		{
			return size;
		}
		inline void Push(T x)
		{
			top=new (x,top) Stack_Point<T>;
			++size;
		}
	};
}