c++队列及优先队列

淩亂°似流年 2023-10-21 06:27 146阅读 0赞

队列

特点：先进先出，可形成有序的结构，运用于算法设计；

常用操作：

Cpp:
    queue<int> q;       //定义；
    q.empty();              //如果队列为空返回true，否则返回false  
    q.size();               //返回队列中元素的个数  
    q.pop();                //删除队列首元素但不返回其值  
    q.front();              //返回队首元素的值，但不删除该元素  
    q.push();               //在队尾压入新元素  
    q.back();               //返回队列尾元素的值，但不删除该元素

#### 优先队列 ####

特点：按照键值的大小排队，stl里的用[大小根堆][Link 1]来实现，

/*优先队列的基本使用    2010/7/24    dooder*/  
    #include<stdio.h>  
    #include<functional>  
    #include<queue>  
    #include<vector>  
    using namespace std;  
    //定义结构，使用运算符重载,自定义优先级1  
    struct cmp1{  
        bool operator ()(int &a,int &b){  
            return a>b;//最小值优先  
        }  
    };  
    struct cmp2{  
        bool operator ()(int &a,int &b){  
            return a<b;//最大值优先  
        }  
    };  
    //定义结构，使用运算符重载,自定义优先级2  
    struct number1{  
        int x;  
        bool operator < (const number1 &a) const {  
            return x>a.x;//最小值优先  
        }  
    };  
    struct number2{  
        int x;  
        bool operator < (const number2 &a) const {  
            return x<a.x;//最大值优先  
        }  
    };  
    int a[]={14,10,56,7,83,22,36,91,3,47,72,0};  
    number1 num1[]={14,10,56,7,83,22,36,91,3,47,72,0};  
    number2 num2[]={14,10,56,7,83,22,36,91,3,47,72,0};  
      
    int main()  
    {   priority_queue<int>que;//采用默认优先级构造队列  
      
        priority_queue<int,vector<int>,cmp1>que1;//最小值优先  
        priority_queue<int,vector<int>,cmp2>que2;//最大值优先  
      
        priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”会被认为错误，  
                                                          //这是右移运算符，所以这里用空格号隔开  
        priority_queue<int,vector<int>,less<int> >que4;最大值优先  
      
        priority_queue<number1>que5;  
        priority_queue<number2>que6;  
      
        int i;  
        for(i=0;a[i];i++){  
            que.push(a[i]);  
            que1.push(a[i]);  
            que2.push(a[i]);  
            que3.push(a[i]);  
            que4.push(a[i]);  
        }  
        for(i=0;num1[i].x;i++)  
            que5.push(num1[i]);  
        for(i=0;num2[i].x;i++)  
            que6.push(num2[i]);  
      
      
        printf("采用默认优先关系:\n(priority_queue<int>que;)\n");  
        printf("Queue 0:\n");  
        while(!que.empty()){  
            printf("%3d",que.top());  
            que.pop();  
        }  
        puts("");  
        puts("");  
      
        printf("采用结构体自定义优先级方式一:\n(priority_queue<int,vector<int>,cmp>que;)\n");  
        printf("Queue 1:\n");  
        while(!que1.empty()){  
            printf("%3d",que1.top());  
            que1.pop();  
        }  
        puts("");  
        printf("Queue 2:\n");  
        while(!que2.empty()){  
            printf("%3d",que2.top());  
            que2.pop();  
        }  
        puts("");  
        puts("");  
        printf("采用头文件\"functional\"内定义优先级:\n(priority_queue<int,vector<int>,greater<int>/less<int> >que;)\n");  
        printf("Queue 3:\n");  
        while(!que3.empty()){  
            printf("%3d",que3.top());  
            que3.pop();  
        }  
        puts("");  
        printf("Queue 4:\n");  
        while(!que4.empty()){  
            printf("%3d",que4.top());  
            que4.pop();  
        }  
        puts("");  
        puts("");  
        printf("采用结构体自定义优先级方式二:\n(priority_queue<number>que)\n");  
        printf("Queue 5:\n");  
        while(!que5.empty()){  
            printf("%3d",que5.top());  
            que5.pop();  
        }  
        puts("");  
        printf("Queue 6:\n");  
        while(!que6.empty()){  
            printf("%3d",que6.top());  
            que6.pop();  
        }  
        puts("");  
        return 0;  
    }

常用操作：

priority_queue<int,vector<int>,cmp1> que;      //声明，que参照上面用法；
    que.empty();                                   //判断是否为空
    que.size();                                    //队列长度；
    que.push();                                    //插入；
    que.pop();                                     //删除；
    que.top();                                     //查询；

[Link 1]: http://baike.baidu.com/link?url=QIA1do740Zow0AfhNpB9ffcvtDG5SPQ1aWmEiU7k0zfltUHgnCYq1bE9SdbbfJyJ6933ehp_Ynb4HXYKZxP5NcVVbi5XeMdcNxNdDAQfRaPmMpQg6ZqgRarYnXILF3TKHkGojxjU07gQf8BSx0lHWvUA3SDTEwP79SbDTuxaFfFMdSDqBD4Ta8Thl1nDCDW1KlHHudMvDhzlHDJXJ_3bw_