数据结构面试之四——队列的常见操作题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。

四、队列的基本操作1.用数组构造队列队列即是满足先进先出的链表。

用数组存储的话，同样需要满足队列头front出栈，队列末尾rear入栈。

而对于数组来讲，rear和front可以代表数组头和尾。

不能简单的固定rear 和front的大小为maxSize和0，因为可能出现中间元素为空的现象。

所以，对于数组队列来讲，可以想象成环式存储，因为每一次入队后rear+1，每一次出队后front+1。

这就需要控制front和rear的大小，每一次修改只要满足front=（front+1）%maxSize，rear=（rear+1）%maxSize即可满足要求。

同样需要注意：入队操作前先判定队列是否已经满；出队操作前先判定队列是否为空。

template<typename Type>class arrQueue{public:arrQueue(intnSize=100);~arrQueue();arrQueue(constarrQueue<Type>& copyQueue);arrQueue&operator=(const arrQueue<Type>& otherQueue);voidinitializeQueue();void destroyQueue();bool isQueueEmpty();bool isQueueFull();void addQueue(constType& item);void deQueue(Type&deletedItem);private:int maxSize;int rear;int front;Type* list;};template<typename Type>arrQueue<Type>::arrQueue(int nSize=100){if(nSize < 0){nSize = 100;list = newType[nSize];front = 0;rear = 0;maxSize = 100;}else{list = newType[nSize];front = 0;rear = 0;maxSize =nSize;}}template<typename Type>arrQueue<Type>::~arrQueue(){if(!list){delete[]list; //注意数组的删除，为delete []list;list = NULL;}}template<typename Type>arrQueue<Type>::arrQueue(const arrQueue<Type>©Queue){maxSize =copyQueue.maxSize;front =copyQueue.front;rear = copyQueue.rear;list = newType[maxSize]; //注意需要自定义大小,容易出错.for( int i = 0; i <rear; i++){list[i] =copyQueue.list[i];}}template<typename Type>arrQueue<Type>& arrQueue<Type>::operator=(constarrQueue<Type>& otherQueue){if(this ==&otherQueue){cout <<"can't copy oneSelf!" << endl;return *this;}else{if(maxSize !=otherQueue.maxSize){cout<< "The Size of two Queue are not equal!" << endl;return*this;}else{maxSize= otherQueue.maxSize;front =otherQueue.front;rear =otherQueue.rear;for( inti = 0; i < rear; i++){list[i]= otherQueue.list[i]; }//endforreturn*this;}}//end else}template<typename Type>void arrQueue<Type>::initializeQueue(){destroyQueue();}template<typename Type>void arrQueue<Type>::destroyQueue(){front = 0;rear = 0;}//栈空的判定标志rear==front[初始]template<typename Type>bool arrQueue<Type>::isQueueEmpty(){return (rear ==front);}//空余1位作为判定位,可以把存储结构想象成环!//注意栈满的判定：1.保证空间都被占用;//2.保证rear的下一个位置=front即为满。

template<typename Type>bool arrQueue<Type>::isQueueFull(){return((rear+1)%maxSize == front);}template<typename Type>void arrQueue<Type>::addQueue(const Type& item){if(!isQueueFull()){list[rear] =item;rear =(rear+1)%maxSize;cout << item<< " was added to Queue!" << endl;}else{cout <<"The Queue was already Full!" << endl;}}template<typename Type>void arrQueue<Type>::deQueue(Type& deletedItem){if(!isQueueEmpty()){deletedItem =list[front];front =(front+1)%maxSize; //注意此处的判定!cout <<deletedItem << " was deleted from Queue!" << endl; }else{cout <<"The Queue was already Empty!" << endl;}}2.队列采用链表链式存储结构注意：1）此时的front和rear都变成了指针，front变成了头结点指针，而rear变成了尾节点的指针。

2）此处的front和rear类似于链表操作中的first和last。

3）入队实现主要在队列尾部实现，需要调整rear指针的指向；而出队操作主要在队头实现，需要调整front指针的指向。

template<typename Type>struct nodeType{Type info;nodeType* link;};template<typename Type>class linkedQueue{public:linkedQueue();~linkedQueue();linkedQueue(constlinkedQueue<Type>&);linkedQueue&operator=(const linkedQueue<Type>&);voidinitializeQueue();void destroyQueue();bool isQueueEmpty()const;bool isQueueFull()const;void addQueue(constType& item);void deQueue(Type&poppedItem);void nodeCount();private:nodeType<Type>*rear;nodeType<Type>*front;int count; //统计节点个数};template<typename Type>linkedQueue<Type>::linkedQueue(){count = 0;front = NULL;rear = NULL;}template<typename Type>linkedQueue<Type>::~linkedQueue(){while( front != NULL ){nodeType<Type>*tempNode = new nodeType<Type>;tempNode =front;front =front->link;deletetempNode;}//注意rear的清空rear = NULL;}template<typename Type>linkedQueue<Type>::linkedQueue(constlinkedQueue<Type>& copyQueue) {if(copyQueue.front !=NULL){nodeType<Type>*current;nodeType<Type>*first;nodeType<Type>*newNode;front = newnodeType<Type>;front->info= copyQueue.front->info; //此处的top不能直接用，内存报错！front->link= copyQueue.front->link;first =front; //first跟进当前链表...current =copyQueue.front->link; //current跟进copy 链表...while( current!= NULL){newNode= new nodeType<Type>;newNode->link= current->link;newNode->info= current->info;first->link= newNode;first =newNode;current= current->link;}//end whilerear = current;count =copyQueue.count;}//end ifelse{front = NULL;rear = NULL;count = 0;}}template<typename Type>linkedQueue<Type>&linkedQueue<Type>::operator=(constlinkedQueue<Type>& otherQueue) {//1避免自身赋值if(this ==&otherQueue){cout <<"Can't copy oneself!" << endl;return *this;}//2其他else{if(front !=NULL){destroyQueue();}if(otherQueue.front!= NULL){nodeType<Type>*current;nodeType<Type>*first;nodeType<Type>*newNode;front =new nodeType<Type>;front->info= otherQueue.front->info;front->link= otherQueue.front->link;first =front; //first跟进当前链表...current= otherQueue.front->link; //current跟进copy链表...while(current != NULL){newNode= new nodeType<Type>;newNode->link= current->link;newNode->info= current->info;first->link= newNode;first= newNode;current= current->link;}//endwhilerear =current;count =otherQueue.count;}//end ifelse{front =NULL;rear =NULL;count =0;}return *this;}}template<typename Type>void linkedQueue<Type>::initializeQueue(){destroyQueue();}template<typename Type>void linkedQueue<Type>::destroyQueue(){count = 0;//注意此处的销毁工作：需要循环判定!while(front != NULL){nodeType<Type>*temp = new nodeType<Type>; temp = front;front =front->link;}rear = NULL;}template<typename Type>bool linkedQueue<Type>::isQueueEmpty() const{return (front ==NULL);}template<typename Type>bool linkedQueue<Type>::isQueueFull() const //空间非固定，动态申请! {return false;}template<typename Type>void linkedQueue<Type>::addQueue(const Type& item){if(!isQueueFull()){nodeType<Type>*newNode = new nodeType<Type>;newNode->info= item;newNode->link= NULL;if(front ==NULL){front =newNode;rear =newNode;}else{rear->link= newNode;rear =newNode;}count++;cout <<item << " was pushed!" << endl;}}template<typename Type>void linkedQueue<Type>::deQueue(Type& deletedItem){if(!isQueueEmpty()){nodeType<Type>*temp = new nodeType<Type>;temp = front;deletedItem =front->info;front =front->link;count--;cout <<deletedItem << " was popped!" << endl;delete temp;}}template<typename Type>void linkedQueue<Type>::nodeCount(){cout <<"nodeCount = " << count << endl;}3.用栈实现队列注意栈是先进后出，而用两个栈：栈1先进后出，栈2在栈1的基础上先进后出，就能实现了先进先出。