队列【数据结构】

                                                        队列

 

一、介绍

队列是一种线性存储结构。队列中的数据是按照先进先出方式进出队列的。队列只允许在队首进行删除操作（出队），而在队尾进行插入操作（入队）。

 

二、C++实现（基于数组）

#include<iostream>

using namespace std;

template<class T>
class ArrayQueue{
	public:
		ArrayQueue();
		ArrayQueue(int size);
		~ArrayQueue();
		
		T front();//返回队首元素
		bool push(T e);//入队
		bool pop();//出队 
		bool empty();//返回队列是否为空 
		int size();//返回队列中的元素个数 
	
	private:
		T *arr;
		int count;//队列中元素的个数
		int capacity;//队列的容量 
};

//构造函数 
template<class T>
ArrayQueue<T>::ArrayQueue(int size)
{
	count=0;
	capacity=size;
	arr=new T[capacity];
	if(!arr)
	{
		cout<<"动态内存分配失败!"<<endl;
	}
}

template<class T>
ArrayQueue<T>::ArrayQueue()
{
	new (this)ArrayQueue(30);
}

//构造函数
template<class T>
ArrayQueue<T>::~ArrayQueue()
{
	count=capacity=0;
	if(!arr)
	{
		delete[] arr;
		arr=NULL;
	}
}

//返回队首元素
template<class T>
T ArrayQueue<T>::front()
{
	return arr[0];
}


//入队
template<class T>
bool ArrayQueue<T>::push(T e)
{
	//队列已满，入队失败，返回false 
	if(count>=capacity)
	 return false;
	arr[count++]=e;
	return true;
} 

//出队
template<class T>
bool ArrayQueue<T>::pop()
{
	//队列为空，出队失败，返回false 
	if(count<0)
	  return false;
	for(int i=0;i<count;i++)
	  arr[i]=arr[i+1];
	count--;
	return true;
}

//返回队列是否为空 
template<class T>
bool ArrayQueue<T>::empty()
{
	return count==0;
}

//返回队列中的元素个数 
template<class T>
int ArrayQueue<T>::size()
{
	return count;
}

int main()
{
	ArrayQueue<int> *queue=new ArrayQueue<int>();
	//入队操作
	cout<<"入队 5 7 4"<<endl;
	queue->push(5);
	queue->push(7);
	queue->push(4);
	while(!queue->empty())
	{
		cout<<"队列中元素个数为"<<queue->size()<<endl; 
		int front=queue->front();
		queue->pop();
		cout<<"删除队首元素"<<front<<endl;
	}
	if(queue->empty())
	  cout<<"队列为空！"<<endl; 
	return 0;
}