Implementation and application of queue

Queue concept

The queue is first in, first out , So it is different from the stack that the stack is loaded and unloaded at the top of the stack , The queue is going out at the head of the queue , Join the team at the end of the team , Therefore, we should pay attention to whether the operation is at the head of the team or at the end of the team

Program realization

Base class 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(){ }
};

Operations corresponding to the queue ：

• Determines if the queue is empty
• check ----- Read the team leader element , Read the tail element
• increase ---- The team
• Delete ---- Out of the team  

Sequential implementation

  use Circular queue , To ensure that space is not wasted

In order to distinguish between empty and full queues ,0 Do not put elements in position

Be careful ：front Point to the previous position of the team header element ,rear It just points to the tail of the team

#include"stack.h"
template<class elemType>
class seqQueue:public queue<elemType>{
private:
   elemType* data;
   int maxsize;
   int front,rear;// Team head , A party 
   void doublespace();
public:
   // structure + destructor 
   seqQueue(int initsize=3){
       data=new elemType[initsize];
       maxsize=initsize;
       front=rear=0;// Circular queue , Vacate 0 Subscript to distinguish whether the line is full or empty 
   }
   ~seqQueue(){ delete[] data;}
   // Base class function implementation 
   bool is_empty() const{ return front==rear;}
   elemType getHead() const{ 
       return data[(front+1)%maxsize];// Circular queue 
       }
   elemType getTail() const{
       return data[rear];
   }
   void enQueue(const elemType& x){// The team -- A party rear
       if((rear+1)%maxsize==front)// The team is full 
          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 There is no element 
        data[i]=tmp[(front+1)%maxsize];
        front++;// Don't forget front Self increasing of 
     }
     // For the new data First and last pointer assignment 
     front=0;
     rear=maxsize-1;
     maxsize*=2;
     delete[] tmp;
}

  What to pay attention to ：

• because front and rear Different definitions ,getHead() When front need +1, And because of the circular queue , Don't forget %maxsize, and getTail() It only needs rear
• Queue out is for front Of , Joining the team is for rear Of , And you have to decide whether the queue is full

 doublespace() What's special about ：

When expanding space , The assignment wants to put Original loop queue In the new memory unit Sequential storage ：

 for(int i=1;i<maxsize;i++){ //0 There is no element

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

        front++;// Don't forget front Self increasing of

     }

• Attention from 1 Start , because 0 There are no elements in the location
• Pay attention to the assignment , yes （front+1）%maxsize
• Don't forget front Self increasing of

Linked list implementation

• use No leading node The single chain table of
•   Single chain watch The header is the team leader , Single chain watch The tail of the table is the tail of the team  
•   meanwhile Record the head and tail nodes The location of .

#include"queue.h"
#include<stdlib.h>
template<class elemType>
class linkQueue:public queue<elemType>{
private:
   struct node{// Don't add ()
       elemType elem;
       node* next;
       // structure 
       node():next(NULL){}
       node(const elemType& x,node* n=NULL){// Don't forget NULL
            elem=x;
            next=n;
       }
       ~node(){}
   };
   node* front,* rear;// Define the first two pointers and the last two pointers 
public:
   linkQueue(){
       front=rear=NULL;
   }
   ~linkQueue(){}
   // Function implementation 
    bool is_empty() const{
        return front==NULL;
    }
    elemType getHead() const{
        return front->elem;
    }
    elemType getTail() const{
        return rear->elem;
    }
    void enQueue(const elemType& x){// For the tail of the team 
       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;
   }
};

  here initialization When ,front and rear All pointers are null ; queue There's only one element when ,front and rear All point to this element ; queue At least two elements ,front and rear only There's a difference .

Be careful ：

The team , Because of the late comers and late comers , For the tail of the team rear The operation of ：

If there are no elements , Apply for a node , then front and rear Pointing to it , namely ：front=rear=new node(x);

There are elements , stay rear Apply for a node after the pointer , then rear Move backward .

Out of the team ---- Pay special attention to , If the queue The only element is out of the team after , take rear empty

There are three ways to judge whether the queue is empty ：

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

Application of queues ---- Train rearrangement

The problem is abstract

Rearrange these carriages into the rail , Will be the first n Put the carriage at the end , The first 1 The carriage is at the front .

Realization thought  

bool putBuffer(seqQueue<int>* buffer,int k,int n);// Put the carriage n Put in a suitable buffer rail 
void checkBuffer(seqQueue<int>* buffer,int k,int& last);// Will buffer the derailment of the track team head in accordance with the output sequence 
void arrange(int a[],int n,int k){
    Enter a most suitable buffer track 
    Check the header element of each buffer track , Get the elements that can be put into cheating out of the team , Enter the infidelity 
}

Code implementation

#include<iostream>
using namespace std;
bool putBuffer(linkQueue<int>* buffer,int k,int n);// Put the carriage n Put in a suitable buffer rail 
void checkBuffer(linkQueue<int>* buffer,int k,int& last);// Will buffer the derailment of the track team head in accordance with the output sequence 
void arrange(int a[],int n,int k){
    // Parameter is --- Deposit n An array of cars a, The number of buffer tracks available is k
    linkQueue<int>* buffer=new linkQueue<int>[k];// use k Queue simulation k A buffer track 
    int last=0;// by checkBuffer Initial value of the parameter of , Indicates waiting 1 Car No. 1 derailed from the buffer track 
    for(int i=0;i<n;i++){// Traverse n Coach compartment 
         if(!putBuffer(buffer,k,a[i])){
             return;// Carriage n If you fail to put the buffer track , Description sequence cannot be achieved , Program end --return
         }
         else{// Put it in successfully , To traverse the buffer track header , Will meet the requirements of the team 
             checkBuffer(buffer,k,last);
         }
    }
}
bool putBuffer(linkQueue<int>* buffer,int k,int n){
    int avail=-1;// Record the optimal track that can be placed 
    int max=0;
    /*
     It is generally considered that it is better to put it after the largest value ：
     such as 8 Can be placed in 5 or 7 Behind , The next carriage is 6;8 Put it in 7 Back ,6 Can be placed in 5 Back ;
     and 8 On the 5 Back ,6 There is no place to put 
     Therefore, take the maximum value of the tail element that can be put into the buffer track max
    */
   for(int i=0;i<k;i++){// Traverse k Tracks 
       if(buffer[i].is_empty()){
          if(avail==-1)  avail=i;// The queue is empty and no suitable track is found , Just put it into the track i
       }
       else if(buffer[i].getTail()<n&&buffer[i].getTail()>max){
           // The element at the end of the queue can only be put if it is less than the car serial number , And choose the largest 
           max=buffer[i].getTail();
           avail=i;
       }
   }
   // Judge whether you find it or not , Due to the return result 
   if(avail==-1) {
       cout<<" There is no suitable track to put into the car "<<n<<endl;
       return false;
   }
   else{
       buffer[avail].enQueue(n);
       cout<<" Carriage "<<n<<" Put in the buffer track "<<avail<<endl;
       return true;
   }
}
void checkBuffer(linkQueue<int>* buffer,int k,int& last){
    bool flag=true;
    while(flag){
        flag=false;// End of cycle exit 
        for(int i=0;i<k;i++){
            if(!buffer[i].is_empty()&&buffer[i].getHead()==last+1){
                cout<<" Carriage "<<buffer[i].deQueue()<<" From track "<<i<<" Derailment ";
                last++;
                flag=true;
                break;// Re enter the judging team leader while
            }
        }
    }
}