队列的实现和应用

队列概念

队列是先进先出的，所以区别于栈都在栈顶进行入栈和出栈，队列是在队头出队，在队尾入队，从而在程序实现上要注意是在队头操作还是队尾操作

程序实现

基类queue

template<class elemType>
class queue{
public:
   virtual bool is_empty() const=0;
   virtual elemType getHead() const=0;
   virtual elemType getTail() const=0;
   virtual void enQueue(const elemType& x)=0;
   virtual elemType deQueue()=0;
   virtual ~queue(){ }
};

队列对应的操作：

• 判断队列是否为空
• 查-----读队头元素，读队尾元素
• 增----入队
• 删----出队 

顺序实现

 采用循环队列，以保证空间不浪费

为了可以区分队列空和队列满的情况，0位置不放元素

注意：front指向队头元素前一个位置，rear正好指向队尾位置

#include"stack.h"
template<class elemType>
class seqQueue:public queue<elemType>{
private:
   elemType* data;
   int maxsize;
   int front,rear;//队头，队尾
   void doublespace();
public:
   //构造+析构
   seqQueue(int initsize=3){
       data=new elemType[initsize];
       maxsize=initsize;
       front=rear=0;//循环队列，空出0下标以区分队列满或空
   }
   ~seqQueue(){ delete[] data;}
   //基类函数实现
   bool is_empty() const{ return front==rear;}
   elemType getHead() const{ 
       return data[(front+1)%maxsize];//循环队列
       }
   elemType getTail() const{
       return data[rear];
   }
   void enQueue(const elemType& x){//入队--队尾rear
       if((rear+1)%maxsize==front)//队满
          doublespace();
       rear=(rear+1)%maxsize;
       data[rear]=x;
   }
   elemType deQueue(){
       front=(front+1)%maxsize;
       return data[front];
   }
};
template<class elemType>
void seqQueue<elemType>::doublespace(){
     elemType* tmp=data;
     data=new elemType[maxsize*2];
     for(int i=1;i<maxsize;i++){//0不存元素
        data[i]=tmp[(front+1)%maxsize];
        front++;//千万别忘了front的自增
     }
     //给新的data首尾指针赋值
     front=0;
     rear=maxsize-1;
     maxsize*=2;
     delete[] tmp;
}

 需要注意的地方：

• 由于front和rear定义的不同，getHead()时候front需要+1，而且因为循环队列，别忘了%maxsize,而getTail()只需要rear
• 队列出队是针对front的，入队是针对rear的，而且入队要判断队列是否满了

 doublespace()的特别之处：

扩展空间时，赋值希望把原循环队列在新的内存单元顺序存储：

 for(int i=1;i<maxsize;i++){ //0不存元素

        data[i]=tmp[(front+1)%maxsize];

        front++;//千万别忘了front的自增

     }

• 注意从1开始，因为0位置不存元素
• 注意赋值时候，是（front+1）%maxsize
• 别忘了front的自增

链表实现

• 采用不带头结点的单链表
•  单链表的表头作为队头，单链表的表尾作为队尾 
•  同时记录头尾结点的位置。

#include"queue.h"
#include<stdlib.h>
template<class elemType>
class linkQueue:public queue<elemType>{
private:
   struct node{//别加()
       elemType elem;
       node* next;
       //构造
       node():next(NULL){}
       node(const elemType& x,node* n=NULL){//别忘了NULL
            elem=x;
            next=n;
       }
       ~node(){}
   };
   node* front,* rear;//定义头尾两个指针
public:
   linkQueue(){
       front=rear=NULL;
   }
   ~linkQueue(){}
   //函数实现
    bool is_empty() const{
        return front==NULL;
    }
    elemType getHead() const{
        return front->elem;
    }
    elemType getTail() const{
        return rear->elem;
    }
    void enQueue(const elemType& x){//针对队尾
       if(rear==NULL){
           front=rear=new node(x);
       }
       else{
           rear->next=new node(x);
           rear=rear->next;
       }
    }
    elemType deQueue(){
       elemType x=front->elem;
       node* tmp=front;
       front=front->next;
       if(front==NULL) {
           rear=NULL;
       }
       delete tmp;
       return x;
    }
};

#include"stdlib.h"
template<class elemType>
class linkQueue{
private:
    struct node{
       elemType data;
       node* next;
       node():next(NULL){}
       node(const elemType& x,node* n=NULL):data(x),next(n){}
       ~node(){}
    };
    node *front,*rear;
public:
   linkQueue(){ front=rear=NULL;}
   ~linkQueue(){ }
   bool is_empty() const {return front==NULL;}
   elemType getHead() const{ return front->data;}
   elemType getTail() const{ return rear->data;}
   void enQueue(const elemType& x){
       if(rear==NULL)
       front=rear=new node(x);
       else{
           rear=rear->next=new node(x);
       }
   }
   elemType deQueue(){
       node* tmp=front;
       elemType x=front->data;
       front=front->next;
       delete tmp;
       if(front==NULL){
           rear=NULL;
       }
       return x;
   }
};

 这里初始化时候，front和rear指针都为空；队列只有一个元素时，front和rear都指向该元素；队列至少两个元素，front和rear才有区别。

注意：

入队，由于后进后出，针对队尾rear的操作：

如果没元素，申请一个结点，然后front和rear指向它，即：front=rear=new node(x);

有元素，在rear指针后申请一个结点，然后rear后移。

出队----特别注意一下，如果将队列唯一元素出队后，将rear置空

判断队列为空有三种方式：

1. rear==NULL
2. front==NULL
3. rear==front==NULL

队列的应用----列车重排

问题抽象

将入轨的这些车厢重新排列，将第n节车厢放在最后，第1节车厢放在最前面。

实现思想 

bool putBuffer(seqQueue<int>* buffer,int k,int n);//将车厢n放入合适的缓冲轨道
void checkBuffer(seqQueue<int>* buffer,int k,int& last);//将缓冲轨道队头符合输出顺序的出轨
void arrange(int a[],int n,int k){
   进入一条最合适的缓冲轨道
   检查每条缓冲轨道的队头元素，将可以放入出轨的元素出队，进入出轨
}

代码实现

#include<iostream>
using namespace std;
bool putBuffer(linkQueue<int>* buffer,int k,int n);//将车厢n放入合适的缓冲轨道
void checkBuffer(linkQueue<int>* buffer,int k,int& last);//将缓冲轨道队头符合输出顺序的出轨
void arrange(int a[],int n,int k){
    //参数为---存放n节车厢的数组a,可以利用的缓冲轨道数目为k
    linkQueue<int>* buffer=new linkQueue<int>[k];//用k个队列模拟k个缓冲轨道
    int last=0;//为checkBuffer的参数赋初值，表明等着1号车厢从缓冲轨道出轨
    for(int i=0;i<n;i++){//遍历n节车厢
         if(!putBuffer(buffer,k,a[i])){
             return;//车厢n如果放入缓冲轨道失败，说明无法实现顺序，程序结束--return
         }
         else{//放入成功了，要遍历缓冲轨道队头，将符合要求的出队
             checkBuffer(buffer,k,last);
         }
    }
}
bool putBuffer(linkQueue<int>* buffer,int k,int n){
    int avail=-1;//记录可放入的最优轨道
    int max=0;
    /*
    一般认为放入数值最大的后面为优：
    比如8可以放在5或7的后面，下一个车厢是6；8放在7后面，6可以放在5后面；
    而8放在了5后面，6就没地方放了
    故而要取可放入缓冲轨道中的队尾元素的最大值max
    */
   for(int i=0;i<k;i++){//遍历k条轨道
       if(buffer[i].is_empty()){
          if(avail==-1)  avail=i;//队列为空而且没找到合适轨道，就放入该轨道i
       }
       else if(buffer[i].getTail()<n&&buffer[i].getTail()>max){
           //队列队尾元素小于该车厢序号才能放，而且要选最大的
           max=buffer[i].getTail();
           avail=i;
       }
   }
   //判断找没找到，由于返回结果
   if(avail==-1) {
       cout<<"没有合适轨道放入车厢"<<n<<endl;
       return false;
   }
   else{
       buffer[avail].enQueue(n);
       cout<<"车厢"<<n<<"放入了缓冲轨道"<<avail<<endl;
       return true;
   }
}
void checkBuffer(linkQueue<int>* buffer,int k,int& last){
    bool flag=true;
    while(flag){
        flag=false;//循环结束出口
        for(int i=0;i<k;i++){
            if(!buffer[i].is_empty()&&buffer[i].getHead()==last+1){
                cout<<"车厢"<<buffer[i].deQueue()<<"从轨道"<<i<<"出轨";
                last++;
                flag=true;
                break;//重新进入判断队头的while
            }
        }
    }
}