程序设计竞赛数据结构知识—队列

引言

队列，在生活中随处可见，在餐厅买饭要排队，在火车站买票要排队，这都是队列。在队列中，我们先排队的人，最先出队列，晚排队的人后出队列，并且只能从队尾加入队列中，不能插队，并且只能从队首出队，具有先进先出的特点。

队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。因此队列具有先进先出的特点。队列中没有元素时，称为空队列。

循环队列

在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。处了一些简单应用之外，真正实用的队列时循环队列。

在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。

队列的操作

队列支持两种操作，push和pop，push就是入队，pop则是出队，push每次只能将元素放置到队尾，而pop每次也只能抛出队顶的元素。其次还有front（）、back（）、size（）、empty（）等方法。

队列与STL

C++的STL里面已经内置了队列，使用时调用queue头文件。使用时像是操作基本类型一样，具体方法参考C++API，下面简单介绍一下基本的使用方法。

Queue

#include <iostream>
#include <queue>

using namespace std;

int main ()
{
  queue<int> myqueue;
  int myint;
  cout << "Please enter some integers (enter 0 to end):\n";

  do {
      cin >> myint;
      myqueue.push (myint);
  } while (myint);

  cout << "myqueue contains: ";

  while (!myqueue.empty())
  {
      cout << " " << myqueue.front();
      myqueue.pop();
  }
  return 0;
}

Priority Queue(优先队列)

优先队列类似队列，在优先队列中，优先级高的元素先出队列。

标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。

第一种用法，也是最常用的用法：

priority_queue<int> qi;

通过<操作符可知在整数中元素大的优先级高。
故示例1中输出结果为：9 7 5 3 1

第二种方法：
在示例1中，如果我们要把元素从小到大输出怎么办呢？
这时我们可以传入一个比较函数，使用functional.h函数对象作为比较函数。

priority_queue<int, vector<int>, greater<int> >qi2;

其中
第二个参数为容器类型。
第二个参数为比较函数。
故示例2中输出结果为：1 3 5 7 9

第三种方法：
自定义优先级。

struct node
{
    friend bool operator< (node n1, node n2)
    {
        return n1.priority < n2.priority;
    }
    int priority;
    int value;
};

在该结构中，value为值，priority为优先级。
通过自定义operator<操作符来比较元素中的优先级。
在示例3中输出结果为：
优先级  值
9          5
8          2
6          1
2          3
1          4

代码

#include<iostream>
#include<functional>
#include<queue>

using namespace std;

struct node
{
    friend bool operator< (node n1, node n2)
    {
        return n1.priority < n2.priority;
    }
    int priority;
    int value;
};

int main()
{
    const int len = 5;
    int i;
    int a[len] = {3,5,9,6,2};

    //示例1
    priority_queue<int> qi;
    for(i = 0; i < len; i++)
        qi.push(a[i]);
    for(i = 0; i < len; i++)
    {
        cout<<qi.top()<<" ";
        qi.pop();
    }
    cout<<endl;

    //示例2
    priority_queue<int, vector<int>, greater<int> >qi2;
    for(i = 0; i < len; i++)
        qi2.push(a[i]);
    for(i = 0; i < len; i++)
    {
        cout<<qi2.top()<<" ";
        qi2.pop();
    }

    cout<<endl;

    //示例3
    priority_queue<node> qn;
    node b[len];
    b[0].priority = 6; b[0].value = 1;
    b[1].priority = 9; b[1].value = 5;
    b[2].priority = 2; b[2].value = 3;
    b[3].priority = 8; b[3].value = 2;
    b[4].priority = 1; b[4].value = 4;

    for(i = 0; i < len; i++)
        qn.push(b[i]);

    cout<<"优先级"<<'\t'<<"值"<<endl;

    for(i = 0; i < len; i++)
    {
        cout<<qn.top().priority<<'\t'<<qn.top().value<<endl;
        qn.pop();
    }
    return 0;
}

例题1：hdu 1896 stones

Problem Description

Because of the wrong status of the bicycle, Sempr begin to walk east to west every morning and walk back every evening. Walking may cause a little tired, so Sempr always play some games this time. 
There are many stones on the road, when he meet a stone, he will throw it ahead as far as possible if it is the odd stone he meet, or leave it where it was if it is the even stone. Now give you some informations about the stones on the road, you are to tell me the distance from the start point to the farthest stone after Sempr walk by. Please pay attention that if two or more stones stay at the same position, you will meet the larger one(the one with the smallest Di, as described in the Input) first.

Input

In the first line, there is an Integer T(1<=T<=10), which means the test cases in the input file. Then followed by T test cases. 
For each test case, I will give you an Integer N(0<N<=100,000) in the first line, which means the number of stones on the road. Then followed by N lines and there are two integers Pi(0<=Pi<=100,000) and Di(0<=Di<=1,000) in the line, which means the position of the i-th stone and how far Sempr can throw it.

Output

Just output one line for one test case, as described in the Description.

Sample Input

2

2

1 5

2 4

2

1 5

6 6

Sample Output

11

12

代码：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct stone{int pos , dis;};
struct compare
{
    bool operator() (const stone & s1 , const stone & s2)
    {
        if(s1.pos != s2.pos){return s1.pos > s2.pos;}
        return s1.dis > s2.dis;
    }
};
int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int n;
        cin >> n;
        priority_queue<stone , vector<stone> , compare> record;
        for(int i = 1; i <= n; ++i)
        {
            stone s;
            cin >> s.pos >> s.dis;
            record.push(s);
        }
        int cnt = 1;
        while(!record.empty())
        {
            stone t = record.top();
            record.pop();
            if(cnt % 2)
            {
                t.pos += t.dis;
                record.push(t);
            }
            if(record.empty()){cout << t.pos << endl;}
            ++cnt;
        }
    }
    return 0;
}

例题2

Hdu 1242 rescue

Problem Description

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.

Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

Input

First line contains two integers stand for N and M.
Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend. 
Process to the end of the file.

Output

For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life." 

Sample Input

7 8

#.#####.

#.a#..r.

#..#x...

..#..#.#

#...##..

.#......

........

Sample Output

13

这个题目所用到的主要算法是广度搜索，优先队列是辅助作用。

代码：

#include <stdio.h>
#include <string.h>
#include <queue>

#define maxn 202
using std::priority_queue;

int n, m, ans;
const int mov[][2] = {0, 1, 0, -1, -1, 0, 1, 0};
char map[maxn][maxn];

struct Node{
       int x, y, time;
       friend bool operator<(Node a, Node b){
              return a.time > b.time;
       }
};

bool check(int x, int y){
       return x >= 0 && x < n && y >= 0
              && y < m && map[x][y] != '#';
}


bool BFS(int x, int y)
{
       Node now, tmp;
       now.x = x; now.y = y;
       map[x][y] = '#';
       now.time = 0;
       priority_queue<Node> Q;
       Q.push(now);
       while(!Q.empty()){
              now = Q.top(); Q.pop();
              for(int i = 0; i < 4; ++i){
                     tmp = now;
                     tmp.x += mov[i][0];
                     tmp.y += mov[i][1];
                     if(check(tmp.x, tmp.y)){
                            ++tmp.time;
                            if(map[tmp.x][tmp.y] == 'x')
                                   ++tmp.time;
                            else if(map[tmp.x][tmp.y] == 'r'){
                                   ans = tmp.time; return true;
                            }
                            map[tmp.x][tmp.y] = '#';
                            Q.push(tmp);
                     }
              }
       }
       return false;
}

int main()
{
       int i, j, x, y;
       while(scanf("%d%d", &n, &m) == 2){
              for(i = 0; i < n; ++i){
                     getchar();
                     for(j = 0; j < m; ++j){
                            map[i][j] = getchar();
                            if(map[i][j] == 'a'){
                                   x = i; y = j;
                            }
                     }
              }
              if(BFS(x, y)) printf("%d\n", ans);
              else printf("Poor ANGEL has to stay in the prison all his life.\n");
       }
       return 0;
}

总结

队列在竞赛中被广泛使用，尤其是优先队列，但是一般题目中直接考队列的并不多，大多题目中，队列都是只起到辅助作用，优先队列一般结合广搜、拓扑排序等算法使用。

推荐例题：Poj3614、Poj2431、Poj3253、Poj2449