STL--queue - acm1314 @ IT工程師數位筆記本

文章出處

queue-概述：

隊列是一種特殊的線性表，它只允許在表的前端（Front）進行刪除操作，而在表的后端（Rear）進行插入操作。

l進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。
隊列中沒有元素時，稱為空隊列。

在隊列這種數據結構中，最先插入在元素將是最先被刪除；反之最后插入的元素將最后被刪除，因此隊列又稱為“先進先出”（FIFO—First In First Out）的線性表。

bool empty()	隊列為空返回true，否則返回false
void pop()	刪除隊列的一個元素
void push( const TYPE &val )	將val元素加入隊列
size_type size()	返當前隊列中的元素數目
TYPE &back()	返回一個引用，指向隊列的最后一個元素
TYPE &front()	返回隊列第一個元素的引用

題目練習：

（會陸續添加）

priority_queue-概述：

優先隊列容器與隊列一樣，只能從隊尾插入元素，從隊首刪除元素。但是它有一個特性，就是隊列中最大的元素總是位于隊首，所以出隊時，并非按照先進先出的原則進行，而是將當前隊列中最大的元素出隊。

元素的比較規則默認按元素值由大到小排序，可以重載“＜”操作符來重新定義比較規則。

bool empty()	優先隊列為空返回true，否則返回false
void pop()	刪除優先隊列中的第一個元素
void push( const TYPE &val )	添加一個元素到優先隊列中，值為val
size_type size()	返當前隊列中的元素數目
TYPE &top ()	返回一個引用，指向最高優先級的元素

題目練習：

（會陸續添加）

1.一道并不簡單的綜合性題目。（小聲告訴你，讀入時考考慮遞歸）。 set + priority_queue 很虐心哦！

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1097

 1 #include<iostream>
 2 #include<queue>
 3 #include<set>
 4 #include<vector>
 5 using namespace std;
 6 
 7 void parse(vector<set<int> >&adj, unsigned int p=0)//十分巧妙地遞歸讀入。 
 8 {
 9     unsigned int x;
10     cin>>x;
11     if(p)
12     {
13         adj[p].insert(x);
14         adj[x].insert(p);
15     }
16     while(true)
17     {
18         char ch;
19         cin>>ch;
20         if(ch==')') break;
21         parse(adj, x);
22     }
23     return;
24 }
25 
26 int main()
27 {
28     //freopen( "in.txt", "r", stdin );
29     //freopen( "out.txt", "w", stdout );
30     char ch;
31     while(cin>>ch)
32     {
33         vector<set<int> > adj(1024, set<int>());
34         parse(adj);
35         priority_queue<int, vector<int>, greater<int> >leafs;
36         int n = 0;
37         for(unsigned int i = 0; i<adj.size();i++)
38         if(adj[i].size())
39         {
40             n++;
41             if(adj[i].size()==1)
42             leafs.push(i);
43         }
44         for(int k=1; k<n; k++)
45         {
46             unsigned int x = leafs.top();
47             leafs.pop();
48             unsigned int p = *(adj[x].begin());
49             if(k>1)
50             cout<<" ";
51             cout<<p;
52             adj[p].erase(x);
53             if(adj[p].size()==1)
54             leafs.push(p);
55         }
56         cout<<endl;
57     }
58     return 0;
59 }

View Code

2.求第K大的數。

http://acm.hdu.edu.cn/showproblem.php?pid=4006

#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#include<iostream>
using namespace std;

int main()
{
    int n, k;
    while(~scanf("%d%d", &n, &k))
    {
        priority_queue<int, vector<int>, greater<int> >que;
        while(n--)
        {
            char op[5];
            scanf("%s", op);
            if(op[0]=='I')
            {
                int val;
                scanf("%d", &val);
                que.push(val);
                while(que.size()>k) que.pop();
            }
            else printf("%d\n", que.top());
        }
    }
    return 0;
}

View Code

（提醒：不要直接交代碼，上面代碼不能通過杭電的編譯器）。
然后稍加改變，編寫自己的比較函數，而不是用自帶的算子（greater）。結果就過啦！也是十分的蛋疼，十分的無語！！!。

#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#include<iostream>
using namespace std;

struct Cmp{
    bool operator()(const int&t1, const int&t2)
    {
        return t1>t2;
    }
    
};

int main()
{
    int n, k;
    while(~scanf("%d%d", &n, &k))
    {
        priority_queue<int, vector<int>,Cmp>que;
        while(n--)
        {
            char op[5];
            scanf("%s", op);
            if(op[0]=='I')
            {
                int val;
                scanf("%d", &val);
                que.push(val);
                while(que.size()>k) que.pop();
            }
            else printf("%d\n", que.top());
        }
    }
    return 0;
}

View Code

上面這個代碼也不太好，因為它有了太多的進隊和出隊，每一次的進出都是需要維護優先隊列的，所以可以在入隊滿K個后，在后來的插入時，可以先比較一下，然后決定是否插入。

#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#include<iostream>
using namespace std;

struct Cmp{
    bool operator()(const int&t1, const int&t2)
    {
        return t1>t2;
    }
    
};

int main()
{
    int n, k;
    while(~scanf("%d%d", &n, &k))
    {
        priority_queue<int, vector<int>,Cmp>que;
        int t = k;
        char op[5];
        int val;
        while(t--)
        {
            scanf("%s", &op);
            scanf("%d", &val);
            que.push(val);
        }
         n = n-k;
         while(n--)
         {
             scanf("%s", &op);
             if(op[0]=='I')
             {
                 scanf("%d", &val);
                 if(val>que.top())
                 que.push(val), que.pop();
             }
             else printf("%d\n", que.top());
             
         }
    }
    return 0;
}

View Code

一般優先隊列的定義方法：

priority_queue< Type,vector<Type>,greater<Type> >(小頂堆)

priority_queue< Type,vector<Type>,less<Type> >(大頂堆)

如果是自定義的結構體類型

priority_queue<Node,vector<Node>,cmp>

需要自己自定義結構體類型：

struct cmp

{

bool operator()(const Node &t1,const Node &t2)

{

return t1.b<t2.b;//相當于less,大頂堆

}

};

3.又是一道可以用優先隊列解的題。優先隊列的功能還真強大。

http://acm.hdu.edu.cn/showproblem.php?pid=4393

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

struct Node{
    int F;
    int index;
    friend bool operator<(Node a, Node b)
    {
        if(a.F!=b.F) return a.F<b.F;
        else return a.index>b.index;
    }
};

priority_queue<Node>q[110];
int main()
{
    int T;
    int kase, n, S;
    Node a;
    scanf("%d", &T);
    for(kase=1; kase<=T; kase++)
    {
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d", &a.F, &S);
            a.index = i;
            q[S].push(a);
        }
        printf("Case #%d:\n", kase);
        for(int i=0; i<n; i++)
        {
            int fast = -1, id = 1;
            for(int j=1; j<=100; j++)
            if(!q[j].empty())
            {
                Node tmp=q[j].top();
                if(tmp.F+i*j>fast) fast=tmp.F+i*j, id=j;
                else if(tmp.F+i*j==fast&&tmp.index<q[id].top().index) id = j;
            }
            printf("%d", q[id].top().index);
            q[id].pop();
            if(i<n-1)printf(" ");
            else printf("\n");
        }
    }
    return 0;
}