队列的实现和应用

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

template
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 seqQueue:public queue{
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
void seqQueue::doublespace(){
     elemType* tmp=data;
     data=new elemType[maxsize*2];
     for(int i=1;i 
 
 
 需要注意的地方：
 
 
由于front和rear定义的不同，getHead()时候front需要+1，而且因为循环队列，别忘了%maxsize,而getTail()只需要rear
队列出队是针对front的，入队是针对rear的，而且入队要判断队列是否满了
 
 
 
 doublespace()的特别之处：
 
 
扩展空间时，赋值希望把原循环队列在新的内存单元顺序存储：
 
 
 for(int i=1;i//0不存元素
 
 
        data[i]=tmp[(front+1)%maxsize];
 
 
        front++;//千万别忘了front的自增
 
 
     }
 
 
注意从1开始，因为0位置不存元素
注意赋值时候，是（front+1）%maxsize
别忘了front的自增
 
链表实现 
 
 
 
 
采用不带头结点的单链表
 单链表的表头作为队头，单链表的表尾作为队尾 
 同时记录头尾结点的位置。
 
#include"queue.h"
#include
template
class linkQueue:public queue{
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;
    }
};
 
 
 
 这里初始化时候，front和rear指针都为空；队列只有一个元素时，front和rear都指向该元素；队列至少两个元素，front和rear才有区别。
 
 
 
 
注意：
 
 
入队，由于后进后出，针对队尾rear的操作：
 
 
如果没元素，申请一个结点，然后front和rear指向它，即：front=rear=new node(x);
 
 
有元素，在rear指针后申请一个结点，然后rear后移。
 
 
 
 
出队----特别注意一下，如果将队列唯一元素出队后，将rear置空
 
 
 
 
判断队列为空有三种方式：
 
 
rear==NULL
front==NULL
rear==front==NULL
 
队列的应用----列车重排 
问题抽象 
 
 
 
 
 
 
 
将入轨的这些车厢重新排列，将第n节车厢放在最后，第1节车厢放在最前面。
 
 
实现思想  
 
 
 
 
 
 
 
bool putBuffer(seqQueue* buffer,int k,int n);//将车厢n放入合适的缓冲轨道
void checkBuffer(seqQueue* buffer,int k,int& last);//将缓冲轨道队头符合输出顺序的出轨
void arrange(int a[],int n,int k){
   进入一条最合适的缓冲轨道
   检查每条缓冲轨道的队头元素，将可以放入出轨的元素出队，进入出轨
}
 
代码实现 
#include
using namespace std;
bool putBuffer(seqQueue* buffer,int k,int n);//将车厢n放入合适的缓冲轨道
void checkBuffer(seqQueue* buffer,int k,int& last);//将缓冲轨道队头符合输出顺序的出轨
void arrange(int a[],int n,int k){
    //参数为---存放n节车厢的数组a,可以利用的缓冲轨道数目为k
    seqQueue* buffer=new seqQueue[k];//用k个队列模拟k个缓冲轨道
    int last=0;//为checkBuffer的参数赋初值，表明等着1号车厢从缓冲轨道出轨
    for(int i=0;i* buffer,int k,int n){
    int avail=-1;//记录可放入的最优轨道
    int max=0;
    
   for(int i=0;imax){
           //队列队尾元素小于该车厢序号才能放，而且要选最大的
           max=buffer[i].getTail();
           avail=i;
       }
   }
   //判断找没找到，由于返回结果
   if(avail==-1) {
       cout<<"没有合适轨道放入车厢"<