队列（Queue）

用途

1.访问资源的时候（比如几个电脑让同一个打印机进行打印）请求会被存在一个队列中，cpu处理进程也是一样的。

实现

1.循环数组方式实现

class array_queue{
    int front=-1,rear=-1;//队列的头指针和尾指针
    int size;
    int*array= nullptr;
public:
    array_queue(int s):size(s){
        array=new int[size];//申请空间
    }
    bool IsEmpty(){//判断队列是否为空
        return front==-1&&rear==-1;
    }
    bool IsFull(){//判断队列是否满了
        return (rear+1)%size==front;//循环数组判断队列满的情况
    }
    void Enqueue(int x){//插入
        if(IsEmpty()){
            front=rear=0;
        } else if(IsFull()){
            cout<<"the queue is full"<<endl;
            return;
        } else{
            rear=(rear+1)%size;//循环数组
        }
        array[rear]=x;
    }
    void Dequeue(){//删除最先进入队列的结点
        if(IsEmpty())return;
        else if(front==rear)front=rear=-1;
        else front=(front+1)%size;//循环数组
    }
    int Front(){//返回头结点的数据
        if(IsEmpty()){
            cout<<"the queue is empty"<<endl;
            exit(1);
        }
        return array[front];
    }
};

2.链表方式实现

struct Node{
    int data;
    Node*next;
};//链表节点
class list_queue{
    Node*head= nullptr;
    Node*tail= nullptr;
public:
    bool IsEmpty(){
        return head== nullptr&&tail== nullptr;//二者都为空的时候队列为空
    }
    void Enqueue(int x){
        Node*temp=new Node;
        temp->data=x;
        temp->next= nullptr;
        if(IsEmpty()){
            head=tail=temp;
        }else{
            tail->next=temp;
            tail=temp;
        }
    }
    void Dequeue(){
        if(IsEmpty()){
            cout<<"the queue is empty";
            return;
        }
        if(head==tail){
            head=tail= nullptr;//二者相等相当于队列仅剩余一个节点，删除后把队列置零即可
            return;
        }
        Node*temp=head;
        head=head->next;
        delete temp;
    }
    void Print(){
        if(IsEmpty())return;
        Node*temp=head;
        while(temp!= nullptr){
            cout<<temp->data<<" ";
            temp=temp->next;
        }
        cout<<endl;
    }
};