个人学习笔记:c++数组实现的模板队列和栈

1、队列

#include<iostream>
using namespace std;


template<class T>
class ArrayQueue
{
	public:
		ArrayQueue();//构造函数
		bool empty(){return listSize==0;};//判断队列是否为空,如果为空返回true,否则返回false 
		int size(){return listSize;}//返回队列元素数量 
		T& front();//返回队首元素的引用 
		T& back();//返回队尾元素的引用 
		void pop();//删除队首元素 
		void push(const T& theElement);//把元素加入队尾 
    private:
	  int queueFront;//队列首元素的位置 
	  int listSize;//队列的元素个数 
	  int arrayLength;//队列的容量 
	  T* queue;//创建一个数组用来存放队列 
	  
};

template<class T>
ArrayQueue<T>::ArrayQueue()//构造函数
{
	arrayLength=20;//初始长度为20 
	listSize=0;
	queueFront=-1;
	queue=new T[arrayLength];
}

template<class T>
T& ArrayQueue<T>::front()//返回队首元素的引用 
{
	if(listSize!=0)
	return queue[queueFront+1];
	else 
	cout<<"queue is null!"<<endl;
}

template<class T>
T& ArrayQueue<T>::back()//返回队尾元素的引用
{
	if(listSize!=0)
	return queue[queueFront+listSize];
	else 
	cout<<"queue is null!"<<endl;
} 

template<class T>
void ArrayQueue<T>::pop()//删除队首元素 
{
	if(listSize!=0)
	 {
	 	queue[queueFront+1].~T();
	 	queueFront=(queueFront+1)%arrayLength;
	 	listSize--;
	 }
	 else 
	 cout<<"queue is null!"<<endl;
}

template<class T>
void ArrayQueue<T>::push(const T& theElement)//把元素加入队尾
{
	if(listSize==arrayLength)//如果队列已满，队列容量加倍
	{
		T* temp=new T[arrayLength*2];
		if(queueFront==0)//没有形成环
		  for(int i=0;i<listSize;i++)
		    copy(queue,queue+listSize,temp);
		else //形成环 
		{
			for(int i=queueFront;i<arrayLength;i++)
			 temp[i-queueFront]=queue[i];
			for(int i=0;i<queueFront;i++)
			 temp[i+arrayLength-queueFront]=queue[i];
		}
		
		delete []queue;
		queue=temp;
		queueFront=0;
	    arrayLength*=2;	
	} 
	
	listSize++;
	int queueBack=(queueFront+listSize)%arrayLength;//插入到队尾 
	queue[queueBack]=theElement; 
}

2、栈

template<class T>
class ArrayStack
{
	public:
		ArrayStack(int initialCapacity=20);//构造函数 
		void push(const T&);//向栈顶插入元素 
		~ArrayStack()//析构函数 
		{delete []stack;}
		bool empty()const//判断栈是否为空 
		{return stackTop==-1;} 
		int size()const
		{return stackTop+1;}
		T& top()//返回栈顶元素 
		{
			return stack[stackTop];
		}
		void pop()//删除栈顶元素 
		{
			stack[stackTop--].~T();//T的析构函数 
		}
		
		
	private:
		T *stack;
		int stackTop;//栈顶 
		int arrayLength;//栈的容量 
			
};

template<class T>
ArrayStack<T>::ArrayStack(int initialCapacity)//构造函数
{
	arrayLength=initialCapacity;
	stackTop=-1;//初始时栈顶位置为-1 
	stack=new T[arrayLength];
} 

template<class T>
void ArrayStack<T>::push(const T& theElement)//向栈顶插入元素 
{
	if(stackTop==arrayLength-1)//栈已满,栈的容量加倍 
	{
		T *temp=new T[arrayLength*2];
		for(int i=0;i<arrayLength;i++)
		     temp[i]=stack[i];
		     
		delete []stack;
		stack=temp; 
		arrayLength*=2;
	} 
	
	stack[++stackTop]=theElement;
}